tu-table-dfs.cpp

本程序采用深度优先的方法完成图的遍历

#include <stdlib.h>
#include <stdio.h>
struct node                       /* 图形顶点结构定义    */
{
   int vertex;                    /* 顶点            */
   struct node *nextnode;         /* 指下一顶点的指针    */
};
typedef struct node *graph;       /* 图形的结构重定义    */
struct node head[6];              /* 图形顶点结构数组    */
bool visited[6];   // 访问标志数组

/*----------建立图形--------*/
void creategraph(int *node,int num)
{
   graph newnode;                 /* 新顶点指针          */
   graph ptr;
   int from;                      /* 边线的起点          */
   int to;                        /* 边线的终点          */
   int i;
   for ( i = 0; i < num; i++ )         /* 读取边线的回路      */
   {
      from = node[i*2];           /* 边线的起点          */
      to = node[i*2+1];           /* 边线的终点          */
      /* 申请存储新顶点的内存空间 */
      newnode = ( graph ) malloc(sizeof(struct node));
      newnode->vertex = to;       /* 建立顶点内容        */
      newnode->nextnode = NULL;   /* 设定指针初值        */
      ptr = &(head[from]);        /* 顶点位置            */
      while ( ptr->nextnode != NULL ) /* 遍历至链表尾    */
         ptr = ptr->nextnode;     /* 下一个顶点          */
      ptr->nextnode = newnode;    /* 插入结尾            */
   }
}
/*------------深度遍历------------*/
void DFS(node *head, int v) {  // 算法7.5
   // 从第v个顶点出发递归地深度优先遍历图G。
   int w;
   graph p;
   visited[v] = true;
   printf(" %d ",head[v].vertex);  // 访问第v个顶点
   
   for (p=head[v].nextnode;  p!=NULL;  p=p->nextnode){
	   w=p->vertex;
       if (!visited[w])  DFS(head, w);     // 对v的尚未访问的邻接顶点w递归调用DFS
   }
}

void DFSTraverse(node *head) {  // 算法7.4
 // 对图G作深度优先遍历。
 int v;
 for (v=0; v<6; ++v) visited[v] = false; // 访问标志数组初始化
 for (v=0; v<6; ++v) 
   if (!visited[v]) DFS(head, v);         // 对尚未访问的顶点调用DFS
}

/*------主程序: 建立图形后,将邻接链表输出------*/
void main()
{
   graph ptr;
   int node[12][2] = { {0, 2}, {2, 0},   /* 边线数组     */
                       {1, 4}, {4, 1},
                       {1, 5}, {5, 1},
                       {3, 4}, {4, 3},
                       {3, 5}, {5, 3},
                       {4, 5}, {5, 4}   };
   int i;
   for ( i = 0; i <= 5; i++ )
   {
      head[i].vertex = i;           /* 设定顶点值          */
      head[i].nextnode = NULL;    /* 清除图形指针         */
   }
   creategraph(*node,12);          /* 建立图形            */
   printf("图形的邻接链表内容:\n");
   for ( i = 0; i <= 5; i++ )
   {
      printf("顶点%d =>",head[i].vertex);/* 顶点值       */
      ptr = head[i].nextnode;             /* 顶点位置     */
      while ( ptr != NULL )              /* 遍历至链表尾 */
      {
         printf(" %d ",ptr->vertex);      /* 输出顶点内容 */
         ptr = ptr->nextnode;            /* 下一个顶点   */
      }
      printf("\n");                      /* 换行         */
   }
   DFSTraverse(head);
}