[关闭]
@quinn 2015-03-20T01:30:30.000000Z 字数 3870 阅读 1967

深度搜索和广度搜索 - 图的遍历

数据结构


一. 图的连接表示

一种表示图的直接方法是使用二维数组,也称为邻接矩阵。通过邻接矩阵表示顶点 i 和 j 之间是否存在一条边(检查邻接矩阵中行 i 和 j 处是否为非零值)。定义数组visited[N] 标记节点是否被访问过。
以下程序:如果在图中顶点 i 和顶点 j 或者顶点 j 和顶点 i 之间存在一条边,就把关联矩阵 G->edges[i][j] 和 G->edges[j][i] 设置为 1 ;如果不存在这样的边,则设置为 0 。
图的结构 图的关联矩阵
创建图的程序如下:

  1. typedef struct Graph
  2. {
  3. int edges[MAX][MAX]; //连接矩阵
  4. int e; //边数
  5. int n; //顶点数
  6. }Graph;
  7. void CreatGraph(Graph* G)
  8. {
  9. for(int i = 0; i < G->n; i++)
  10. {
  11. for(int j = 0; j < G->n; j++)
  12. {
  13. G->edges[i][j] = 0; //初始化连接矩阵
  14. }
  15. visited[i] = 0; //初始化访问标记
  16. }
  17. //输入相连的顶点
  18. for(int k = 0; k < G->e; k++)
  19. {
  20. int s, t, v;
  21. v = 1;//权重,非0即连接
  22. printf("Please enter two connected vertices\n");
  23. scanf("%d%d", &s, &t);
  24. G->edges[s][t] = v;
  25. }
  26. }

二. 图的遍历

沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
这里写图片描述
如上图所示的无向图,从0 节点开始遍历的顺序:0 -> 1 -> 3 -> 5 -> 4 -> 2
DFS的实现方式一般有两种:递归实现和非递归实现:

递归实现

实现程序简单,比较常用

  1. void DFS(Graph* G, int i)
  2. {
  3. printf("Visiting %d\n", i);
  4. visited[i] = 1;
  5. for(int j = 0; j < G->n; j++)
  6. {
  7. if(G->edges[i][j] != 0 && visited[j] == 0)
  8. DFS(G, j);
  9. }
  10. }

非递归实现:

使用栈压入每一个没有被访问过的节点,由于栈的后进先出的原理,我们总是以最后访问的那一节点(栈顶节点)为起始节点,访问下一个未被访问过的节点,当当前栈顶节点没有后续连接节点要访问时,从栈中弹出。
这里写图片描述
例如上图从节点 0 开始访问的过程为:
访问 0,压入 0 ,访问 1 压入 1,访问 3 压入 3,访问 5 压入 5, 弹出 5(无与 5 相连且未访问的节点),弹出 3 ,访问 4 (此时栈顶为 1),压入 4,弹出 4,访问 2,弹出 2,弹出 0, 栈空。
遍历的顺序:0 -> 1 -> 3 -> 5 -> 4 -> 2

  1. void DFS1(Graph* G, int i)
  2. {
  3. printf("Visiting %d\n", i);
  4. visited[i] = 1;
  5. Stack s = NULL;
  6. s = StackInit(s);
  7. StackPush(s, i);
  8. while (!StackIsEmpty(s))
  9. {
  10. i = StackTop(s);
  11. int j;
  12. for (j = 0; j < G->n; j++)
  13. {
  14. if (G->edges[i][j] != 0 && visited[j] == 0)
  15. {
  16. printf("Visiting %d\n", j);
  17. visited[j] = 1;
  18. StackPush(s, j);
  19. break;
  20. }
  21. }
  22. if (j == G->n) //已无与i相连且未访问的节点
  23. {
  24. StackPop(s);
  25. }
  26. }
  27. }

又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。
使用FIFO队列压入每一个没有被访问过的节点, 由于队列的先进先出的原理,我们总是以最开始访问的那一节点(队列顶节点)为起始节点,访问所有与之相连且未被访问过的节点,当当前队列顶节点没有后续连接节点要访问时,从队列中弹出。
这里写图片描述
访问顺序为:0 -> 1 -> 2 -> 3 -> 4 -> 5
遍历过程为: 访问 0 ,压入 0, (队列顶一直为 0 )<访问 1 压入 1,访问 2 压入 2 >,弹出 0 ,(队列顶一直为 1 )<访问 3 压入 3,访问 4 压入 4>,弹出 1,(队顶为2),弹出 2,(队顶为3)访问 5 ,弹出 3,(队顶为4)弹出 4,访问压入5,弹出 5.

  1. void BFS(Graph *G, int i)
  2. {
  3. printf("Visiting %d\n", i);
  4. visited[i] = 1;
  5. Queue q = NULL;
  6. q = (Queue)malloc(sizeof(q));
  7. QueueInit(q); //上一句分配内存后,应该初始化后才能正常使用
  8. QueuePut(q, i);
  9. while(!QueueIsEmpty(q))
  10. {
  11. i = QueueGet(q);
  12. for(int j = 0; j < G->n; j++)
  13. {
  14. if(G->edges[i][j] != 0 && visited[j] == 0)
  15. {
  16. printf("Visiting %d\n", j);
  17. visited[j] = 1;
  18. QueuePut(q, j);
  19. }
  20. }
  21. }
  22. }

