#define M 20
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/*定义图*/
typedef struct{
int V
;
int R
;
int vexnum;
}Graph;
/*定义队列*/
typedef struct{
int V
;
int front;
int rear;
}Queue;
/*全局变量：访问标志数组*/
int visited
;
/*创建图*/
void creatgraph(Graph *g,int n);
/* 打印图的邻接矩阵 */
void printgraph(Graph *g);
/* 访问顶点 */
void visitvex(Graph *g,int vex);
/* 获取第一个未被访问的邻接节点 */
int firstadjvex(Graph *g,int vex);
/* 获取下一个未被访问的邻接节点(深度遍历) */
int nextadjvex(Graph *g,int vex,int w);
/* 深度递归遍历 */
void dfs(Graph *g,int vex);
void dfstraverse(Graph *g);
/* 初始化队列 */
initqueue(Queue *q);
/* 判断队列是否为空 */
int quempty(Queue *q);
/* 入队操作 */
enqueue(Queue *q,int e);
/* 出队操作 */
dequeue(Queue *q);
/* 广度遍历 */
void BESTraverse(Graph *g);
/* 主程序 */
main()
{
int n;
Graph *g=(Graph *)malloc(sizeof(Graph));
char menu;
printf("请输入图的顶点个数:/n");
scanf("%d",&n);
creatgraph(g,n);
printf("图的邻接矩阵如下:/n");
printgraph(g);
input:
printf("请输入您的选择(b-广度优先遍历，d-深度优先遍历，q-退出): /n");
while((menu=getchar())=='/n');
if(menu=='b')
{
printf("广度优先遍历结果如下:/n");
BESTraverse(g);
printf("/n");
goto input;
}
else if(menu=='d')
{
printf("深度优先遍历结果如下:/n");
dfstraverse(g);
printf("/n");
goto input;
}
else if(menu=='q')
{
exit(0);
}
else
{
printf("您的输入有误!/n");
}
}
/*创建图*/
void creatgraph(Graph *g,int n)
{
int i,j,r1,r2,weight;
g->vexnum=n;
/*顶点用i表示*/
for(i=1;i<=n;i++)
{
g->V[i]=i;
}
/*初始化R*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
g->R[i][j]=0;
}
/*输入R*/
printf("请输入有关系的两个边及其权重，格式如(0,0,0 代表结束):/n");
scanf("%d,%d,%d",&r1,&r2,&weight);
while(r1!=0&&r2!=0&&weight!=0)
{
g->R[r1][r2]=weight;
g->R[r2][r1]=weight;
scanf("%d,%d,%d",&r1,&r2,&weight);
}
}
/*打印图的邻接矩阵*/
void printgraph(Graph *g)
{
int i,j;
for(i=1;i<=g->vexnum;i++)
{
for(j=1;j<=g->vexnum;j++)
{
printf("- ",g->R[i][j]);
}
printf("/n");
}
}
/*访问顶点*/
void visitvex(Graph *g,int vex)
{
printf("%d ",g->V[vex]);
}
/*获取第一个未被访问的邻接节点*/
int firstadjvex(Graph *g,int vex)
{
int w,i;
for(i=1;i<=g->vexnum;i++)
{
if(g->R[vex][i]==1&&visited[i]==0)
{
w=i;
break;
}
else
{
w=0;
}
}
return w;
}
/*获取下一个未被访问的邻接节点(深度遍历)*/
int nextadjvex(Graph *g,int vex,int w)
{
int t;
t=firstadjvex(g,w);
return t;
}
/*深度递归遍历*/
void dfs(Graph *g,int vex)
{
int w;
visited[vex]=1;
visitvex(g,vex);
for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w))
if(!visited[w])
{
dfs(g,w);
}
}
void dfstraverse(Graph *g)
{
int i;
for(i=1;i<=g->vexnum;i++)
visited[i]=0;
for(i=1;i<=g->vexnum;i++)
if(!visited[i])
{dfs(g,i);}
}
/*初始化队列*/
initqueue(Queue *q)
{
q->fr;
q->rear=0;
}
/*判断队列是否为空*/
int quempty(Queue *q)
{
if(q->front==q->rear)
{
return 0;
}
else
{
return 1;
}
}
/*入队操作*/
enqueue(Queue *q,int e)
{
if((q->rear+1)%M==q->front)
{
printf("The queue is overflow!/n");
return 0;
}
else
{
q->V[q->rear]=e;
q->rear=(q->rear+1)%M;
return 1;
}
}
/*出队操作*/
dequeue(Queue *q)
{
int t;
if(q->front==q->rear)
{
printf("The queue is empty!/n");
return 0;
}
else
{
t=q->V[q->front];
q->front=(q->front+1)%M;
return t;
}
}
/*广度遍历*/
void BESTraverse(Graph *g)
{
int i;
Queue *q=(Queue *)malloc(sizeof(Queue));
for(i=1;i<=g->vexnum;i++)
{
visited[i]=0;
}
initqueue(q);
for(i=1;i<=g->vexnum;i++)
{
if(!visited[i])
{
visited[i]=1;
visitvex(g,g->V[i]);
enqueue(q,g->V[i]);
while(!quempty(q))
{
int u,w;
u=dequeue(q);
for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))
{
if(!visited[w])
{
visited[w]=1;
visitvex(g,w);
enqueue(q,w);
}
}
}
}
}
}
