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;

             

    上面两个图均为无权图，我们假设存储的时候，V0的序号为0，V1的序号为1，V2的序号为2。。。，且adj为1表示两顶点间没有没有连接，为0时表示有连接。则有向图的邻接矩阵如下图左边的矩阵所示，无向图的邻接矩阵如下图右边的矩阵所示；

 
       

    根据邻接矩阵很容易判断图中任意两个顶点之间连通与否，并可以求出各个顶点的度。

    1、对于无向图，观察右边的矩阵，发现顶点Vi的度即是邻接矩阵中第i行（或第i列）的元素之和。

    2、对于有向图，由于需要分别计算出度和入读，观察左边的矩阵，发现顶点Vi的出度即为邻接矩阵第i行元素之和，入度即为邻接矩阵第i列元素之和，因此顶点Vi的度即为邻接矩阵中第i行元素和第i列元素之和。

    很明显，邻接矩阵所占用的存储空间与图的边数或弧数无关，因此适用于边数或弧数较多的稠密图。

邻接表

邻接表是图的一种链式存储结构，既适合于存储无向图，也适合于存储有向图。在邻接表中，用一个一维数组存储图中的每个顶点的信息，同时为每个顶点建立一个单链表，链表中的节点保存依附在该顶点上的边或弧的信息。其描述形式如下：

    依然以上面的有向图和无向图为例，采用邻接表来存储，可以得到对应的存储形式如下：

    在邻接表上容易找到任意一个顶点的第一个邻接点和下一个邻接点，但是要判定任意两个顶点之间是否有边或弧需搜索两个顶点对应的链表，不及邻接矩阵方便。

    很明显，邻接表所占用的存储空间与图的边数或弧数有关，因此适用于边数或弧数较少的稀疏图。

十字链表

十字链表也是一种链式存储结构，用来表示有向图，它在有向图邻接表的基础上加入了指向弧尾的指针。表示形式如下：

    其思想也很容易理解，这里不再细说。

    在十字链表中，既容易找到以某个顶点为尾的弧，也容易找到以某个顶点为头的弧，因而容易求得顶点的出度和入度。

邻接多重表

邻接多重表也是一种链式存储结构，用来表示无向图，与有向图的十字链表相似，这里也不再细说，直接给出其表示形式：

图的遍历

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

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

1. /*
2. 从序号为begin的顶点出发，递归深度优先遍历连通图Gp
3. */
4. void DFS(Graph Gp, int begin)
5. {
6. //遍历输出序号为begin的顶点的数据域，并保存遍历信息
7. printf("%c ",Gp[begin].data);
8. visited[begin] = true;
9. //循环访问当前节点的所有邻接点（即该节点对应的链表）
10. int i;
11. for(i=first_vertex(Gp,begin); i>=0; i=next_vertex(Gp,begin,i))
12. {
13. if(!visited[i])  //对于尚未遍历的邻接节点，递归调用DFS
14. DFS(Gp,i);
15. }
16. }
17. /*
18. 从序号为begin的节点开始深度优先遍历图Gp，Gp可以是连通图也可以是非连通图
19. */
20. void DFS_traverse(Graph Gp,int begin)
21. {
22. int i;
23. for(i=0;i<NUM;i++)    //初始化遍历标志数组
24. visited[i] = false;
25. //先从序号为begin的顶点开始遍历对应的连通图
26. DFS(Gp,begin);
27. //如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到
28. for(i=0;i<NUM;i++)
29. {
30. if(!visited[i])
31. DFS(Gp,i);
32. }
33. }

