习题2-连通图上实现深度优先遍历.c

数据结构各章实验源代码； 数据结构实验源代码

#include  <stdio.h>
#include  "datastru.h"
#include  <malloc.h>

int  visited[MAXLEN];

ADJGRAPH creat_adjgraph()
{
   EDGENODE  *p;
   int  i, s, d;
   ADJGRAPH  adjg;

adjg.kind = 2;
printf("\n\n输入顶点数和边数(用逗号隔开) : ");
scanf("%d,%d", &s, &d);fflush(stdin);
adjg.vexnum = s;                                /*存放顶点数在adjg.vexnum中 */
adjg.arcnum = d;                                /*存放边点数在adjg.arcnum中*/
printf("\n\n");
for(i = 0; i < adjg.vexnum; i++)                /*输入顶点的值*/
  {printf("输入顶点 %d 的值 : ", i + 1);
   scanf("%d", &adjg.adjlist[i].vertex);   
   fflush(stdin);
   adjg.adjlist[i].link = NULL;}
   printf("\n");
for(i = 0; i < adjg.arcnum; i++)
  {printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ", i+1);
   scanf("%d,%d", &s, &d);                      /*输入边的起始顶点和终止顶点*/
   fflush(stdin);
   while(s < 1 || s > adjg.vexnum || d < 1 || d > adjg.vexnum)
      { printf("输入错，重新输入: ");
        scanf("%d,%d", &s, &d);	}
   s --;
   d --;
   p = malloc(sizeof(EDGENODE));                /*建立一个和边相关的结点*/
   p->adjvex = d;
   p->next = adjg.adjlist[s].link;              /*挂到对应的单链表上*/
   adjg.adjlist[s].link = p;
   p = malloc(sizeof(EDGENODE));                /*建立另一个和边相关的结点*/
   p->adjvex = s;
   p->next = adjg.adjlist[d].link;              /*挂到对应的单链表上*/
   adjg.adjlist[d].link = p;}
return adjg;
}

void dfs(ADJGRAPH adjg, int v){
/*连通图的深度遍历算法：从v顶点出发*/
EDGENODE *p;

visited[v - 1] = 1;                       /*从编号为v的顶点出发，visited数组对应置1*/
v --;
printf("  %d", adjg.adjlist[v].vertex);   /*输出v顶点*/
p = adjg.adjlist[v].link;                 /*取单链表的第一个结点*/
while(p != NULL)                          /*对应单链表不空，进行遍历*/
   { if(visited[p->adjvex] == 0)          /*如果有未被访问过的结点*/
	  dfs(adjg, (p->adjvex)+1);       /*递归调用深度遍历算法*/
     p = p->next;}                        /*取单链表的下一个结点*/
}

main()
{
   ADJGRAPH ag;
   int  i;
   printf("\n连通图的深度遍历\n");
   ag = creat_adjgraph();                  /*建立连通图的邻接链表结构*/
   for(i = 0; i < ag.vexnum; i++)          /*visited数组初始化，均置0*/
     visited[i] = 0;
   printf("\n\n输入深度遍历起始顶点(1 -- %d) : ",ag.vexnum);
   scanf("%d",&i);
   printf("\n\n深度遍结果序列 :  ");
   dfs(ag,i);                              /*连通图的深度遍历算法*/
   printf("\n\n");
}