图的存储结构

    本文的重点在于图的深度优先搜索（DFS）和广度优先搜索（BFS），因此不再对图的基本概念做过多的介绍，但是要先大致了解下图的几种常见的存储结构。

    邻接矩阵

    邻接矩阵既可以用来存储无向图，也可以用来存储有向图。该结构实际上就是用一个二维数组（邻接矩阵）来存储顶点的信息和顶点之间的关系（有向图的弧或无向图的边）。其描述形式如下：

[cpp] view plaincopy

1. //图的邻接矩阵存储表示  
2. #define MAX_NUM 20 // 最大顶点个数  
3. enum GraphKind{GY,GN}; // {有向图,无向图}  
4. typedef struct  
5. {  
6.    VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示是否相邻；对带权图，则为权值  
7.    InfoType *info; // 与该弧或边相关信息的指针(可无)  
8. }ArcCell,AdjMatrix[MAX_NUM][MAX_NUM]; // 二维数组  
9. typedef struct  
10. {  
11.    VertexType vexs[MAX_NUM]; // 顶点向量  
12.    AdjMatrix arcs; // 邻接矩阵  
13.    int vexnum,arcnum; // 图的当前顶点数和弧（边）数  
14.    GraphKind kind; // 图的种类标志  
15. }Graph;  

[cpp] view plaincopy

1. //图的邻接表存储表示  
2. #define MAX_NUM 20  
3. enum GraphKind{GY,GN}; // {有向图,无向图}  
4. typedef struct   
5. {  
6.    int adjvex; // 该弧所指向的顶点或边的另一个顶点的位置  
7.    ArcNode *nextarc; // 指向下一条弧或边的指针  
8.    InfoType *info; // 与弧或边相关信息的指针（可无）  
9. }ArcNode;// 表结点  
10. typedef struct  
11. {  
12.    VertexType data; // 顶点信息  
13.    ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧或边的指针  
14. }VNode,AdjList[MAX_NUM]; // 头结点  
15. struct   
16. {  
17.    AdjList vertices;  
18.    int vexnum,arcnum; // 图的当前顶点数和弧（边）数  
19.    GraphKind kind; // 图的种类标志  
20. }Graph;  

[cpp] view plaincopy

1. //有向图的十字链表存储表示  
2. #define MAX_NUM 20  
3. typedef struct // 弧结点  
4. {  
5.   int tailvex,headvex; // 该弧的尾和头顶点的位置  
6.   ArcBox *hlink,*tlink; // 分别为弧头相同和弧尾相同的弧的链域  
7.   InfoType *info; // 该弧相关信息的指针，可指向权值或其他信息（可无）  
8. }ArcBox;  
9. typedef struct // 顶点结点  
10. {  
11.   VertexType data;  
12.   ArcBox *firstin,*firstout; // 分别指向该顶点第一条入弧和出弧  
13. }VexNode;  
14. struct  
15. {  
16.   VexNode xlist[MAX_NUM]; // 表头向量(数组)  
17.   int vexnum,arcnum; // 有向图的当前顶点数和弧数  
18. }Graph;      

[cpp] view plaincopy

1. //无向图的邻接多重表存储表示  
2.  #define MAX_NUM 20  
3.  typedef struct   
4.  {  
5.    VisitIf mark; // 访问标记  
6.    int ivex,jvex; // 该边依附的两个顶点的位置  
7.    EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边  
8.    InfoType *info; // 该边信息指针，可指向权值或其他信息  
9.  }EBox;  
10.  typedef struct  
11.  {  
12.    VertexType data;  
13.    EBox *firstedge; // 指向第一条依附该顶点的边  
14.  }VexBox;  
15.  typedef struct   
16.  {  
17.    VexBox adjmulist[MAX_NUM];  
18.    int vexnum,edgenum; // 无向图的当前顶点数和边数  
19.  }Graph;  

图的遍历

    图的遍历比树的遍历要复杂的多，因为图的任一顶点都有可能与其他的顶点相邻接，因此，我们需要设置一个辅助数组visited[]来标记某个节点是否已经被访问过。图的遍历通常有两种方法：深度优先遍历（BFS）和广度优先遍历（DFS），两种遍历方式的思想都不难理解。下面我们就以如下图所示的例子来说明图的这两种遍历方式的基本思想，并用邻接表作为图的存储结构，给出BFS和DFS的实现代码（下图为无向图，有向图的BFS和DFS实现代码与无向图的相同）：

    我们以邻接表作为上图的存储结构，并将A、B、C、D、E、F、G、H在顶点数组中的序号分别设为0、1、2、3、4、5、6、7。我们根据上图所包含的信息，精简了邻接表的存储结构，采取如下所示的结构来存储图中顶点和边的相关信息：

[cpp] view plaincopy

1. #define NUM 8          //图中顶点的个数  
2.   
3. /* 
4. 用邻接表作为图的存储结构 
5. 在邻接表中，用一个一维数组存储图中的每个顶点的信息， 
6. 同时为每个顶点建立一个单链表，链表中的节点保存依附在该顶点上的边或弧的信息 
7. */  
8. typedef struct node  
9. {   //链表中的每个节点，保存依附在该节点上的边或弧的信息  
10.     int vertex;          //在有向图中表示该弧所指向的顶点（即弧头）的位置，  
11.                          //在无向图中表示依附在该边上的另一个顶点的位置  
12.     struct node *pNext;  //指向下一条依附在该顶点上的弧或边  
13. }Node;  
14. typedef struct head  
15. {   //数组中的每个元素，保存图中每个顶点的相关信息  
16.     char data;          //顶点的数据域  
17.     Node *first;        //在有向图中，指向以该顶点为弧尾的第一条弧  
18.                         //在无向图中，指向依附在该顶点上的第一条边  
19. }Head,*Graph;           //动态分配数组保存每个顶点的相关信息  

    那么用邻接表来表示上图中各顶点间的关系，如下图所示：

    深度优先搜索

    结合上面的例子来分析，假设从A点开始遍历该图，根据图中顶点的存储关系，会按照下面的步骤来遍历该图：

    1、在访问完顶点A后，选择A的第一个邻接点B进行访问；

    2、而后看B的邻接点，由于B的第一个邻接点A已经被访问过，故选择其下一个邻接点D进行访问；

    3、而后看D的邻接点，由于D的第一个邻接点B已经被访问过，故选择其下一个邻接点H进行访问；

    4、而后看H的邻接点，由于H的第一个邻接点D已经被访问过，故选择其下一个邻接点E进行访问；

    5、而后看E的邻接点，由于E的第一个邻接点B已经被访问过，那么看其第二个邻接点H，也被访问过了，E的邻接点已经全部被访问过了。

    6、这时退回到上一层递归，回到顶点H，同样H的邻接点也都被访问完毕，再退回到D，D的邻接点也已访问完毕，再退回到B，一直退回到A；

    7、由于A的下一个邻接点C还没有被访问，因此访问C；

    8、而后看C的邻接点，由于C的第一个邻接点A已经被访问过，故选择其下一个邻接点F进行访问；

    9、而后看F的邻接点，由于F的第一个邻接点C已经被访问过，故选择其下一个邻接点G进行访问；

    10、而后看G的邻接点，由于G的临界点都已被访问完毕，因此会退到上一层递归，看F顶点；

    11、同理，由F再回退到C，再由C回退到A，这是第一层的递归，A的所有邻接点也已都被访问完毕，遍历到此结束。