1. /*
2. 返回图Gp中pos顶点（序号为pos的顶点）的第一个邻接顶点的序号，如果不存在，则返回-1
3. */
4. int first_vertex(Graph Gp,int pos)
5. {
6. if(Gp[pos].first)  //如果存在邻接顶点，返回第一个邻接顶点的序号
7. return  Gp[pos].first->vertex;
8. else              //如果不存在，则返回-1
9. return -1;
10. }
11. /*
12. cur顶点是pos顶点（cur和pos均为顶点的序号）的其中一个邻接顶点，
13. 返回图Gp中，pos顶点的（相对于cur顶点）下一个邻接顶点的序号,如果不存在，则返回-1
14. */
15. int next_vertex(Graph Gp,int pos,int cur)
16. {
17. Node *p = Gp[pos].first; //p初始指向顶点的第一个邻接点
18. //循环pos节点对应的链表，直到p指向序号为cur的邻接点
19. while(p->vertex != cur)
20. p = p->pNext;
21. //返回下一个节点的序号
22. if(p->pNext)
23. return p->pNext->vertex;
24. else
25. return -1;
26. }

1. /*
2. 从序号为begin的顶点开始，广度优先遍历图Gp，Gp可以是连通图也可以是非连通图
3. */
4. void BFS_traverse(Graph Gp,int begin)
5. {
6. int i;
7. for(i=0;i<NUM;i++)    //初始化遍历标志数组
8. visited[i] = false;
9. //先从序号为begin的顶点开始遍历对应的连通图
10. BFS(Gp,begin);
11. //如果是非连通图，该循环保证每个极大连通子图中的顶点都能被遍历到
12. for(i=0;i<NUM;i++)
13. {   if(!visited[i])
14. BFS(Gp,i);
15. }
16. }
17. /*
18. 从序号为begin的顶点开始，广度优先遍历连通图Gp
19. */
20. void BFS(Graph Gp,int begin)
21. {
22. //遍历输出序号为begin的顶点的数据域，并保存遍历信息
23. printf("%c ",Gp[begin].data);
24. visited[begin] = true;
25. int i;
26. int pVertex;  //用来保存从队列中出队的顶点的序号
27. PQUEUE queue = create_queue();  //创建一个空的辅助队列
28. en_queue(queue, begin);          //首先将序号为begin的顶点入队
29. while(!is_empty(queue))
30. {
31. de_queue(queue,&pVertex);
32. //循环遍历，访问完pVertex顶点的所有邻接顶点,并将访问后的邻接顶点入队
33. for(i=first_vertex(Gp,pVertex); i>=0; i=next_vertex(Gp,pVertex,i))
34. {
35. if(!visited[i])
36. {
37. printf("%c ",Gp[i].data);
38. visited[i] = true;
39. en_queue(queue,i);
40. }
41. }
42. }
43. //销毁队列，释放其对应的内存
44. destroy_queue(queue);
45. }

1. /**********************************
2. 图的BFS和DFS
3. Author:兰亭风雨 Date:2014-02-20
4. Email:zyb_maodun@163.com
5. **********************************/
6. #include<stdio.h>
7. #include<stdlib.h>
8. #include "data_structure.h"
9. int main()
10. {
11. Graph Gp = create_graph();
12. //深度优先遍历
13. printf("对图进行深度优先遍历：\n");
14. printf("从顶点A出发DFS的结果：");
15. DFS_traverse(Gp,0);
16. printf("\n");
17. printf("从顶点H出发DFS的结果：");
18. DFS_traverse(Gp,7);
19. printf("\n");
20. printf("从顶点E出发DFS的结果：");
21. DFS_traverse(Gp,4);
22. printf("\n");
23. printf("\n");
24. //广度优先遍历
25. printf("对图进行深度优先遍历：\n");
26. printf("从顶点A出发BFS的结果：");
27. BFS_traverse(Gp,0);
28. printf("\n");
29. printf("从顶点H出发BFS的结果：");
30. BFS_traverse(Gp,7);
31. printf("\n");
32. printf("从顶点E出发BFS的结果：");
33. BFS_traverse(Gp,4);
34. printf("\n");
35. int i;
36. //释放掉为每个单链表所分配的内存
37. for(i=0;i<NUM;i++)
38. {
39. free(Gp[i].first);
40. Gp[i].first = 0;  //防止悬垂指针的产生
41. }
42. //释放掉为顶点数组所分配的内存
43. free(Gp);
44. Gp = 0;
45. return 0;
46. }