深度优先搜索详解与代码实现

下载万磁搜索绿色版

有志者，事竟成！如果你在学习文章，那么本文《深度优先搜索详解及DFS代码实现》，就很适合你！文章讲解的知识点主要包括，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

DFS与BFS主要区别在于探索方式和数据结构：DFS用栈（或递归）实现深度优先，适合连通性、回溯等问题；BFS用队列实现广度优先，常用于找最短路径。

深度优先搜索（DFS）本质上是一种探索图或树结构的策略，它有点像你在一个巨大的迷宫里，选择一条路就一直走到底，直到无路可走才回头，然后尝试另一条未探索的路。它追求的是“深度”，优先探索一个分支的所有可能性。

想象一下，你站在一个岔路口，DFS会选择其中一条路径，然后沿着这条路径一直走下去，直到遇到死胡同或者已经走过的路。这时候，它会“回溯”到上一个岔路口，选择另一条还没走过的路继续深入。这个过程会一直重复，直到所有能走的路都走遍了。实现上，我们通常利用递归的特性来模拟这种“深入”和“回溯”，或者使用一个显式的栈来管理待访问的节点。关键在于，我们需要一个机制来记住哪些节点已经访问过，以免陷入无限循环。

DFS与广度优先搜索（BFS）的主要区别在哪里？

说起DFS，就不得不提它的“兄弟”——广度优先搜索（BFS）。这俩就像是两种截然不同的旅行方式。DFS是个“深度探险家”，一头扎进一个区域，不把这个区域的秘密挖完不罢休。而BFS则更像个“全面普查员”，它会先看看周围所有邻居，确认完第一圈，再去看第二圈的邻居。

技术上讲，最大的不同在于它们管理待访问节点的方式：DFS用的是栈（或递归调用的函数栈），后进先出，所以它总是往最深处走；BFS用的是队列，先进先出，所以它总是先处理“离起点近”的节点。这导致了它们在应用上的偏好：BFS常用来找最短路径（因为它是逐层探索的），而DFS则更擅长解决连通性、拓扑排序、以及一些回溯类问题。没有哪个更好，只有哪个更适合当前的问题。有时候，选择哪一个甚至能直接决定你的算法效率。

深度优先搜索在实际编程中通常有哪些应用场景？

DFS的应用范围其实非常广，远不止是教科书上的图遍历。在我看来，只要是涉及到“探索所有可能性”或者“沿着一条路径走到底”的场景，DFS都有用武之地。

最直观的当然是图和树的遍历，比如你想要访问一个树的所有节点，或者找出图中所有与某个节点连通的节点。再比如，路径查找，虽然不是最短路径，但如果你只是想知道A到B有没有路，DFS就能很快告诉你。

更复杂一点的，像检测图中的环，DFS在遍历时如果发现要访问的节点已经在当前递归路径上，那基本就是有环了。还有拓扑排序，对于有向无环图（DAG），DFS能帮助我们找到一个有效的任务执行顺序。

当然，最让我觉得DFS“性感”的，是它在回溯算法中的应用。像经典的N皇后问题、数独求解器、组合问题、排列问题，这些本质上都是在构建一个解决方案，每一步都尝试一个选择，如果发现此路不通就回溯到上一步，尝试另一个选择。DFS的递归特性完美契合了这种“尝试-回溯”的模式。

如何用Python实现一个典型的深度优先搜索？

实现DFS，通常有两种思路：递归和迭代。递归实现因为其简洁性，通常更受欢迎，也更能体现DFS的“深入”特性。迭代实现则更显式地使用了栈，对于某些场景（比如避免递归深度限制）会有优势。

这里我们以一个简单的图遍历为例，用邻接表表示图。

递归实现：

def dfs_recursive(graph, start_node, visited=None):
    if visited is None:
        visited = set() # 用集合存储已访问节点，查找效率高

    visited.add(start_node)
    print(start_node, end=' ') # 访问当前节点

    for neighbor in graph.get(start_node, []): # 遍历邻居
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 示例图 (邻接表表示)
# 1 -- 2
# |    |
# 3 -- 4
# |
# 5
graph_example = {
    '1': ['2', '3'],
    '2': ['1', '4'],
    '3': ['1', '4', '5'],
    '4': ['2', '3'],
    '5': ['3']
}

print("DFS递归遍历结果:")
dfs_recursive(graph_example, '1')
print("\n")

迭代实现（使用显式栈）：

def dfs_iterative(graph, start_node):
    visited = set()
    stack = [start_node] # 初始栈，放入起始节点

    while stack:
        current_node = stack.pop() # 弹出栈顶元素，即当前要访问的节点

        if current_node not in visited:
            visited.add(current_node)
            print(current_node, end=' ')

            # 将邻居节点（未访问过的）压入栈中
            # 注意：这里压入的顺序会影响访问顺序，通常是逆序压入以保持与递归相似的“左优先”
            # 或者按照你希望的顺序压入
            for neighbor in reversed(graph.get(current_node, [])): # 反转，使得栈顶是“最左”的邻居
                if neighbor not in visited:
                    stack.append(neighbor)

print("DFS迭代遍历结果:")
dfs_iterative(graph_example, '1')
print("\n")

无论是递归还是迭代，核心都是维护一个已访问集合，避免重复处理和死循环。选择哪种实现，更多时候取决于个人偏好和具体问题的约束（比如Python的默认递归深度限制）。

好了，本文到此结束，带大家了解了《深度优先搜索详解与代码实现》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！