深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它从一个节点开始，尽可能深地搜索图的分支。当节点v的邻接点都已被访问后，回溯到发现节点v的那条边的起始点。这一过程一直进行到已发现从源节点可达的所有节点为止。 在编程实现中，我们通常使用递归和栈来实现深度优先搜索。递归函数会检查每个可能的路径，直到找到目标节点或者没有其他路径可以走为止。每次调用递归函数时，都会将当前节点压入栈中，以便稍后使用。这样，我们可以确保在回溯时能够准确地回到之前访问过的节点。

它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还有未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

在实际应用中，DFS可以用于解决许多问题，例如寻找图中的连通分量、检测图中的环、拓扑排序等。

本文将通过递归和栈两种方式来实现DFS算法，并应用于无向图的遍历。

1. 递归实现DFS。

在这种方法中，我们使用函数自身来模拟栈的行为。

每次调用函数时，我们都将当前节点标记为已访问，然后递归地访问其所有未被访问的邻居。

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 访问节点
    for next in graph[start] - visited:
        dfs_recursive(graph, next, visited)
    return visited

# 示例图的邻接表表示
graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

# 从节点'A'开始递归DFS
dfs_recursive(graph, 'A')

首先访问节点'A'，然后递归地访问它的邻居'B'和'C'。

对于每个邻居，我们继续递归地访问它们的未访问邻居，直到所有节点都被访问。

2. 栈实现DFS。

为了避免这种情况，我们可以使用显式的栈来模拟递归过程。

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 访问节点
            stack.extend(graph[vertex] - visited)
    return visited

# 从节点'A'开始使用栈进行DFS
dfs_stack(graph, 'A')

初始时，栈中只有起始节点。

在每一步中，我们从栈中弹出一个节点，访问它，并将其所有未访问的邻居添加到栈中。

这个过程重复进行，直到栈为空。

3. DFS的应用实例。

以下是一些实际应用场景： - #路径查找#：在迷宫或地图中找到从起点到终点的路径。

- #连通分量#：在社交网络中找到所有相互连接的用户群体。

- #拓扑排序#：在有向无环图（DAG）中找到顶点的线性排序，使得对于每条有向边uv，顶点u在排序中出现在顶点v之前。

- #强连通分量#：在有向图中找到所有强连通子图。

4. 总结。

递归方法简洁直观，但可能在处理大图时遇到栈溢出问题；而使用显式栈的方法则更加健壮，适用于大规模图的处理。

DFS在实际应用中具有广泛的用途，包括路径查找、连通分量检测、拓扑排序等。

通过理解和掌握DFS，我们可以有效地解决许多复杂的图论问题。

深度优先搜索（DFS）与图遍历代码实现 - 集智数据集