#define M 20
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
typedef struct{/*定义图*/
int V[M];
int R[M][M];
int vexnum;
}Graph;
void creatgraph(Graph *g,int n){/*创建图*/
int i,j,r1,r2;
g->vexnum=n;
for(i=1;i<=n;i++)/*顶点用i表示*/{g->V[i]=i;}for(i=1;i<=n;i++)/*初始化R*/ for(j=1;j<=n;j++){g->R[i][j]=0;}printf("Please input R(0,0 END):
\n");/*输入R*/
scanf("%d,%d",&r1,&r2);
while(r1!=0&&r2!=0){g->R[r1][r2]=1;
g->R[r2][r1]=1;
scanf("%d,%d",&r1,&r2);}}
void printgraph(Graph *g){/*打印图的邻接矩阵*/
int i,j;
for(i=1;i<=g->vexnum;i++)
{ for(j=1;j<=g->vexnum;j++){printf("%2d ",g->R[i][j]);}printf("\n");}}
int visited[M];/*全局变量：
访问标志数组*/
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);}}
typedef struct{/*定义队列*/
int V[M];
int front;
int rear;
}Que;
void Initque(Que *q){/*初始化队列*/
q->front=0;
q->rear=0;}int Quempty(Que *q){/*判断队列是否为空*/
if(q->front==q->rear){return 0;}else{return 1;}}
Enque(Que *q,int e){/*入队操作*/
if((q->rear+1)%M==q->front){printf("The que is overflow!\n"); return 0;}else{q->V[q->rear]=e;
q->rear=(q->rear+1)%M;
return 1;}}
Deque(Que *q){/*出队操作*/
int t;
if(q->front==q->rear){printf("The que is empty!\n");
return 0;}else{t=q->V[q->front];
q->front=(q->front+1)%M;
return t;}}
void BFSTraverse(Graph *g){/*广度遍历*/
int i;
Que *q=(Que *)malloc(sizeof(Que));
for(i=1;i<=g->vexnum;i++){visited[i]=0;}Initque(q); for(i=1;i<=g->vexnum;i++){if(!visited[i]){visited[i]=1; visitvex(g,g->V[i]);
Enque(q,g->V[i]);
while(!Quempty(q)){int u,w;
u=Deque(q);
for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w)){ if(!visited[w]){visited[w]=1;
visitvex(g,w);
Enque(q,w);}}}}}}
int main()/*主程序*/{int n;
Graph *g=(Graph *)malloc(sizeof(Graph));
char menu;
printf("Please input the number of vertex:
\n");
scanf("%d",&n);
creatgraph(g,n);
printf("This is the linjiejuzhen of graph:
\n");
printgraph(g);
input:
printf("PleaseinputBorDorQ,Breadth_first:
B Depth_first:
Dquit:
Q\n");
while((menu=getchar())=='\n');
if(menu=='B'){printf("Breadth_first:
\n");
BFSTraverse(g);
printf("\n");
goto input;}else if(menu=='D'){printf("Depth_first:
\n");
DFSTraverse(g);
printf("\n");
goto input;}else if(menu=='Q'){exit
(0);}else{printf("Input error!Please input B or D!\n");}return 0;}。