图的遍历——深度优先搜索【图】

深度优先搜索（Depth First Search，DFS）是一种常见的图遍历算法，它可以用于回溯和寻找图中的连通分量。

算法步骤：

1. 从起始节点开始遍历图，标记该节点为已访问。
2. 访问当前节点的邻接节点中未被访问过的节点，标记它们为已访问，递归访问它们的邻接节点。
3. 当前节点的所有邻接节点都被访问过后，回溯到上一个节点，继续访问未被访问过的邻接节点。

深度优先搜索可以用递归或栈（Stack）来实现。以下是使用递归实现深度优先搜索的示例代码：

visited = set()  # 已访问的节点集合

def dfs(node):
    visited.add(node)  # 将当前节点标记为已访问
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor)  # 递归访问邻接节点

其中，`node.neighbors` 表示节点 `node` 的所有邻接节点。

深度优先搜索的时间复杂度为 $O(V+E)$，其中 $V$ 是节点数，$E$ 是边数。

相关问题

算法7-4,7-5：图的遍历——深度优先搜索

### 回答1：
算法7-4：深度优先搜索

1. 从起点开始，将其标记为已访问。
2. 对于起点的每个未访问的邻居，递归地执行步骤1-2。
3. 重复步骤2，直到没有未访问的邻居。

算法7-5：深度优先搜索（非递归）

1. 从起点开始，将其标记为已访问，并将其压入栈中。
2. 当栈不为空时，弹出栈顶元素，并对其每个未访问的邻居执行步骤1-2，并将其标记为已访问并压入栈中。
3. 重复步骤2，直到栈为空。

### 回答2：
一、定义

深度优先搜索（Depth First Search，DFS）是图论中的基本算法，是从图的某个节点出发，访问这个节点，然后依次访问这个节点的每个未被访问的邻居节点，直至遍历完整个图。

二、实现

深度优先搜索可以通过递归或栈的方式实现。递归实现简单，但难以控制递归深度，容易发生栈溢出。栈的实现需要手动模拟栈，但可以灵活控制深度，避免栈溢出。

递归实现：

1.从某个节点v开始遍历。

2.标记该节点v为已访问。

3.对于v的每个未被访问的邻居节点w，递归访问w。

栈实现：

1.从某个节点v开始遍历。

2.将v入栈，并标记v为已访问。

3.当栈非空时循环执行以下步骤：弹出栈顶节点u，对于u的每个未被访问的邻居节点w，将w入栈并标记w为已访问。

三、应用

深度优先搜索可以用来判断图是否连通，可用于求解最小生成树、拓扑排序、连通分量等问题。

由于深度优先搜索需要存储所有已访问节点的路径，所以针对大规模图的遍历可能导致空间复杂度较高。

四、算法7-4，7-5代码分析

算法7-4：

算法7-4是对图的深度优先遍历的递归实现。首先遍历该节点，并标记为已访问，然后将该节点的所有邻居节点都遍历一遍。如果邻居节点未被访问，则对该节点进行递归调用进行遍历。

具体思路：

1.定义全局vis数组，用于记录节点是否已被访问。

2.定义一个函数dfs(u)，对节点u进行深度优先遍历。遍历完u的所有邻居节点后，会回溯到该节点u的上一个节点。

3.主函数遍历所有节点，对未被访问的节点进行深度优先遍历。

算法7-5：

算法7-5是对图的深度优先遍历的栈实现。使用了一个栈来存储待访问节点。首先将初始节点加入栈中，并标记为已访问，然后循环遍历栈中的节点，直至栈为空。

具体思路：

1.定义全局vis数组，用于记录节点是否已被访问。

2.定义一个函数dfs(u)，对节点u进行深度优先遍历。遍历完u的所有邻居节点后，会回溯到该节点u的上一个节点。

3.主函数遍历所有节点，对未被访问的节点进行深度优先遍历。在遍历到未被访问的节点时，加入栈中并标记为已访问，然后循环遍历栈中的节点，直至栈为空。

### 回答3：
算法7-4，7-5是关于图的遍历中的深度优先搜索（DFS），主要是用来搜索和遍历图中所有的节点和边的算法。

深度优先搜索的核心思想是：从一个未访问的节点开始，深度优先遍历到最深处，然后回溯到上一个节点，再从上一个未遍历节点开始继续深度优先遍历。在具体实现过程中，我们可以使用递归或栈来实现深度优先搜索算法。

深度优先搜索算法在图的遍历、搜索、路径查找等方面有着广泛的应用，如迷宫问题、拓扑排序、关键路径等。

在算法7-4中，我们给出了使用递归实现深度优先搜索的伪代码：

void DFS(int u) {
    vis[u] = true; // 标记已经访问过
    // 遍历所有邻接节点
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i]; // 取出邻接节点
        if (!vis[v]) {
            DFS(v); // 继续遍历
        }
    }
}

而在算法7-5中，我们使用栈来实现深度优先搜索，具体实现过程如下：

void DFS(int u) {
    stack<int> s; // 定义一个栈
    s.push(u); // 将起始节点放入栈中
    vis[u] = true; // 标记已经访问过

    while (!s.empty()) {
        int v = s.top(); // 取出栈顶节点
        s.pop(); // 将该节点出栈
        // 遍历所有邻接节点
        for (int i = 0; i < G[v].size(); i++) {
            int w = G[v][i]; // 取出邻接节点
            if (!vis[w]) {
                s.push(w); // 将未访问节点放入栈中
                vis[w] = true; // 标记已访问
            }
        }
    }
}

总之，深度优先搜索算法是一种基本的图遍历算法，其核心思想和实现方法都比较简单，但是能够灵活应用在众多图相关的算法问题中。

AI数据结构与算法——深度优先搜索与广度优先搜索

深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）都是图搜索算法，用于遍历或搜索图中的节点。

DFS是一种递归算法，从起始节点开始，依次遍历所有相邻的节点，直到找到目标节点或遍历完整个图。如果一个节点有多个相邻节点，会优先遍历其中一个节点，直到不能继续遍历为止，然后回溯到上一个节点，继续遍历它的其他相邻节点。DFS的实现可以使用栈来保存遍历的节点。

BFS是一种迭代算法，从起始节点开始，依次遍历所有与它距离为1的节点，然后遍历与起始节点距离为2的节点，以此类推，直到找到目标节点或遍历完整个图。BFS的实现可以使用队列来保存遍历的节点。

在实际应用中，DFS的空间复杂度较低，但可能会导致遍历到目标节点的时间较长；而BFS的空间复杂度较高，但能够保证找到最短路径。具体选择哪种算法，需要根据具体的问题和需求来决定。