相比于树结构的遍历，图的遍历要复杂得多，因为图中的任何一个节点都可能与其它所有节点相邻接。这就意味着，在访问了某个节点之后，可能会顺着某条路径再次返回到这个节点。为了防止对节点进行重复访问，在图的遍历过程中需要记录下已经访问过的节点。深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历方法。

图的遍历图解

深度优先

广度优先

一、深度优先遍历是什么？

深度优先遍历（Depth-First Search, DFS）是一种用于遍历或搜索树或图结构的算法。深度优先遍历的基本思想是从根节点（或任意一个节点）开始，沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯到上一个分叉点，再尝试其他可能的路径。这个过程一直进行，直到所有的节点都被访问过。举一个简单的列子，就是一条路走到黑，不撞南墙你不回头。

二、深度优先遍历的原理

我们可以将其比作一场寻宝游戏。想象一下，你站在一片未知的土地上，目标是找到隐藏的宝藏。你会选择一条路径前进，直到遇到岔路口。此时，你会如何选择？深度优先遍历是让你选择其中一条路走到尽头，如果发现没有宝藏，就返回到刚刚遇到的岔路口，尝试其他的路径。这个过程会一直重复，直到所有的路径都被探索过。

三、深度优先遍历的实现

1.递归实现

在递归实现中，算法首先访问当前节点，然后递归地访问其子节点。如果一个节点没有子节点或所有子节点都已被访问，算法将回溯到该节点的父节点，并尝试访问其他分支，关键代码（C语言）如下：


void dfs(int node) {
    visited[node] = 1;
    printf("访问节点 %d", node);
    for (int i = 0; i < num_nodes; i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

下面是对代码的详细解释：
1.void dfs(int node)定义了一个名为 `dfs` 的函数，它接受一个整数参数 `node`，表示当前访问的节点。
2. visited[node] = 1;将当前节点标记为已访问。这是为了避免重复访问同一个节点。
3. printf("访问节点 %d", node);打印当前访问的节点编号。
4. for (int i = 0; i < num_nodes; i++) { ... }使用 for 循环遍历所有节点。`num_nodes` 表示图中节点的数量。
5. if (graph[node][i] == 1 && !visited[i]) { ... } 判断当前节点 `node` 与节点 `i` 之间是否存在边，并且节点 `i` 是否未被访问过。如果满足条件，则执行下一步。
6.dfs(i);递归调用 `dfs` 函数，以节点 `i` 作为新的当前节点进行深度优先遍历。
在每次递归调用中，都会访问一个新的节点，并将其标记为已访问。然后，继续递归地访问与该节点相邻的未访问过的节点，直到所有可达的节点都被访问过为止。

2.栈实现

我们可以使用栈来存储待访问的节点。每次从栈中弹出一个节点进行处理，并将其未访问的邻居节点压入栈中，直到栈为空，关键代码（Java）如下：


import java.util.Stack;
public class DFS {
    private Stack<Integer> stack;
    public DFS() {
        stack = new Stack<>();
    }
    public void dfs(int[][] graph, int start) {
        boolean[] visited = new boolean[graph.length];
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                visited[node] = true;
                System.out.println("访问节点：" + node);
                for (int i = 0; i < graph[node].length; i++) {
                    if (graph[node][i] == 1 && !visited[i]) {
                        stack.push(i);
                    }
                }
            }
        }
    }
}

下面是对代码的详细解释：
1. 定义一个栈`stack`，用于存储待访问的节点。
2. 定义一个构造函数`DFS()`，初始化栈。
3. 定义一个`dfs()`方法，接收一个邻接矩阵`graph`表示图的结构，以及一个起始节点`start`。
4. 在`dfs()`方法中，首先定义一个布尔数组`visited`，用于记录每个节点是否被访问过，初始值都为`false`。
5. 将起始节点`start`压入栈中。
6. 进入循环，当栈不为空时，执行以下操作：
   a. 弹出栈顶元素，即当前要访问的节点`node`。
   b. 如果该节点`node`未被访问过，则将其标记为已访问，并输出访问信息。
   c. 遍历与该节点相邻的所有节点，如果相邻节点未被访问过且与当前节点有边相连（即`graph[node][i] == 1`），则将相邻节点压入栈中。
7. 循环结束后，所有可达节点都已访问过，遍历结束。

四、广度优先遍历是什么？

广度优先遍历（Breadth-First Search, BFS）是一种用于遍历或搜索树或图结构的算法。与深度优先遍历不同的是，广度优先遍历是从某个顶点出发，逐层向外探索，直到所有相通的顶点都被访问为止。

五、广度优先遍历的原理

广度优先遍历通常使用队列这种数据结构来实现。队列遵循“先进先出”的规则，这与广度优先遍历的“逐层推进”规则相契合，BFS使用队列这种数据结构来存储待访问的节点。在遍历过程中，首先访问起始节点，然后将其邻接节点加入队列。之后，从队列中取出节点并访问其邻接节点，重复这一过程直到队列为空。

六、广度优先遍历的实现


    public static void bfs(Map<Character, List<Character>> graph, char start) {
    Set<Character> visited = new HashSet<>();  // 用于记录已访问的节点
    Queue<Character> queue = new LinkedList<>();  // 使用队列存储待访问的节点
    queue.add(start);
    visited.add(start);
    while (!queue.isEmpty()) {
        char vertex = queue.poll();  // 取出队列中的第一个节点
        System.out.print(vertex + " ");  // 访问该节点
        // 将邻接节点加入队列
        for (char neighbor : graph.get(vertex)) {
            if (!visited.contains(neighbor)) {
                queue.add(neighbor);
                visited.add(neighbor);
            }
        }
    }
}

我们使用了一个队列来存储待访问的节点，并使用一个集合来记录已访问过的节点。当队列不为空时，我们从队列中取出一个节点并访问它，然后将它的邻接节点加入队列。这个过程一直重复，直到队列为空。

总结

DFS更适合深入挖掘问题的解决方案，而BFS则适用于逐层分析问题，寻找最短路径或按层次顺序进行操作。

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