devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法学习(5)-图的遍历

作者：Gausst松鼠会 | 2024-04-29 09:17:36

赞

踩

算法学习(5)-图的遍历

目录

什么是深度和广度优先

图的深度优先遍历-城市地图

图的广度优先遍历-最少转机

什么是深度和广度优先

         使用深度优先搜索来遍历这个图的过程具体是：

  1. 首先从一个未走到过的顶点作为起始顶点， 比如以1号顶点作为起点。
  2. 沿1号顶点的边去尝试访问其它未走到过的顶点， 首先发现2 号顶点还没有走到过， 于是来到了2 号顶点。
  3. 再以2 号顶点作为出发点继续尝试访问其它未走到过的顶点， 这样又来到了4号顶点。
  4. 再以4 号顶点作为出发点继续尝试访问其它未走到过的顶点。
  5. 但是， 此时沿4号顶点的边， 已经不能访问到其它未走到过的顶点了， 所以要返回到2号顶点。
  6. 返回到2号顶点后， 发现沿2 号顶点的边也不能再访问到其它未走到过的顶点。因此还需要继续返回到1号顶点。
  7. 再继续沿1号顶点的边看看还能否访问到其它未走到过的顶点。
  8. 此时又会来到3号顶点， 再以3号顶点作为出发点继续访问其它未走到过的顶点， 千是又来到5号顶点。
  9. 到此， 所有顶点都走到过了， 遍历结束。

        深度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；没有未访问过的顶点时， 则回到上一个顶点， 继续试探访问别的顶点， 直到所有的顶点都被访问过。

        显然， 深度优先遍历是沿着图的某一条分支遍历直到末端， 然后回溯， 再沿着另一条进行同样的遍历， 直到所有的顶点都被访问过为止。那这一过程如何用代码来实现呢？在讲代码实现之前我们先来解决如何存储一个图的问题。最常用的方法是使用一个二维数组e来存储， 如下。

 

        上图二维数组中第i行第j列表示的就是顶点 i 到顶点 j 是否有边。1表示有边， ∞表示
