深度优先遍历

基本思想

  • 从图G中某个顶点vi出发，访问vi，然后选择一个与vi相邻且没有被访问过的顶点v访问，再从v出发选择一个与v相邻且未被访问的顶点vj访问，依次访问。

  • 如果当前已被访问的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点w，从w出发按相同的方法继续遍历，直到所有的顶点都被访问到。

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <string.h>
  5. #define MAXVEX 100
  7. typedef char VertexType[3];        /*定义VertexType为char数组类型*/
  9. typedef struct vertex
  10. {    
  11.     int adjvex;                     /*顶点编号*/
  12.     VertexType data;             /*顶点的信息*/
  13. } VType;                        /*顶点类型*/
  15. typedef struct graph
  16. {    
  17.     int n,e;                    /*n为实际顶点数,e为实际边数*/
  18.     VType vexs[MAXVEX];            /*顶点集合*/
  19.     int edges[MAXVEX][MAXVEX];    /*边的集合*/
  20. } AdjMatix;                        /*图的邻接矩阵类型*/
  22. typedef struct edgenode
  23. {    
  24.     int adjvex;                  /*邻接点序号*/
  25.     int value;                  /*边的权值*/
  26.     struct edgenode *next;        /*下一条边的顶点*/
  27. } ArcNode;                        /*每个顶点建立的单链表中结点的类型*/
  29. typedef struct vexnode
  30. {
  31.     VertexType data;               /*结点信息*/
  32.     ArcNode *firstarc;             /*指向第一条边结点*/
  33. } VHeadNode;                    /*单链表的头结点类型*/
  35. typedef struct 
  36. {
  37.     int n,e;                    /*n为实际顶点数,e为实际边数*/
  38.     VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
  39. } AdjList;                         /*图的邻接表类型*/
  41. void DispAdjList(AdjList *G)
  42. {
  43.     int i;
  44.     ArcNode *p;
  45.     printf("图的邻接表表示如下:\n");
  46.     for (i=0;i<G->n;i++)
  47.     {    
  48.         printf("  [%d,%3s]=>",i,G->adjlist[i].data);
  49.         p=G->adjlist[i].firstarc;
  50.         while (p!=NULL)
  51.         {    
  52.             printf("(%d,%d)->",p->adjvex,p->value);
  53.             p=p->next;
  54.         }
  55.         printf("∧\n");
  56.     }
  57. }
  59. void MatToList(AdjMatix g,AdjList *&G)  /*例6.3算法:将邻接矩阵g转换成邻接表G*/
  60. {
  61.     int i,j;
  62.     ArcNode *p;
  63.     G=(AdjList *)malloc(sizeof(AdjList));
  64.     for (i=0;i<g.n;i++)                    /*给邻接表中所有头结点的指针域置初值*/
  65.     {    
  66.         G->adjlist[i].firstarc=NULL;
  67.         strcpy(G->adjlist[i].data,g.vexs[i].data);
  68.     }
  69.     for (i=0;i<g.n;i++)                    /*检查邻接矩阵中每个元素*/
  70.         for (j=g.n-1;j>=0;j--)
  71.             if (g.edges[i][j]!=0)        /*邻接矩阵的当前元素不为0*/
  72.             {
  73.                 p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
  74.                 p->value=g.edges[i][j];p->adjvex=j;
  75.                 p->next=G->adjlist[i].firstarc;          /*将*p链到链表后*/
  76.                 G->adjlist[i].firstarc=p;
  77.             }
  78.     G->n=g.n;G->e=g.e;
  79. }
  81. int visited[MAXVEX];
  82. void DFS(AdjList *g,int vi)        /*对邻接表G从顶点vi开始进行深度优先遍历*/
  83. {
  84.     ArcNode *p;
  85.     printf("%d ",vi);            /*访问vi顶点*/
  86.     visited[vi]=1;                /*置已访问标识*/
  87.     p=g->adjlist[vi].firstarc;    /*找vi的第一个邻接点*/
  88.     while (p!=NULL)                /*找vi的所有邻接点*/
  89.     {
  90.         if (visited[p->adjvex]==0) 
  91.             DFS(g,p->adjvex);    /*从vi未访问过的邻接点出发深度优先搜索*/
  92.         p=p->next;                /*找vi的下一个邻接点*/
  93.     }
  94. }
  96. void DFS1(AdjList *G,int vi)        /*非递归深度优先遍历算法*/
  97. {
  98.     ArcNode *p;
  99.     ArcNode *St[MAXVEX];
  100.     int top=-1,v;
  101.     printf("%d ",vi);                    /*访问vi顶点*/
  102.     visited[vi]=1;                        /*置已访问标识*/
  103.     top++;                                /*将初始顶点vi的firstarc指针进栈*/
  104.     St[top]=G->adjlist[vi].firstarc;
  105.     while (top>-1)                        /*栈不空循环*/
  106.     {
  107.         p=St[top];top--;                /*出栈一个顶点为当前顶点*/
  108.         while (p!=NULL)                    /*循环搜索其相邻顶点*/
  109.         {
  110.             v=p->adjvex;                /*取相邻顶点的编号*/
  111.             if (visited[v]==0)            /*若该顶点未访问过*/
  112.             {                            
  113.                 printf("%d ",v);        /*访问v顶点*/
  114.                 visited[v]=1;            /*置访问标识*/
  115.                 top++;                    /*将该顶点的第1个相邻顶点进栈*/
  116.                 St[top]=G->adjlist[v].firstarc;
  117.                 break;                    /*退出当前顶点的搜索*/
  118.             }        
  119.             p=p->next;                    /*找下一个相邻顶点*/
  120.         }
  121.     }
  122. }
  124. void main()
  125. {
  126.     int i,j;
  127.     AdjMatix g;
  128.     AdjList *G;
  129.     int a[5][5]={ {0,1,0,1,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1},{0,0,1,1,0} };
  130.     char *vname[MAXVEX]={"a","b","c","d","e"};
  131.     g.n=5;g.e=12;    /*建立图6.1(a)的无向图,每1条无向边算为2条有向边*/
  132.     for (i=0;i<g.n;i++)
  133.         strcpy(g.vexs[i].data,vname[i]);
  134.     for (i=0;i<g.n;i++)
  135.         for (j=0;j<g.n;j++)
  136.             g.edges[i][j]=a[i][j];
  137.     MatToList(g,G);        /*生成邻接表*/
  138.     DispAdjList(G);        /*输出邻接表*/
  139.     for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
  140.     printf("从顶点0的深度优先遍历序列:\n");
  141.     printf("  递归算法:");DFS(G,0);printf("\n");
  142.     for (i=0;i<g.n;i++)    visited[i]=0; /*顶点标识置初值*/
  143.     printf("  非递归算法:");DFS1(G,0);printf("\n");
  144. }