• 6.5 图的遍历

     前言：

    主要内容：

    这段文字描述的是图的遍历。图的遍历与树的遍历有些相似，都是从某个点开始，按照一定的规则遍历其他的点，但是图的遍历更加复杂，因为图中存在循环和回路，这意味着可能会多次访问到同一顶点。

    ### 主要内容：
    1. **图的遍历**
       - 图的遍历是从图中的某一顶点出发，按照某种方法，对图中的所有顶点进行访问，每个顶点都只访问一次。
       - 图的遍历是图算法的基础，可以用于解决连通性问题、拓扑排序、寻找关键路径等。

    2. **复杂性**
       - 图的遍历比树的遍历要复杂，因为图中的任一顶点都可能与其它顶点相邻，可能会存在回路，导致多次访问同一顶点。

    3. **避免重复访问**
       - 为了避免同一顶点被访问多次，使用一个辅助数组 `visited` 来记录每个已经访问过的顶点。
       - 当顶点被访问时，将相应的 `visited` 数组的值设为 `true`。

    4. **遍历方法**
       - 图的遍历主要有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。
       - 这两种遍历方法都适用于无向图和有向图。

    ### 总结：
    在图的遍历中，深度优先搜索和广度优先搜索是两种主要的遍历方法。深度优先搜索在探索尽可能深的分支时，会一直前进，直到没有更深的分支为止。而广度优先搜索则是一层一层地进行遍历。在进行图的遍历时，为了避免重复访问，通常需要一个 `visited` 数组来标记已经访问过的顶点。

     

     6.5.1 深度优先搜索

    主要内容：

    6.5.1 深度优先搜索 (DFS)

    1. 深度优先搜索遍历过程

    - 深度优先搜索遍历类似于树的先序遍历。
    - 对于连通图的遍历过程：
      1. 从图中某顶点v出发，访问v。
      2. 找出刚访问过的顶点的未被访问的邻接点，访问该顶点，并以该顶点为新顶点重复此步骤，直至没有未被访问的邻接点为止。
      3. 返回至上一个有未访问邻接点的顶点，访问其未被访问的邻接点。
      4. 重复2和3步骤，直至所有顶点都被访问过。

    - 举例: 无向图G₄的深度优先搜索遍历图如图6.17(b)所示。

    - 深度优先搜索所构成的所有顶点和实箭头的边，称为深度优先生成树。

    #### 2. 算法实现

    - 深度优先搜索遍历是递归的。
    - 使用访问标志数组`visited[n]`来标记顶点是否被访问。

    **算法6.3 深度优先搜索遍历连通图**

    1. void DFS(Graph G, int v) {
    2.     cout << v;
    3.     visited[v] = true;
    4.     for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
    5.         if (!visited[w]) DFS(G, w);
    6. }


    - 如果是非连通图，需要循环调用该算法，直到所有顶点都被访问过。

    **算法6.4 深度优先搜索遍历非连通图**

    1. void DFSTraverse(Graph G) {
    2.     for (v = 0; v < G.vexnum; ++v) visited[v] = false;
    3.     for (v = 0; v < G.vexnum; ++v) if (!visited[v]) DFS(G, v);
    4. }

    - 算法6.5 和算法6.6 分别采用邻接矩阵和邻接表实现了深度优先搜索遍历。

    #### 3. 算法分析

    - 每个顶点至多调用一次DFS()函数。
    - 时间复杂度取决于存储结构。邻接矩阵为O(n²)；邻接表为O(e)，其中n为顶点数，e为边数。

    ### 总结

    深度优先搜索(DFS)是一种常用的图遍历算法，适用于连通图和非连通图。它从图中的一个顶点出发，递归地访问其所有未访问过的邻接点。DFS的实现依赖于图的存储结构，因此，不同的存储结构会导致不同的实现方法和时间复杂度。在实际应用中，需要根据具体情况选择合适的存储结构和实现方法。

    我的理解：

    我们可以将深度优先搜索（DFS）比喻为一个人在迷宫中探路的过程。

    ### 深度优先搜索（DFS）如同探索迷宫：
    1. **迷宫与图**
       - 想象一个迷宫，其中每个房间是图中的一个顶点，每个通道是边。
       - 迷宫的入口是搜索的起始顶点。

    2. **探险家与算法执行**
       - 想象探险家是在执行DFS的算法。
       - 探险家进入一个房间（访问一个顶点）时会做记号，避免再次进入（标记为已访问）。

    3. **深入探索与递归**
       - 探险家每次会选择一个未探索的通道深入探索，直到来到一个没有未探索通道的房间（递归访问邻接点）。
       - 在无法继续深入时，他会回溯到上一个房间，寻找其他未探索的通道（回溯）。

    4. **全图遍历**
       - 如果迷宫有多个不连通的区域，探险家会完成一个区域的探索后，返回到入口，选择另一个未探索的区域进行探索，直到整个迷宫都被探索完毕。
       - 这就如同在非连通图中，从每个未访问的顶点出发进行DFS，直至图中的所有顶点都被访问。

    ### 深度优先生成树
    就像探险家探索迷宫时可能会画出一张地图，这张地图记录了他访问过的所有房间和他通过的通道，这张地图就像是深度优先搜索过程中生成的树，称为深度优先生成树。

    ### 总结
    通过以上的比喻，深度优先搜索就像一个探险家在未知的迷宫中进行探索，他会深入每一个通道，直到不能再深入为止，然后回溯到上一个分岔口，继续探索其他通道，直到整个迷宫都被探索完毕。在这个过程中，探险家画出的迷宫地图就是深度优先生成树。

     6.5.2 广度优先搜索

    主要内容：

    6.5.2 广度优先搜索

    1. 广度优先搜索遍历的过程
    广度优先搜索（BFS）类似于树的层次遍历。过程如下：
    - (1) 从图中某个顶点v出发并访问v。
    - (2) 依次访问v的各个未曾访问过的邻接点。
    - (3) 对每个邻接点，再依次访问它们的邻接点，重复此过程，直至所有已被访问的顶点的邻接点都被访问到。
    - 例子中展示了一种具体的广度优先搜索过程，所有的顶点和边构成了一棵广度优先生成树。

    2. 广度优先搜索遍历的算法实现
    广度优先搜索的特点是尽可能先进行横向搜索。算法实现时需要引入队列来保存已被访问过的顶点，并需要一个访问标志数组来记录哪些顶点被访问过。

    【算法步骤】
    - ① 从图中某个顶点v出发，访问v，并将visited[v]置为true，然后使v入队。
    - ② 只要队列不空，重复以下操作：
      - 队头元素u出队；
      - 依次检查u的所有邻接点w，如果visited[w]为false, 则访问w，并将visited[w]置为true，然后使w入队。

    【算法描述】

    1. void BFS(Graph G, int v) {
    2.     cout << v;
    3.     visited[v] = true; // 访问第v个顶点，并将访问标志数组的相应分量值置为true
    4.     InitQueue(Q); // 辅助队列Q初始化，置空
    5.     EnQueue(Q, v); // v入队
    6.     while (!QueueEmpty(Q)) { // 队列非空
    7.         DeQueue(Q, u); // 队头元素出队并置为u
    8.         for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) // 依次检查u的所有邻接点w
    9.             if (!visited[w]) {
    10.                 cout << w;
    11.                 visited[w] = true;
    12.                 EnQueue(Q, w);
    13.             }
    14.     }
    15. }

    3. 广度优先搜索的时间复杂度
    广度优先搜索的时间复杂度与遍历所有顶点和边的次数有关，通常情况下，广度优先搜索的时间复杂度为O(V+E)，其中V是顶点的数量，E是边的数量。

    笔记总结
    广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。这个算法使用队列来记录要访问的顶点，并使用一个访问标志数组来避免重复访问。广度优先搜索的基本思想是“宽度优先”，即先访问起始顶点的所有邻接点，然后再访问这些邻接点的未访问邻接点。此算法通常用于找到无权图中的最短路径。

     我的理解：

    当然可以。我们可以将广度优先搜索（BFS）比喻为在一座未知的城市中探索。

    假设你现在站在一个城市的某个路口（初始顶点），你的目标是探索这座城市中的每个路口（每个顶点）。城市中的每条街道（边）都连接着两个路口（两个顶点）。

    1. **开始探索：**
       - 当你来到一个新的路口，你会在地图上标记这个路口（访问顶点，并标记为已访问）。
       - 然后，你会查看与这个路口直接相连的所有其他路口（邻接点），并将它们加入到你的“待探索”名单中（入队）。

    2. **探索邻居：**
       - 你会先探索与起始路口直接相连的所有路口，即在移动到下一层邻居之前，你会探索所有当前层的邻居（横向搜索）。
       - 在探索每个路口时，你会将所有未被探索的相邻路口加入到“待探索”名单中。
       - 你会重复这个过程，直到所有的路口都被探索过（队列为空）。

    3. **记录与计划：**
       - 为了记住你需要探索哪些路口，你会使用一张清单（队列）。
       - 每次你探索一个新的路口，你会将与它直接相连的所有未探索的路口加入到这张清单中。
       - 同时，你会在地图上标记每个已探索的路口，以防重复探索（访问标志数组）。

    这个过程就像是一场由内而外的探索。你始终优先探索离你最近的、还未探索过的路口，直到整座城市都被你探索过。在这个过程中，你使用了一个清单（队列）来保持探索的顺序，以及一张地图（访问标志数组）来避免重复探索。

    例题： 

    ### 题目：岛屿数量

    假设有一个二维数组，`0` 表示水域，`1` 表示陆地。相邻的陆地形成一个岛屿，求出岛屿的数量。

    例如：

    ```plaintext
    11110
    11010
    11000
    00000
    ```

    输出：`1`

    ```plaintext
    11000
    11000
    00100
    00011
    ```

    输出：`3`

    思考过程和分析过程：

    思考过程：

    1. **深度优先遍历：**
       从一个陆地出发，尽可能深入，将与其相连的所有陆地都访问一遍，每找到一个陆地就将其标记为已访问，最终我们就能得到一个岛屿。
       
    2. **广度优先遍历：**
       从一个陆地出发，访问其所有相邻的陆地，将未访问的陆地加入队列，再依次访问队列中的每个陆地及其相邻陆地，直到队列为空。

    #### 分析过程：

    1. 对于深度优先遍历和广度优先遍历，我们都需要遍历整个二维数组，当遇到一个`1`时，就从这个点出发，进行深度优先遍历或广度优先遍历，标记相连的所有陆地，岛屿数加`1`。
       
    2. 时间复杂度：
       遍历整个二维数组，每个点都会被访问一次，所以时间复杂度为：O(m×n)，其中`m`和`n`分别为二维数组的行数和列数。

    C++ 实现：

    深度优先遍历

    1. #include 
    2. using namespace std;
    3.  
    4. class Solution {
    5. public:
    6.     int numIslands(vectorchar>>& grid) {
    7.         if(grid.empty() || grid[0].empty()) return 0;
    8.         
    9.         int count = 0;
    10.         for(int i = 0; i < grid.size(); ++i) {
    11.             for(int j = 0; j < grid[0].size(); ++j) {
    12.                 if(grid[i][j] == '1') {
    13.                     dfs(grid, i, j);
    14.                     ++count;
    15.                 }
    16.             }
    17.         }
    18.         
    19.         return count;
    20.     }
    21.     
    22.     void dfs(vectorchar>>& grid, int i, int j) {
    23.         if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0')
    24.             return;
    25.         
    26.         grid[i][j] = '0';
    27.         dfs(grid, i + 1, j);
    28.         dfs(grid, i - 1, j);
    29.         dfs(grid, i, j + 1);
    30.         dfs(grid, i, j - 1);
    31.     }
    32. };

    广度优先遍历

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. class Solution {
    6. public:
    7.     int numIslands(vectorchar>>& grid) {
    8.         if(grid.empty() || grid[0].empty()) return 0;
    9.         
    10.         int count = 0;
    11.         for(int i = 0; i < grid.size(); ++i) {
    12.             for(int j = 0; j < grid[0].size(); ++j) {
    13.                 if(grid[i][j] == '1') {
    14.                     bfs(grid, i, j);
    15.                     ++count;
    16.                 }
    17.             }
    18.         }
    19.         
    20.         return count;
    21.     }
    22.     
    23.     void bfs(vectorchar>>& grid, int i, int j) {
    24.         queueint, int>> q;
    25.         q.push({i, j});
    26.         grid[i][j] = '0';
    27.         
    28.         while(!q.empty()) {
    29.             auto [x, y] = q.front(); q.pop();
    30.             
    31.             if(x > 0 && grid[x - 1][y] == '1') {
    32.                 q.push({x - 1, y});
    33.                 grid[x - 1][y] = '0';
    34.             }
    35.             if(x < grid.size() - 1 && grid[x + 1][y] == '1') {
    36.                 q.push({x + 1, y});
    37.                 grid[x + 1][y] = '0';
    38.             }
    39.             if(y > 0 && grid[x][y - 1] == '1') {
    40.                 q.push({x, y - 1});
    41.                 grid[x][y - 1] = '0';
    42.             }
    43.             if(y < grid[0].size() - 1 && grid[x][y + 1] == '1') {
    44.                 q.push({x, y + 1});
    45.                 grid[x][y + 1] = '0';
    46.             }
    47.         }
    48.     }
    49. };

    Java 实现

    深度优先遍历

    1. class Solution {
    2.     public int numIslands(char[][] grid) {
    3.         if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    4.         
    5.         int count = 0;
    6.         for(int i = 0; i < grid.length; ++i) {
    7.             for(int j = 0; j < grid[0].length; ++j) {
    8.                 if(grid[i][j] == '1') {
    9.                     dfs(grid, i, j);
    10.                     ++count;
    11.                 }
    12.             }
    13.         }
    14.         
    15.         return count;
    16.     }
    17.     
    18.     void dfs(char[][] grid, int i, int j) {
    19.         if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
    20.             return;
    21.         
    22.         grid[i][j] = '0';
    23.         dfs(grid, i + 1, j);
    24.         dfs(grid, i - 1, j);
    25.         dfs(grid, i, j + 1);
    26.         dfs(grid, i, j - 1);
    27.     }
    28. }

     广度优先遍历

    1. import java.util.Queue;
    2. import java.util.LinkedList;
    3.  
    4. class Solution {
    5.     public int numIslands(char[][] grid) {
    6.         if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
    7.         
    8.         int count = 0;
    9.         for(int i = 0; i < grid.length; ++i) {
    10.             for(int j = 0; j < grid[0].length; ++j) {
    11.                 if(grid[i][j] == '1') {
    12.                     bfs(grid, i, j);
    13.                     ++count;
    14.                 }
    15.             }
    16.         }
    17.         
    18.         return count;
    19.     }
    20.     
    21.     void bfs(char[][] grid, int i, int j) {
    22.         Queue<int[]> q = new
    23.  
    24.  LinkedList<>();
    25.         q.add(new int[]{i, j});
    26.         grid[i][j] = '0';
    27.         
    28.         while(!q.isEmpty()) {
    29.             int[] cur = q.poll();
    30.             int x = cur[0], y = cur[1];
    31.             
    32.             if(x > 0 && grid[x - 1][y] == '1') {
    33.                 q.add(new int[]{x - 1, y});
    34.                 grid[x - 1][y] = '0';
    35.             }
    36.             if(x < grid.length - 1 && grid[x + 1][y] == '1') {
    37.                 q.add(new int[]{x + 1, y});
    38.                 grid[x + 1][y] = '0';
    39.             }
    40.             if(y > 0 && grid[x][y - 1] == '1') {
    41.                 q.add(new int[]{x, y - 1});
    42.                 grid[x][y - 1] = '0';
    43.             }
    44.             if(y < grid[0].length - 1 && grid[x][y + 1] == '1') {
    45.                 q.add(new int[]{x, y + 1});
    46.                 grid[x][y + 1] = '0';
    47.             }
    48.         }
    49.     }
    50. }

    C实现

    由于C语言编写会稍显复杂一些，这里简要描述一下步骤和关键实现：
    1. 用一个二维字符数组表示地图，用两重循环遍历地图上的每一点。
    2. 如果找到一个‘1’，就用深度优先遍历或者广度优先遍历将与它相连的所有‘1’都标记为‘0’，同时岛屿数量+1。
    3. 对于深度优先遍历，可以用递归实现。
    4. 对于广度优先遍历，可以用一个队列来保存待访问的点。

    mooc：陈越的问题

    1.出口定在哪里？

    在迷宫搜索问题中，深度优先搜索（DFS）和广度优先搜索（BFS）有不同的优势，这取决于迷宫的结构和出口的位置。

    1. 深度优先搜索（DFS）的优势:

      • 出口位于迷宫的边缘或角落：如果出口位于迷宫的边缘或一个远离起点的角落，DFS可能会更快找到它。这是因为DFS会深入探索一条路径直到尽头，所以如果正确的路径是深且直的，DFS可能会快速找到出口。
      • 迷宫路径很深：在复杂或深层的迷宫中，DFS可以快速深入到远处的区域。如果出口恰好在这样一个深处区域，DFS可能表现得更好。

    2. 广度优先搜索（BFS）的优势:

      • 出口位于迷宫的中心或靠近起点：如果出口位于迷宫的中心或相对靠近起点，BFS通常会更有效。BFS以起点为中心向外层层扩展，如果出口较近，它将更快被发现。
      • 迷宫路径较平坦或宽敞：在较少歧路或较宽敞的迷宫中，BFS通过其层级搜索能够更快地覆盖每一层的所有可能路径。

    理论上，两种算法都能找到出口，但在实际应用中，迷宫的具体布局和出口位置会影响它们的效率。DFS在深且直的路径中表现良好，而BFS在寻找最短路径和探索近处区域时更为高效。通常，在不了解迷宫具体信息的情况下，BFS更常被用于找到最短路径，而DFS在某些情况下因其内存使用较少而被选用。

    2.DFS和BFS的优缺点

    深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图和树搜索算法，各有其优缺点及适用场景。

    深度优先搜索（DFS）

    优点:

    1. 空间效率: DFS通常比BFS占用更少的内存，因为它不需要存储所有层的节点。在最坏情况下，它的空间复杂度为O(h)，其中h是图的最大深度。
    2. 找到解决方案的路径: 如果存在多个解决方案，DFS可能更快地找到一个解决方案（尽管这个解决方案不一定是最短的）。
    3. 简单性: 对于某些问题，如拓扑排序或检查循环，DFS的实现可能比BFS更直接和简单。

    缺点:

    1. 可能缺乏效率: 对于宽度较大的图，DFS可能花费很长时间探索不必要的分支。
    2. 不保证最短路径: 对于许多问题，DFS不能保证找到最短路径。
    3. 可能导致深度很深的递归: 这可能导致栈溢出等问题。

    适用场景:

    • 当空间是一个重要限制时（尤其是在大图中）。
    • 当目标节点预计会在离根较远的位置时。
    • 需要搜索全部或特定条件的解时，而不是最短路径。

    广度优先搜索（BFS）

    优点:

    1. 找到最短路径: 对于无权图，BFS能够保证找到从起点到目标的最短路径。
    2. 更快找到解决方案: 如果解决方案比较靠近根节点，BFS可能会比DFS更快地找到它。
    3. 适用性广: 对于许多问题，如寻找最短路径或层级遍历，BFS是一个自然且有效的选择。

    缺点:

    1. 空间效率: 对于宽度广泛的图，BFS可能需要大量内存来存储所有扩展出的节点。
    2. 可能慢于DFS: 在某些情况下，尤其是目标节点位于较深层时，BFS可能会比DFS慢。

    适用场景:

    • 当需要找到最短路径或离起点最近的解决方案时。
    • 当树或图的深度很大，或者解决方案可能在较浅层时。
    • 当内存不是主要瓶颈时。

    总结

    • 空间效率: DFS通常更有空间效率，尤其是在深度远大于宽度的图中。
    • 时间效率: 这取决于目标节点的位置和图的结构。在宽度较大的图中，DFS可能更快地到达深层节点；而在目标节点靠近起点的情况下，BFS可能更有效。
    • 选择算法: 如果问题需要最短路径或层级信息，BFS是首选。如果空间是限制，或者需要深入探索，DFS可能更合适。考虑特定问题的结构和需求来选择最适合的算法。

  • 相关阅读:
    【零基础入门】ACL访问控制列表
    万能的JSON解析方法，获取指定字段值
    批量处理长视频，提高视频制作效率的技巧分享
    计算机内功修炼：程序的机器级表示（C与汇编）
    OpenCV的二值化处理函数threshold()详解
    【fairseq】RuntimeError: Unrecognized tensor type ID: AutogradCUDA
    NuGet打包类库并上传教程
    SpringMVC13-注解配置SpringMVC
    centos下防火墙对指定ip开放端口权限
    STM32状态机编程实例——全自动洗衣机(下)
  • 原文地址：https://blog.csdn.net/tang7mj/article/details/133254744