没有边， 这里我们将自己到自己（即i等于j)设为0。我们将这种存储图的方法称为图的邻
接矩阵存储法。
        注意观察会发现这个二维数组是沿主对角线对称的， 因为上面这个图是无向图。所谓无向阳指的就是图的边没有方向， 例如边1-5表示， 1号顶点可以到5号顶点， 5号顶点也可以到1号顶点。
        接下来要解决的问题就是如何用深度优先搜索来实现遍历了。 

  1. void dfs(int cur) { // cur是当前所在的顶点编号
  2.     printf("%d. ", cur);
  3.     sum++; // 每访问一个顶点s就加1
  4.     if (sum == n) return; // 所有的顶点都已经访问过则直接退出
  5.     for (i = 1; i <= n; i++) { // 从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
  6.         // 判断当前顶点cur到顶点i是否有边，并判断顶点i是否已访问过
  7.         if (e[cur][i] == 1 && book[i] == 0) {
  8.             // 标记顶点i已经访问过
  9.             book[i] = 1;
  10.             // 从顶点i再出发继续遍历
  11.             dfs(i);
  12.         }
  13.     }
  14.     return;
  15. }

        在上面的代码中变揽cur存储的是当前正在遍历的顶点， 二维数组e存储的就是图的边（邻接矩阵）， 数组book用来记录哪些顶点已经访问过， 变揽sum用来记录已经访问过多少个顶点， 变证n存储的是图的顶点的总个数。完整代码如下。

  1. #include <stdio.h>
  2.  
  3. int book[101], sum, n, e[101][101];
  4.  
  5. void dfs(int cur) { // cur是当前所在的顶点编号
  6.     int i;
  7.     printf("%d ", cur);
  8.     sum++; // 每访问一个顶点，sum就加1
  9.     if (sum == n) return; // 所有的顶点都已经访问过则直接退出
  10.     for (i = 1; i <= n; i++) { // 从1号顶点到n号顶点依次尝试，看哪些顶点与当前顶点cur有边相连
  11.         // 判断当前顶点cur到顶点i是否有边， 并判断顶点i是否已访问过
  12.         if (e[cur][i] == 1 && book[i] == 0) {
  13.             // 标记顶点i已经访问过
  14.             book[i] = 1;
  15.             // 从顶点i再出发继续遍历
  16.             dfs(i);
  17.         }
  18.     }
  19.     return;
  20. }
  21.  
  22. int main() {
  23.     int i, j, m, a, b;
  24.     scanf("%d %d", &n, &m);
  25.     // 初始化二维矩阵
  26.     for (i = 1; i <= n; i++) {
  27.         for (j = 1; j <= n; j++) {
  28.             if (i == j)
  29.                 e[i][j] = 0;
  30.             else
  31.                 e[i][j] = 99999999; // 我们这里假设999999999为正无穷
  32.         }
  33.     }
  34.     // 读入顶点之间的边
  35.     for (i = 1; i <= m; i++) {
  36.         scanf("%d %d", &a, &b);
  37.         e[a][b] = 1;
  38.         e[b][a] = 1; // 这里是无向图，所以需要将e[b][a]也赋为1
  39.     }
  40.     // 从1号城市出发
  41.     book[1] = 1; // 标记1号顶点已访问
  42.     dfs(1); // 从1号顶点开始遍历
  43.     getchar();
  44.     getchar();
  45.     return 0;
  46. }

        广度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点， 然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过， 遍历结束。

        代码实现如下：

  1. #include <stdio.h>
  2.  
  3. int main() {
  4.     int i, j, n, m, a, b, cur;
  5.     int book[101] = {0}; // 使用数组初始化语法将book数组初始化为全0
  6.     int e[101][101];
  7.     int que[10001], head = 0, tail = 0; // 将队列初始化为0
  8.  
  9.     scanf("%d %d", &n, &m);
  10.  
  11.     // 初始化二维矩阵
  12.     for (i = 1; i <= n; i++) {
  13.         for (j = 1; j <= n; j++) {
  14.             if (i == j) {
  15.                 e[i][j] = 0;
  16.             }
  17.             else {
  18.                 e[i][j] = 99999999; // 假设999999999为正无穷
  19.             }
  20.         }
  21.     }
  22.  
  23.     // 读入顶点之间的边
  24.     for (i = 1; i <= m; i++) {
  25.         scanf("%d %d", &a, &b);
  26.         e[a][b] = 1;
  27.         e[b][a] = 1; // 无向图，需要双向赋值
  28.     }
  29.  
  30.     // 从1号顶点出发，将1号顶点加入队列
  31.     que[tail] = 1;
  32.     tail++;
  33.     book[1] = 1; // 标记1号顶点已访问
  34.  
  35.     // 当队列不为空时循环
  36.     while (head < tail) {
  37.         cur = que[head]; // 当前正在访问的顶点编号
  38.         // 从1~n依次尝试
  39.         for (i = 1; i <= n; i++) {
  40.             // 判断从顶点cur到顶点i是否有边，且顶点i是否已经访问过
  41.             if (e[cur][i] == 1 && book[i] == 0) {
  42.                 // 如果从顶点cur到顶点i有边，并且顶点i没有被访问过，则将顶点i入队
  43.                 que[tail] = i;
  44.                 tail++;
  45.                 book[i] = 1; // 标记顶点i已访问
  46.             }
  47.         }
  48.         // 如果tail大于n，则所有顶点都已经被访问过，退出循环
  49.         if (tail > n) {
  50.             break;
  51.         }
  52.         head++; // 顶点扩展结束后，head++，继续往下扩展
  53.     }
  54.  
  55.     // 输出队列中的顶点编号
  56.     for (i = 0; i < tail; i++) {
  57.         printf("%d ", que[i]);
  58.     }
  59.     getchar();
  60.     getchar();
  61.     return 0;
  62. }

