核心要点

  • BFS 用队列逐层向外扩展，天然适合无权图的最短路径（边数最少）

  • DFS 用递归或显式栈一路深入，适合连通性、拓扑排序、找所有路径

  • 都要用 visited 集合防止重复访问；邻接表存图，复杂度 O(V+E)

标准回答

图遍历有广度优先（BFS）和深度优先（DFS）两种。BFS 用队列，从起点开始逐层把邻居入队再出队，由于按距离一层层扩展，在无权图中第一次到达某点时的层数就是最短路径长度。DFS 用递归或栈，沿一条路径尽量深入，回退后再探其他分支，适合判连通、找环、拓扑排序。两者都用邻接表存图、用 visited 防止重复访问，时间复杂度都是 O(V+E)。下面给出 BFS 求无权图最短路（步数）和 DFS 遍历：

python
from collections import deque


def bfs_shortest_path(graph, start, target):
    # 无权图最短路：BFS 逐层扩展，记录到每个点的距离
    visited = {start}
    q = deque([(start, 0)])              # (节点, 到起点的步数)
    while q:
        node, dist = q.popleft()
        if node == target:
            return dist                  # 第一次到达即最短
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)         # 入队即标记，避免重复入队
                q.append((nxt, dist + 1))
    return -1                            # 不可达


def dfs(graph, start):
    # 深度优先遍历，返回访问顺序
    visited = []
    seen = set()
    def go(node):
        seen.add(node)
        visited.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                go(nxt)
    go(start)
    return visited


if __name__ == '__main__':
    # 邻接表表示的无向图
    g = {
        'A': ['B', 'C'],
        'B': ['A', 'D'],
        'C': ['A', 'D'],
        'D': ['B', 'C', 'E'],
        'E': ['D'],
    }
    print(bfs_shortest_path(g, 'A', 'E'))  # 3 (A->B->D->E)
    print(dfs(g, 'A'))                      # ['A', 'B', 'D', 'C', 'E']

常见误区

⚠️ 常见踩坑

BFS 求最短路要在「入队时」标记 visited，而非出队时，否则同一节点会被多次入队导致重复甚至错误；带权图最短路不能用普通 BFS，要用 Dijkstra（优先队列）。

追问

追问 1：BFS 和 DFS 的复杂度各是多少？

用邻接表时两者时间都是 O(V+E)：每个顶点入队/递归一次，每条边检查一次。空间上 BFS 队列最坏 O(V)，DFS 递归栈最坏 O(V)（退化为链时）。

追问 2：带权图求最短路该用什么算法？

非负权用 Dijkstra（最小堆优先队列，O((V+E)log V)）；有负权边用 Bellman-Ford（O(VE)，可检测负环）；多源最短路用 Floyd-Warshall（O(V³)）。普通 BFS 只在边权全相等（即无权）时给出最短路。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题