今晚写的有关于图的一些操作算法，欢迎指教
#include<stdio.h>#include<malloc.h>
#include<windows.h>
#define MAX_Weight 1000 //定义无穷大的具体值
#define MAX_Ver 10 //定义顶点数的最大值
typedef enum
{
DG, //不带权有向图
AG, //不带权无向图
WDG, //带权有向图
WAG //带权无向图
}GraphKind; //图的种类结构体定义
/**************************
//
//邻接链表表示法
//
**************************/
typedef struct LinkNode
{
int adjvex; //邻接点在头结点数组中的下标位置
int infor; //边或弧的相关信息,如权值
struct LinkNode *next; //指向下一个邻接点
}LinkNode;
typedef struct
{
char data; //顶点信息
int degree; //顶点的度
LinkNode *first; //指向第一个表结点
}VexNode; //顶点结点类型定义
typedef struct
{
char data1,data2; //边或弧所依附的顶点
int infor; //边或弧的相关信息,如权值
}ArcNode; //边或弧类型定义
typedef struct
{
GraphKind kind; //图的种类标志
int vexnum; //顶点数目
int arcnum; //边或弧的数目
VexNode list[MAX_Ver]; //顶点信息集合
}Graph; //图的类型定义
void Create_Graph( Graph *G ) //图的初始化,建立一个空图
{
G->vexnum = 0;
G->arcnum = 0;
}
/*
* 图的顶点定位,如果顶点存在则返回该顶点在头结点数组中的下标值;
* 如果顶点不存在,则返回数值-1.
*/
int Locate_Vex( Graph *G, char v )
{
int k;
for ( k=0; k<G->vexnum; k++ )
{
if(G->list[k].data == v) //顶点存在则返回该顶点下标值
return k;
else
continue;
}
return -1; //顶点不存在,则返回-1
}
/***************************
* 向头结点数组中添加顶点
***************************/
void Add_Vex( Graph *G, char v )
{
if(G->vexnum > MAX_Ver)
printf("图的顶点数超出预定范围,发生越界!\n");
else if(Locate_Vex(G,v) != -1)
printf("你所输入的顶点已经存在!\n");
else
{
G->list[G->vexnum].data = v; //向数组存入顶点
G->list[G->vexnum].degree = 0; //顶点的度置为0
G->list[G->vexnum].first = NULL; //顶点指针域置为空
G->vexnum++; //顶点数增加1
}
}
/******************************
* 利用两个顶点构造图的边或弧
******************************/
void Add_Arc( Graph *G, ArcNode *arc )
{
int k,j;
LinkNode *q,*p; //边或弧所依附的表结点
k = Locate_Vex(G,arc->data1); //弧尾顶点的下标值
j = Locate_Vex(G,arc->data2); //弧头顶点的下标值
if(k == -1)
printf("顶点%c不存在!\n",arc->data1);
else if(j == -1)
printf("顶点%c不存在!\n",arc->data2);
else
{
p = (LinkNode*)malloc(sizeof(LinkNode)); //开辟弧尾表结点的存储空间
p->adjvex = arc->data1;
p->infor = arc->infor;
p->next = NULL;
q = (LinkNode*)malloc(sizeof(LinkNode)); //开辟弧头表结点的存储空间
q->adjvex = arc->data2;
q->infor = arc->infor;
q->next = NULL;
}
//如果建立无向图的邻接链表,则利用头插入法把两个表结点分别插入到对应的单链表中
if(G->kind == AG || G->kind == WAG)
{
q->next = G->list[k].first;
G->list[k].first = q;
G->list[k].degree++;
p->next = G->list[j].first;
G->list[j].first = p;
G->list[j].degree++;
}
else
{
//建立有向图的正邻接链表
q->next = G->list[k].first;
G->list[k].first = q;
G->list[k].degree++;
}
}
//图的邻接链表输出
void Output_Graph( Graph *G )
{
int j;
LinkNode *q;
printf("\n你输入的图是:");
switch(G->kind)
{
case 0:
printf(" DG:不带权有向图!\n"); break;
case 1:
printf(" AG:不带权无向图!\n"); break;
case 2:
printf(" WDG:带权有向图!\n"); break;
case 3:
printf(" WAG:带权无向图!\n"); break;
}
printf("\n图的邻接链表输出如下:\n\n");
printf("下标 | 顶点 | 度 | 邻接点下标 | 权值");
for ( j=0; j<G->vexnum; j++ )
{
printf("\n");
printf(" %d (%c , %d)",j,G->list[j].data,G->list[j].degree);
q = G->list[j].first;
while(q != NULL)
{
int k;
k = Locate_Vex(G,q->adjvex);
printf("%s"," ->");
printf(" (%d,%d)",k,q->infor);
q = q->next;
}
}
}
typedef enum
{
F,
T
}Bool;
Bool visit[MAX_Ver];
//从顶点V出发,深度遍历V所在的子图
void DFS( Graph *G ,char v )
{
int k;
k = Locate_Vex(G,v);
LinkNode *p;
visit[k] = T; //置访问标志
printf("%c ",G->list[k].data);
p = G->list[k].first;
while(p != NULL)
{
int j = Locate_Vex(G,p->adjvex);
if(visit[j] != TRUE)
DFS(G,p->adjvex);
p = p->next;
}
}
//深度优先遍历函数
void DFS_Traverse( Graph *G )
{
int v;
for ( v=0; v<G->vexnum; v++ )
visit[v] = F;
LinkNode *p = G->list[v].first;
for ( v=0; v<G->vexnum; v++ )
if(!visit[v])
DFS(G,G->list[v].data);
}
//定义一个队列将要访问的顶点
typedef struct
{
int Data[MAX_Ver];
int front,rear;
}Queue;
//广度优先遍历函数
void BFS_Traverse( Graph *G )
{
int k,v,w;
LinkNode *p;
Queue *q;
q = (Queue*)malloc(sizeof(Queue)); //开辟空间
q->front = q->rear = 0; //初始化队列队头与队尾
for ( k=0; k<G->vexnum; k++ )
visit[k] = F; //初始化访问标志
for ( k=0; k<G->vexnum; k++ )
{
if(!visit[k]) //下标为V的顶点尚未访问
{
q->Data[q->rear++] = k; //顶点下标入队
while(q->front != q->rear)
{
w = q->Data[q->front++];
visit[w] = T;
printf("%c ",G->list[w].data);
p = G->list[w].first;
while(p != NULL)
{
if(!visit[Locate_Vex(G,p->adjvex)])
q->Data[q->rear++] = Locate_Vex(G,p->adjvex);
p = p->next;
}
}
}
}
}
int main()
{
int weight; //边或弧的权值
char Vex[MAX_Ver],vex,fex1,fex2; //图的顶点
char Vex1[MAX_Ver],Vex2[MAX_Ver]; //边或弧所依附的两个顶点
Graph *G; //定义一个图类型
ArcNode *arc; //定义一个边类型
printf("调用初始化函数建立空图G...\n");
G = (Graph*)malloc(sizeof(Graph)); //申请存放图G的空间
Create_Graph(G); //调用初始化函数建立G
printf("初始化结束!\n");
printf("你要建立的图种类是:\n 0:不带权有向图 1:不带权无向图 2:带权有向图 3:带权无向图\n");
scanf("%d",&G->kind);
printf("请输入图的顶点,以\".\"结束.\n");
while( 1 )
{
scanf("%s",Vex);
vex = Vex[0];
if(vex == '.')
break;
else
Add_Vex(G,vex);
}
arc = (ArcNode*)malloc(sizeof(ArcNode));
if(G->kind == AG || G->kind == DG)
{
printf("\n\n请按\"顶点 顶点\"的形式输入图的边或弧,当输入\". .\"时结束输入!\n");
while( 1 )
{
scanf("%s%s",Vex1,Vex2);
fex1 = Vex1[0];
fex2 = Vex2[0];
if(fex1 == '.' && fex2 == '.')
break;
else
{
arc->data1 = fex1;
arc->data2 = fex2;
arc->infor = 0;
Add_Arc(G,arc);
printf("继续输入边或弧:\n");
}
}
}
else
{
printf(" \n\n请按\"顶点 顶点 权值\"的形式输入图的边或弧,当输入\". . 0\"时结束输入!\n");
while( 1 )
{
scanf("%s%s%d",Vex1,Vex2,&weight);
fex1 = Vex1[0];
fex2 = Vex2[0];
if(fex1 == '.' && fex2 =='.' && weight == 0)
break;
else
{
arc->data1 = fex1;
arc->data2 = fex2;
arc->infor = weight;
Add_Arc(G,arc);
printf("继续输入边或弧:\n");
}
}
}
Output_Graph(G);
int ch;
printf("\n\n你想通过哪种方式遍历所建立的图?\n");
printf("1:深度优先遍历(DFS)\n2:广度优先遍历(BFS)\n\n");
L:scanf("%d",&ch);
switch(ch)
{
case 1:
{
printf("你选择了深度优先遍历,遍历结果如下:\n");
DFS_Traverse(G); //调用深度优先遍历函数
break;
}
case 2:
{
printf("你选择了广度优先遍历,遍历结果如下:\n");
BFS_Traverse(G); //调用广度优先遍历函数
break;
}
default:
printf("输入错误,请重新输入:");
goto L;
}
Sleep(2*1000);
printf("\n\n电脑分析结果与人工分析结果一致!\n\n");
return 0;
}