三.测试主程序

  1. #include<stdio.h>
  2. #include "stack.h"
  3. #include "queue.h"
  4. #define MAX 100
  5. typedef struct Graph Graph;
  6. int visited[MAX];
  7. struct Graph
  8. {
  9. int edges[MAX][MAX]; //连接矩阵
  10. int e; //边数
  11. int n; //顶点数
  12. };
  13. //将visited[]全部设为0
  14. void visitedInit(Graph* G, int visited[])
  15. {
  16. for (int i = 0; i < G->n; i++)
  17. {
  18. visited[i] = 0;
  19. }
  20. }
  21. //创建图(矩阵连接)
  22. void CreatGraph(Graph* G)
  23. {
  24. for(int i = 0; i < G->n; i++)
  25. {
  26. for(int j = 0; j < G->n; j++)
  27. {
  28. G->edges[i][j] = 0; //初始化连接矩阵
  29. }
  30. visited[i] = 0; //初始化访问标记
  31. }
  32. //输入相连的顶点
  33. for(int k = 0; k < G->e; k++)
  34. {
  35. int s, t, v;
  36. v = 1;//权重,非0即连接
  37. printf("Please enter the two connected vertices\n");
  38. scanf("%d%d", &s, &t);
  39. G->edges[s][t] = v;
  40. }
  41. }
  42. //递归深度优先搜索
  43. void DFS(Graph* G, int i)
  44. {
  45. printf("Visiting %d\n", i);
  46. visited[i] = 1;
  47. for(int j = 0; j < G->n; j++)
  48. {
  49. if(G->edges[i][j] != 0 && visited[j] == 0)
  50. DFS(G, j);
  51. }
  52. }
  53. //非递归深度优先搜索,栈
  54. void DFS1(Graph* G, int i)
  55. {
  56. printf("Visiting %d\n", i);
  57. visited[i] = 1;
  58. Stack s = NULL;
  59. s = StackInit(s);
  60. StackPush(s, i);
  61. while (!StackIsEmpty(s))
  62. {
  63. i = StackTop(s);
  64. int j;
  65. for (j = 0; j < G->n; j++)
  66. {
  67. if (G->edges[i][j] != 0 && visited[j] == 0)
  68. {
  69. printf("Visiting %d\n", j);
  70. visited[j] = 1;
  71. StackPush(s, j);
  72. break;
  73. }
  74. }
  75. if (j == G->n)
  76. {
  77. StackPop(s);
  78. }
  79. }
  80. }
  81. //广度优先搜索
  82. void BFS(Graph *G, int i)
  83. {
  84. printf("Visiting %d\n", i);
  85. visited[i] = 1;
  86. Queue q = NULL;
  87. q = (Queue)malloc(sizeof(q));
  88. QueueInit(q); //上一句分配内存后,应该初始化后才能正常使用
  89. QueuePut(q, i);
  90. while(!QueueIsEmpty(q))
  91. {
  92. i = QueueGet(q);
  93. for(int j = 0; j < G->n; j++)
  94. {
  95. if(G->edges[i][j] != 0 && visited[j] == 0)
  96. {
  97. printf("Visiting %d\n", j);
  98. visited[j] = 1;
  99. QueuePut(q, j);
  100. }
  101. }
  102. }
  103. }
  104. int main()
  105. {
  106. int n, e;
  107. Graph* G = (Graph*)malloc(sizeof(*G));
  108. printf("Please enter the number of vertices and edges\n");
  109. scanf("%d %d", &n, &e); //输入图的顶点数和边数
  110. G->n = n;
  111. G->e = e;
  112. CreatGraph(G);
  113. printf("\nDepth-First-Search-1:\n");
  114. DFS(G, 0);
  115. visitedInit(G, visited); //将visited[]全部设为0
  116. printf("\nDepth-First-Search-2:\n");
  117. DFS1(G, 0);
  118. visitedInit(G, visited); //将visited[]全部设为0
  119. printf("\nBreadth-First-Search:\n");
  120. BFS(G, 0);
  121. system("pause");
  122. return 0;
  123. }

结果如下:
这里写图片描述

四. 源代码下载

http://pan.baidu.com/s/1DAD6u

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注