C语言课程设计报告_图的遍历的演示 第2页
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;
}Queue;
/*初始化队列*/
initqueue(Queue *q)
{
q->front=0;
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);
}
}
}
}
}
}
/*主程序*/
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("Please input b or d or q ,Breadth_first: b Depth_first: d quit: q\n");
while((menu=getchar())=='\n');
if(menu=='b')
{
printf("Breadth_first:\n");
BESTraverse(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");
}
}