图的深度优先遍历-城市地图

         我们可以创建一个5*5的邻接矩阵，如下图：

        用book数组记录哪些城市已经走过，用全局变量min来更新每次找到的路径的最小值，代码实现如下：

  1. #include <stdio.h>
  2. int min = 99999999, book[101], n, e[101][101]; // 我们这里假设999999999为正无穷
  3.  
  4. // cur是当前所在的城市编号，dis是当前已经走过的路程
  5. void dfs(int cur, int dis) {
  6.     int j;
  7.     // 如果当前走过的路程已经大于之前找到的最短路，则没有必要再往下尝试了，立即返回
  8.     if (dis > min)
  9.         return;
  10.     if (cur == n)  // 判断是否到达了目标城市
  11.     {
  12.         if (dis < min) {
  13.             min = dis;  // 更新最小值
  14.             return;
  15.         }
  16.     }
  17.     for (j = 1; j <= n; j++) { // 从1号城市到n号城市依次尝试
  18.         // 判断当前城市cur到城市j是否有路，并判断城市j是否在已走过的路径中
  19.         if (e[cur][j] != 99999999 && book[j] == 0) {
  20.             book[j] = 1;  // 标记城市j已经在路径中
  21.             dfs(j, dis + e[cur][j]);  // 从城市j再出发，继续寻找目标城市
  22.             book[j] = 0;  // 之前一步探索完毕之后，取消对城市j的标记
  23.         }
  24.     }
  25. }
  26.  
  27. int main() {
  28.     int i, j, m, a, b, c;
  29.     scanf("%d %d", &n, &m);
  30.  
  31.     // 初始化二维矩阵
  32.     for (i = 1; i <= n; i++)
  33.         for (j = 1; j <= n; j++)
  34.             if (i == j)
  35.                 e[i][j] = 0;
  36.             else
  37.                 e[i][j] = 99999999;
  38.  
  39.     // 读入城市之间的道路
  40.     for (i = 1; i <= m; i++) {
  41.         scanf("%d %d %d", &a, &b, &c);
  42.         e[a][b] = c;
  43.     }
  44.  
  45.     // 从1号城市出发
  46.     book[1] = 1;  // 标记1号城市已经在路径中
  47.     dfs(1, 0);  // 1表示当前所在的城市编号，0表示当前已经走过的路程
  48.  
  49.     printf("%d\n", min);  // 打印1号城市到目标城市的最短路径
  50.     getchar();
  51.     getchar();
  52.     return 0;
  53. }

图的广度优先遍历-最少转机

 

  1. #include <stdio.h>
  2.  
  3. struct note {
  4.     int x;  // 城市编号
  5.     int s;  // 转机次数
  6. };
  7.  
  8. int main() {
  9.     struct note que[2501];
  10.     // 初始化
  11.     int e[51][51] = {0}, book[51] = {0};
  12.     int head, tail;
  13.     int i, j, n, m, a, b, cur, start, end, flag = 0;
  14.     scanf("%d %d %d %d", &n, &m, &start, &end);
  15.  
  16.     // 初始化二维矩阵
  17.     for (i = 1; i <= n; i++) {
  18.         for (j = 1; j <= n; j++) {
  19.             if (i == j)
  20.                 e[i][j] = 0;
  21.             else
  22.                 e[i][j] = 99999999;
  23.         }
  24.     }
  25.  
  26.     // 读入城市之间的航班
  27.     for (i = 1; i <= m; i++) {
  28.         scanf("%d %d", &a, &b);
  29.         // 注：这里是无向图
  30.         e[a][b] = 1;
  31.         e[b][a] = 1;
  32.     }
  33.  
  34.     // 队列初始化
  35.     head = 1;
  36.     tail = 1;
  37.     // 从start号城市出发，将start号城市加入队列
  38.     que[tail].x = start;
  39.     que[tail].s = 0;
  40.     tail++;
  41.     book[start] = 1;  // 标记start号城市已在队列中
  42.  
  43.     // 当队列不为空的时候循环
  44.     while (head < tail) {
  45.         cur = que[head].x;  // 当前队列中首城市的编号
  46.         for (j = 1; j <= n; j++) {  // 从1~n依次尝试
  47.             // 从城市cur到城市j是否有航班并且判断城市j是否已经在队列中
  48.             if (e[cur][j] != 99999999 && book[j] == 0) {
  49.                 // 如果从城市cur到城市j有航班并且城市j不在队列中，则将城市j入队
  50.                 que[tail].x = j;
  51.                 que[tail].s = que[head].s + 1;  // 转机次数+1
  52.                 tail++;
  53.                 // 标记城市j已经在队列中
  54.                 book[j] = 1;
  55.                 // 如果到达目标城市，停止扩展，任务结束，退出循环
  56.                 if (que[tail].x == end) {
  57.                     // 注意下面两句话的位置千万不要写颠倒了
  58.                     flag = 1;
  59.                     break;
  60.                 }
  61.             }
  62.         }
  63.         if (flag == 1)
  64.             break;
  65.         head++;  // 注意这地方，千万不要忘记当一个点扩展结束后，head++才能继续扩展
  66.     }
  67.  
  68.     // 打印队列中末尾最后一个（目标城市）的转机次数
  69.     // 注意：tail是指向队列队尾（即最后一位）的下一个位置，所以这里要-1
  70.     printf("%d\n", que[tail - 1].s);
  71.     getchar();
  72.     getchar();
  73.     return 0;
  74. }

         当然也可以使用深度优先搜索解决， 但是这里用广度优先搜索会更快。广度优先搜索更
加适用于所有边的权值相同的情况。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/507023
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号