[关闭]
@guoxs 2016-01-15T15:55:46.000000Z 字数 3594 阅读 3292

图的遍历

数据结构与算法


四、图的遍历

图的遍历:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)。

图的遍历要比树的遍历复杂的多,因为它的任一顶点都可能和其余的所有顶点相邻接,极有可能存在沿着某条路径搜索后,又回到原顶点,而有些顶点却还没有遍历到的情况。因此需要在遍历过程中把访问过的顶点打上标记,以避免访问多次而不自知。具体办法是设置一个访问数组visited[n],n是图中顶点的个数,初值为0,访问过后设置为1。

4.1 深度优先遍历

深度优先遍历(Depth_First_Search),也有称为深度优先搜索,简称为DFS。
深度优先遍历
遍历过程

    首先从顶点A开始,做上表示走过的记号后,面前有两条路,通向B和F,可以定一个原则,在没有碰到重复顶点的情况下,始终是向右手边走,于是走到了B顶点。整个行路过程,可参看上图的右图。此时发现有三条分支,分别通向顶点C、I、G,右手通行原则,使得我们走到了C顶点。就这样一直顺着右手通道走,一直走到F顶点。当依然选择右手通道走过去后,发现走回到顶点A了,因为在这里做了记号表示已经走过。此时退回到顶点F,走向从右数的第二条通道,到了G顶点,它有三条通道,发现B和D都已经是走过的,于是走到H,当面对通向H的两条通道D和E时,会发现都已经走过了。

    此时是否已经遍历了所有顶点呢?没有。可能还有很多分支的顶点没有走到,所以按原路返回。在顶点H处,再无通道没走过,返回到G,也无未走过通道,返回到F,没有通道,返回到E,有一条通道通往H的通道,验证后也是走过的,再返回到顶点D,此时还有三条道未走过,一条条来,H走过了,G走过了,I,哦,这是一个新顶点,没有标记,赶快记下来。继续返回,直到返回顶点A,确认已经完成遍历任务,找到了所有的9个顶点。

深度优先遍历其实就是一个递归的过程,就像是一棵树的前序遍历。从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。这里讲到的是连通图,对于非连通图,只需要对它的连通分量分别进行深度优先遍历,即在先前一个顶点进行一次深度优先遍历后,若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

如果用邻接矩阵的方式,代码如下:

  1. /* Boolean是布尔类型,其值是TRUE或FALSE */
  2. typedef int Boolean;
  3. /* 访问标志的数组 */
  4. Boolean visited[MAX];
  5. /* 邻接矩阵的深度优先递归算法 */
  6. void DFS(MGraph G, int i)
  7. {
  8. int j;
  9. visited[i] = TRUE;
  10. /* 打印顶点,也可以其他操作 */
  11. printf("%c ", G.vexs[i]);
  12. for (j = 0; j < G.numVertexes; j++)
  13. if (G.arc[i][j] == 1 && !visited[j])
  14. /* 对为访问的邻接顶点递归调用 */
  15. DFS(G, j);
  16. }
  17. /* 邻接矩阵的深度遍历操作 */
  18. void DFSTraverse(MGraph G)
  19. {
  20. int i;
  21. for (i = 0; i < G.numVertexes; i++)
  22. /* 初始所有顶点状态都是未访问过状态 */
  23. visited[i] = FALSE;
  24. for (i = 0; i < G.numVertexes; i++)
  25. /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */
  26. if (!visited[i])
  27. DFS(G, i);
  28. }

果图结构是邻接表结构,其DFSTraverse函数的代码是几乎相同的,只是在递归函数中因为将数组换成了链表而有不同,代码如下:

  1. /* 邻接表的深度优先递归算法 */
  2. void DFS(GraphAdjList GL, int i)
  3. {
  4. EdgeNode *p;
  5. visited[i] = TRUE;
  6. /* 打印顶点,也可以其他操作 */
  7. printf("%c ", GL->adjList[i].data);
  8. p = GL->adjList[i].firstedge;
  9. while (p)
  10. {
  11. if (!visited[p->adjvex])
  12. /* 对为访问的邻接顶点递归调用 */
  13. DFS(GL, p->adjvex);
  14. p = p->next;
  15. }
  16. }
  17. /* 邻接表的深度遍历操作 */
  18. void DFSTraverse(GraphAdjList GL)
  19. {
  20. int i;
  21. for (i = 0; i < GL->numVertexes; i++)
  22. /* 初始所有顶点状态都是未访问过状态 */
  23. visited[i] = FALSE;
  24. for (i = 0; i < GL->numVertexes; i++)
  25. /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */
  26. if (!visited[i])
  27. DFS(GL, i);
  28. }

