有向图的邻接表存储，递归和非递归的深度、广度遍历（codeblocks+gcc）



有向图的邻接表存储，递归和非递归的深度、广度遍历（codeblocks+gcc。

程序功能:

1. 图的邻接表存储

2. 递归深度遍历

3. 非递归深度遍历（借助stack）

4. 递归广度遍历

5. 非递归广度遍历（借助queue）

 

程序中通过条件编译实现，递归与非递归的选择

  1. //#define _RECURSION_TRAVERSE                                              //递归遍历(将下一行注释，此行不注释)
  2. #define _NON_RECURSION_TRAVERSE                                       //非递归遍历(节点本身有isVisited域)(将上一行注释，此行不注释)

 

注释第一行，保留第二行：实现非递归遍历

注释第二行，保留第一行：实现递归遍历

两行都注释或都不注释：出错（无此函数/函数重名）

 

程序所用图的结构

程序源代码

  1. /*****************************************************************
  2. *功  能：利用邻接表存储图，实现其递归与非递归的深度遍历和广度遍历
  3. *作  者：JarvisChu
  4. *时  间：2011-04-30
  5. *****************************************************************/
  6. #include <iostream>
  7. #include <string>
  8. #include <stack>
  9. #include <queue>
  11. using namespace std;
  13. //#define _RECURSION_TRAVERSE                                              //递归遍历(将下一行注释，此行不注释)
  14. #define _NON_RECURSION_TRAVERSE                                       //非递归遍历(节点本身有isVisited域)(将上一行注释，此行不注释)
  16. #define MAX_VERTEX_NUM 20                                                   //最大顶点数
  19. /*弧节点的结构，即每个顶点后面的单链表中的节点结构*/
  20. typedef struct ArcNode{
  21.     int adjvex;                                                                                //该弧所指向的顶点的位置
  22.     struct ArcNode* nextArc;                                                        //下一条弧
  23.     string info;                                                                               //该弧所携带的信息
  24. }ArcNode;
  26. #ifdef  _NON_RECURSION_TRAVERSE
  27. /*每个顶点的节点结构,非递归时使用*/
  28. typedef struct VNode{
  29.     bool isVisited;
  30.     string data;                                                                               //顶点的数据
  31.     ArcNode* fristArc;                                                                    //指向该顶点所接的单链表的第一个弧节点
  32. }VNode,AdjList[MAX_VERTEX_NUM];
  33. #endif
  35. #ifdef  _RECURSION_TRAVERSE
  36. /*每个顶点的节点结构，递归时使用*/
  37. typedef struct VNode{
  38.     string data;                                                                               //顶点的数据
  39.     ArcNode* fristArc;                                                                    //指向该顶点所接的单链表的第一个弧节点
  40. }VNode,AdjList[MAX_VERTEX_NUM];
  41. #endif
  43. /*图的结构*/
  44. typedef struct{
  45.     AdjList vertices;                                                                        //顶点数组
  46.     int vexNum;                                                                             //顶点数
  47.     int arcNum;                                                                              //弧数
  48.     int kind;                                                                                    //种类
  49. }Graph;
  51. /*初始化有向图*/
  52. bool InitDiGraph(Graph* pGraph){
  53.     pGraph->kind = 0;                                                                   //有向图
  54.     pGraph->vexNum = 5;
  55.     pGraph->arcNum = 5;
  57.     pGraph->vertices[0].data = “V0″;                                             //顶点V0的邻接表
  58. #ifdef _NON_RECURSION_TRAVERSE
  59.     pGraph->vertices[0].isVisited = false;
  60. #endif
  61.     ArcNode* node = new ArcNode();
  62.     node->adjvex = 1;
  63.     node->info = “V0–>V1″;
  64.     node->nextArc = NULL;
  65.     ArcNode* node1 = new ArcNode();
  66.     node1->adjvex = 2;
  67.     node1->info = “V0–>V2″;
  68.     node1->nextArc = NULL;
  69.     node->nextArc = node1;
  70.     pGraph->vertices[0].fristArc = node;
  72.     pGraph->vertices[1].data = “V1″;                                             //顶点V1的邻接表
  73. #ifdef _NON_RECURSION_TRAVERSE
  74.     pGraph->vertices[1].isVisited = false;
  75. #endif
  76.     pGraph->vertices[1].fristArc = NULL;
  78.     pGraph->vertices[2].data = “V2″;                                             //顶点V2的邻接表
  79. #ifdef _NON_RECURSION_TRAVERSE
  80.     pGraph->vertices[2].isVisited = false;
  81. #endif
  82.     node = new ArcNode();
  83.     node->adjvex = 3;
  84.     node->info = “V2–>V3″;
  85.     node->nextArc = NULL;
  86.     pGraph->vertices[2].fristArc = node;
  88.     pGraph->vertices[3].data = “V3″;                                             //顶点V3的邻接表
  89. #ifdef _NON_RECURSION_TRAVERSE
  90.     pGraph->vertices[3].isVisited = false;
  91. #endif
  92.     node = new ArcNode();
  93.     node->adjvex = 0;
  94.     node->info = “V3–>V0″;
  95.     node->nextArc = NULL;
  96.     node1 = new ArcNode();
  97.     node1->adjvex = 4;
  98.     node1->info = “V3–>V4″;
  99.     node1->nextArc = NULL;
  100.     node->nextArc = node1;
  101.     pGraph->vertices[3].fristArc = node;
  103.     pGraph->vertices[4].data = “V4″;                                             //顶点V4的邻接表
  104. #ifdef _NON_RECURSION_TRAVERSE
  105.     pGraph->vertices[4].isVisited = false;
  106. #endif
  107.     pGraph->vertices[4].fristArc = NULL;
  109.     return true;
  110. }
  112. /*显示有向图*/
  113. bool DisplayDiGraph(Graph diGraph){
  114.     cout<<”*******************图信息********************”<<endl;
  115.     cout<<”图种类为：”<<diGraph.kind<<endl;
  116.     cout<<”顶点数为：”<<diGraph.vexNum<<endl;
  117.     cout<<”弧数为：”<<diGraph.arcNum<<endl<<endl;
  118.     cout<<”邻接表结构如下”<<endl;
  119.     ArcNode* node = NULL;
  120.     for(int i=0;i<diGraph.vexNum;i++){
  121.         cout<<diGraph.vertices[i].data<<”:”;
  122.         node = diGraph.vertices[i].fristArc;
  123.         while(node != NULL){
  124.             cout<<”(“<<node->adjvex<<”,”<<node->info<<”) ; “;
  125.             node = node->nextArc;
  126.         }
  127.         cout<<endl;
  128.     }
  129.     return true;
  130. }
  132. #ifdef _NON_RECURSION_TRAVERSE
  133. /*深度优先非递归遍历有向图,利用栈*/
  134. bool Depth_First_Traverse(Graph* pDiGraph){
  135.     for(int i=0;i<pDiGraph->vexNum;i++){                  //初始化，全为false
  136.         pDiGraph->vertices[i].isVisited = false;
  137.     }
  138.     VNode* vnode;
  139.     stack<VNode*> TraverseStack;                                                 //用stack实现非递归遍历算法
  140.     TraverseStack.push(&(pDiGraph->vertices[0]));                                   //第一个节点入栈
  142.     while(!TraverseStack.empty()){
  143.         vnode = (VNode*)TraverseStack.top();                                                //获得栈顶节点
  144.         vnode->isVisited = true;
  145.         cout<<”遍历：”<<vnode->data<<endl;
  146.         TraverseStack.pop();
  147.         ArcNode* node = vnode->fristArc;
  148.         while(node != NULL){
  149.             if(!(pDiGraph->vertices[node->adjvex]).isVisited){
  150.                 TraverseStack.push(&(pDiGraph->vertices[node->adjvex]));        //入栈
  151.             }
  152.             node = node->nextArc;
  153.         }
  154.     }
  155.     return true;
  156. }
  157. #endif
  159. #ifdef _RECURSION_TRAVERSE
  160. /*深度优先递归遍历时，用来遍历每一个顶点*/
  161. bool DFT(Graph* pDiGraph,bool* visited,int i){
  162.     if(!visited[i]){
  163.         visited[i] = true;                                                 //标志该顶点已被访问了
  164.         cout<<”遍历：”<<pDiGraph->vertices[i].data<<endl;
  165.         ArcNode* node = pDiGraph->vertices[i].fristArc;//遍历其临街单链表
  166.         while(node != NULL){
  167.             DFT(pDiGraph,visited,node->adjvex);
  168.             node = node->nextArc;
  169.         }
  170.     }
  171.     return true;
  172. }
  174. /*深度优先递归遍历有向图*/
  175. bool Depth_First_Traverse(Graph* pDiGraph){
  176.     int size = pDiGraph->vexNum;                           //顶点数目
  177.     bool* visited = new bool[size];                          //访问标志数组
  178.     for(int i = 0;i < size;i++){                                    //初始化，全为false
  179.         visited[i] = false;
  180.     }
  181.     for(int i = 0;i<size;i++){                                      //
  182.             DFT(pDiGraph,visited,i);
  183.     }
  184.     delete[] visited;
  185.     return true;
  186. }
  187. #endif
  189. #ifdef _NON_RECURSION_TRAVERSE
  190. /*广度优先非递归遍历有向图，利用队列*/
  191. bool Breadth_First_Traverse(Graph* pDiGraph){
  192.     for(int i=0;i<pDiGraph->vexNum;i++){                  //初始化，全为false
  193.         pDiGraph->vertices[i].isVisited = false;
  194.     }
  195.     VNode* vnode;
  196.     queue<VNode*> TraverseQueue;                                                 //用queue实现非递归遍历算法
  197.     TraverseQueue.push(&(pDiGraph->vertices[0]));                           //第一个节点入队
  199.     while(!TraverseQueue.empty()){
  200.         vnode = (VNode*)TraverseQueue.front();                                  //获得队首节点
  201.         vnode->isVisited = true;
  202.         cout<<”遍历：”<<vnode->data<<endl;
  203.         TraverseQueue.pop();
  204.         ArcNode* node = vnode->fristArc;
  205.         while(node != NULL){
  206.             if(!(pDiGraph->vertices[node->adjvex]).isVisited){
  207.                 TraverseQueue.push(&(pDiGraph->vertices[node->adjvex]));        //入队
  208.             }
  209.             node = node->nextArc;
  210.         }
  211.     }
  212.     return true;
  213. }
  214. #endif
  216. #ifdef _RECURSION_TRAVERSE
  217. /*广度优先递归遍历时，用来遍历每一个顶点*/
  218. bool BFT(Graph* pDiGraph,bool* visited,int i){
  219.     if(!visited[i]){
  220.         visited[i] = true;                                                 //标志该顶点已被访问了
  221.         cout<<”遍历：”<<pDiGraph->vertices[i].data<<endl;
  222.         ArcNode* node = pDiGraph->vertices[i].fristArc;//遍历其临街单链表
  223.         while(node != NULL){
  224.             if(!pDiGraph->vertices[node->adjvex].isVisited){
  225.                 pDiGraph->vertices[node->adjvex].isVisited = true;
  226.                 cout<<”遍历：”<<pDiGraph->vertices[node->adjvex].data<<endl;
  227.             }
  228.             node = node->nextArc;
  229. //       BFT(pDiGraph,visited,node->adjvex);
  230.         }
  231.         BFT(pDiGraph,visited,node->adjvex);
  232.     }
  233.     return true;
  234. }
  235. /*广度优先递归遍历有向图*/
  236. bool Breadth_First_Traverse(Graph* pDiGraph){
  237.     int size = pDiGraph->vexNum;                           //顶点数目
  238.     bool* visited = new bool[size];                          //访问标志数组
  239.     for(int i = 0;i < size;i++){                                    //初始化，全为false
  240.         visited[i] = false;
  241.     }
  242.     for(int i = 0;i<size;i++){                                      //
  243.             BFT(pDiGraph,visited,i);
  244.     }
  245.     delete[] visited;
  246. }
  247. #endif
  251. int main()
  252. {
  253.     Graph diGraph;                                                                         //有向图
  254.     Graph udiGraph;                                                                       //无向图
  256.     InitDiGraph(&diGraph);                                                             //初始化有向图，构建
  258.     DisplayDiGraph(diGraph);                                                         //显示该有向图
  260.     cout<<endl<<”***************深度优先遍历结果***********”<<endl;
  261.     Depth_First_Traverse(&diGraph);                                           //深度优先遍历
  263.     cout<<endl<<”***************广度优先遍历结果***********”<<endl;
  264.     Breadth_First_Traverse(&diGraph);                                           //广度优先遍历
  267.     return 0;
  268. }

 

 

程序运行结果

0 表示有向图