图的遍历

从起点出发，沿边访问所有可达顶点，称为一次图遍历。有向图中只能沿边的方向走；无向图中只能到达起点所属的连通分量。若要访问整张图，需要对每个尚未访问的顶点重新发起搜索。

以下代码使用邻接表 adj，顶点编号为 0..n-1。

深度优先搜索

DFS 从当前顶点选择一个尚未访问的邻居继续搜索，直到无路可走再回溯。访问标记使每个顶点只展开一次，因此普通 DFS 不会枚举所有简单路径。

def dfs_order(adj, start):
    seen = [False] * len(adj)
    order = []

    def visit(u):
        seen[u] = True
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                visit(v)

    visit(start)
    return order

递归栈保存尚未结束的搜索过程，最深可达 $n$ 层。链状大图可能超过语言的递归深度限制，实际使用时可改为显式栈。

广度优先搜索

BFS 用队列维护待展开顶点。起点距离为 0，从距离为 $d$ 的顶点首次发现的邻居距离为 $d+1$。队列保证较近的顶点先被展开，因此第一次发现某顶点时，就确定了无权图中到它的最短距离。

from collections import deque

def bfs_distance(adj, start):
    dist = [-1] * len(adj)
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

访问标记在入队时设置，避免同一个顶点重复入队。返回值中的 -1 表示不可达。若边权不同，按边数分层不能直接得到最小权值路径。

复杂度与用途

使用邻接表时，两种遍历的时间复杂度都是 $O(n+m)$，辅助空间为 $O(n)$；邻接矩阵则需要 $O(n^2)$ 时间扫描邻接关系。DFS 的搜索树和完成顺序用于环检测、拓扑排序和强连通分量；BFS 的分层用于无权最短路和网络流。

例题

• 洛谷 P5318 查找文献
• 洛谷 P3916 图的遍历