对比两个不同存储结构的深度优先遍历算法,对于n个顶点e条边的图来说,邻接矩阵由于是二维数组,要查找每个顶点的邻接点需要访问矩阵中的所有元素,因此都需要的时间。而邻接表做存储结构时,找邻接点所需的时间取决于顶点和边的数量,所以是O(n+e)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。

4.2 广度优先遍历

广度优先遍历(Breadth_First_Search),又称为广度优先搜索,简称BFS。

如果说图的深度优先遍历类似树的前序遍历,那么图的广度优先遍历就类似于树的层序遍历了。如下图,把深度优先遍历图形案例变形,变形原则是顶点A放置在最上第一层,让与它有边的顶点B、F为第二层,再让与B和F有边的顶点C、I、G、E为第三层,再将这四个顶点有边的D、H放在第四层,此时在视觉上感觉图的形状发生了变化,其实顶点和边的关系还是完全相同的。
广度优先遍历

邻接矩阵结构的广度优先遍历算法:

  1. /* 邻接矩阵的广度遍历算法 */
  2. void BFSTraverse(MGraph G)
  3. {
  4. int i, j;
  5. Queue Q;
  6. for (i = 0; i < G.numVertexes; i++)
  7. visited[i] = FALSE;
  8. /* 初始化一辅助用的队列 */
  9. InitQueue(&Q);
  10. /* 对每一个顶点做循环 */
  11. for (i = 0; i < G.numVertexes; i++)
  12. {
  13. /* 若是未访问过就处理 */
  14. if (!visited[i])
  15. {
  16. /* 设置当前顶点访问过 */
  17. visited[i]=TRUE;
  18. /* 打印顶点,也可以其他操作 */
  19. printf("%c ", G.vexs[i]);
  20. /* 将此顶点入队列 */
  21. EnQueue(&Q,i);
  22. /* 若当前队列不为空 */
  23. while (!QueueEmpty(Q))
  24. {
  25. /* 将队中元素出队列,赋值给i */
  26. DeQueue(&Q, &i);
  27. for (j = 0; j < G.numVertexes; j++)
  28. {
  29. /* 判断其他顶点若与当前顶点存在边且未访问过 */
  30. if (G.arc[i][j] == 1 && !visited[j])
  31. {
  32. /* 将找到的此顶点标记为已访问 */
  33. visited[j]=TRUE;
  34. /* 打印顶点 */
  35. printf("%c ", G.vexs[j]);
  36. /* 将找到的此顶点入队列 */
  37. EnQueue(&Q,j);
  38. }
  39. }
  40. }
  41. }
  42. }
  43. }

对于邻接表的广度优先遍历,代码与邻接矩阵差异不大,代码如下:

  1. /* 邻接表的广度遍历算法 */
  2. void BFSTraverse(GraphAdjList GL)
  3. {
  4. int i;
  5. EdgeNode *p;
  6. Queue Q;
  7. for (i = 0; i < GL->numVertexes; i++)
  8. visited[i] = FALSE;
  9. InitQueue(&Q);
  10. for (i = 0; i < GL->numVertexes; i++)
  11. {
  12. if (!visited[i])
  13. {
  14. visited[i] = TRUE;
  15. /* 打印顶点,也可以其他操作 */
  16. printf("%c ", GL->adjList[i].data);
  17. EnQueue(&Q, i);
  18. while (!QueueEmpty(Q))
  19. {
  20. DeQueue(&Q, &i);
  21. /* 找到当前顶点边表链表头指针 */
  22. p = GL->adjList[i].firstedge;
  23. while (p)
  24. {
  25. /* 若此顶点未被访问 */
  26. if (!visited[p->adjvex])
  27. {
  28. visited[p->adjvex] = TRUE;
  29. printf("%c ", GL->adjList[p->adjvex].data);
  30. /* 将此顶点入队列 */
  31. EnQueue(&Q, p->adjvex);
  32. }
  33. /* 指针指向下一个邻接点 */
  34. p = p->next;
  35. }
  36. }
  37. }
  38. }
  39. }

对比图的深度优先遍历与广度优先遍历算法可知,它们在时间复杂度上是一样的,不同之处仅仅在于对顶点访问的顺序不同。可见两者在全图遍历上是没有优劣之分的,只是视不同的情况选择不同的算法。
深度优先更适合目标比较明确,以找到目标为主要目的的情况,而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

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