图的遍历：DFS 与 BFS

概念

图的遍历是指从图中某一顶点出发，按某种策略访问图中所有顶点，且每个顶点只访问一次。

与树不同，图中可能存在回路，且图可能不连通，因此遍历必须带一个 visited[] 标记数组，否则会在环里打转。

两种基本策略：

	深度优先 DFS	广度优先 BFS
类比	树的先序遍历	树的层序遍历
辅助结构	栈（递归即栈）	队列
走法	一条路走到底，碰壁再回退	一层一层向外扩散
空间	O(n)（递归栈）	O(n)（队列）

一句话理解：DFS 是"不撞南墙不回头"，BFS 是"一圈一圈往外荡"。两者访问到的顶点集合完全相同，只是顺序不同。

原理

DFS：递归 + 回退

DFS(v):
    访问 v，visited[v] = true
    对 v 的每个邻接点 w：
        若 w 未被访问，递归 DFS(w)

递归本身就是栈：一路深入，走到无路可走就返回上一层，继续试探下一个邻接点。

BFS：队列 + 分层

BFS(v):
    visited[v] = true;  v 入队
    while 队列非空:
        u = 出队;  访问 u
        对 u 的每个邻接点 w：
            若 w 未被访问: visited[w] = true; w 入队

BFS 的队列保证"先被发现的顶点的邻接点先被访问"，于是产生了按距离分层的效果。

遍历完整图：外层循环

一次 DFS/BFS 只能走完一个连通分量。要遍历整个图，必须在外面套一层：

for 每个顶点 v:
    若 v 未访问:  从 v 出发做一次 DFS/BFS    /* 每调用一次，多一个连通分量 */

调用次数 = 连通分量数（无向图）。

时间复杂度

存储结构	DFS / BFS	原因
邻接矩阵	O(n²)	对每个顶点都要扫完整行（n 个元素），共 n 行
邻接表	O(n + e)	每个顶点入队/递归 1 次（n），每条边被检查 1 次（有向 e、无向 2e）

空间复杂度均为 O(n)：visited[] 加上递归栈或队列。

遍历序列的唯一性（易考点）

存储结构	表示是否唯一	遍历序列是否唯一
邻接矩阵	唯一	唯一
邻接表	不唯一（链表顺序随插入而变）	不唯一

考题若问"某图的 DFS 序列可能是"，答案往往不止一个；若明确给的是邻接矩阵，序列就唯一。

遍历生成树

遍历过程中"第一次到达某个顶点所经过的那条边"共 n − 1 条（连通图），它们与全部顶点构成一棵生成树：

• DFS 生成树：高度通常较大（一条链）；
• BFS 生成树：高度最小，等于从起点到其他点距离的最大值。

典型应用

应用	用谁	理由
无权图单源最短路径	BFS	BFS 天然按"距离起点的边数"分层
求连通分量 / 判两点是否可达	两者皆可	一次调用覆盖一个分量
判无向图是否有环	DFS	遇到已访问且不是当前顶点双亲的邻接点 → 有环
有向图拓扑排序	DFS	后序逆序即拓扑序列（见拓扑排序一章）
求割点、桥、强连通分量	DFS	需要 DFS 的时间戳（dfn/low）

示例

例：同一张图，DFS 与 BFS

沿用上一章的图（邻接表按顶点编号升序链接）：

[1] -> 2 -> 3
[2] -> 1 -> 4 -> 5
[3] -> 1 -> 5
[4] -> 2 -> 6
[5] -> 2 -> 3 -> 6
[6] -> 4 -> 5

从顶点 1 出发，分别写出 DFS 与 BFS 的访问序列，并给出各自的生成树。

完整推导过程：

     1 ──────── 2 ──────── 4
     │          │  ╲       │
     │          │    ╲     │
     │          │      ╲   │
     3 ──────── 5 ──────── 6

DFS（递归，邻接点按编号从小到大试探）：

1. 访问 1。邻接点 2 未访问 → 深入 2。
2. 访问 2。邻接点 1 已访问；4 未访问 → 深入 4。
3. 访问 4。邻接点 2 已访问；6 未访问 → 深入 6。
4. 访问 6。邻接点 4 已访问；5 未访问 → 深入 5。
5. 访问 5。邻接点 2 已访问；3 未访问 → 深入 3。
6. 访问 3。邻接点 1、5 都已访问 → 返回。层层回退，结束。

DFS 序列：1, 2, 4, 6, 5, 3

BFS（队列，先入先出）：

步	出队并访问	本轮入队
1	1	2, 3
2	2	4, 5（1 已访问）
3	3	无（1、5 都已标记，5 在第 2 步已入队）
4	4	6（2 已访问）
5	5	无（2、3、6 均已标记）
6	6	无

BFS 序列：1, 2, 3, 4, 5, 6

关键细节：第 2 步访问 2 时把 5 入了队，所以第 3 步访问 3 时发现 5 已经"被标记过"（visited 已置位），不再重复入队。这是保证每个顶点只入队一次、复杂度为 O(n+e) 的关键——入队时立刻置 visited，而不是出队时才置。

两棵生成树：

DFS 生成树（链状，高 6）        BFS 生成树（矮胖，高 4）
1                                    1
└─ 2                            ┌────┴────┐
   └─ 4                         2         3
      └─ 6                      ├─┐       │
         └─ 5                   4  5      6 ← 5 已在上一层
            └─ 3

BFS 生成树的边为 (1,2),(1,3),(2,4),(2,5),(3,6)——共 n − 1 = 5 条，树高 3（层数）小于 DFS 树的 6。BFS 树更矮，这正是它"最短路径"属性的体现。

BFS 求无权图最短路：上面 BFS 的层数就是各点到 1 的最短距离：d(1)=0，d(2)=d(3)=1，d(4)=d(5)=d(6)=2。

C 语言：邻接表上的 DFS 与 BFS

#include <stdio.h>
#include <stdlib.h>

#define MAXV 10

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct {
    int data;
    ArcNode *first;
} VNode;

VNode v[MAXV];
int n = 6, visited[MAXV];

/* 头插法加无向边，故链表顺序与输入顺序相反；本例输入时倒序给即可得到升序 */
void addEdge(int u, int v_) {
    ArcNode *a = (ArcNode *)malloc(sizeof(ArcNode));
    a->adjvex = v_; a->next = v[u].first; v[u].first = a;
    ArcNode *b = (ArcNode *)malloc(sizeof(ArcNode));
    b->adjvex = u;  b->next = v[v_].first; v[v_].first = b;
}

void DFS(int u) {
    visited[u] = 1;
    printf("%d ", v[u].data);
    for (ArcNode *p = v[u].first; p; p = p->next)
        if (!visited[p->adjvex]) DFS(p->adjvex);
}

void BFS(int s) {
    int q[MAXV], front = 0, rear = 0;
    visited[s] = 1; q[rear++] = s;          /* 入队即标记 */
    while (front < rear) {
        int u = q[front++];
        printf("%d ", v[u].data);
        for (ArcNode *p = v[u].first; p; p = p->next)
            if (!visited[p->adjvex]) {
                visited[p->adjvex] = 1;
                q[rear++] = p->adjvex;
            }
    }
}

void reset(void) { for (int i = 0; i < n; i++) visited[i] = 0; }

int main(void) {
    for (int i = 0; i < n; i++) { v[i].data = i + 1; v[i].first = NULL; }
    /* 顶点 0..5 对应 1..6；因采用头插法，按"邻接点降序"输入可使链表呈升序 */
    int E[][2] = {{4,5},{2,4},{3,5},{1,4},{0,2},{1,3},{0,1}};
    for (int i = 0; i < 7; i++) addEdge(E[i][0], E[i][1]);

    reset(); printf("DFS from 1: "); DFS(0); printf("\n");   /* 1 2 4 6 5 3 */
    reset(); printf("BFS from 1: "); BFS(0); printf("\n");   /* 1 2 3 4 5 6 */

    /* 统计连通分量数：外层调用次数 */
    reset();
    int comps = 0;
    for (int i = 0; i < n; i++)
        if (!visited[i]) { comps++; DFS(i); }
    printf("\n连通分量数 = %d\n", comps);                     /* 1 */
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

Python 对照

from collections import deque

g = {1: [2, 3], 2: [1, 4, 5], 3: [1, 5],
     4: [2, 6], 5: [2, 3, 6], 6: [4, 5]}

def dfs(g, s):
    visited, out = set(), []
    def go(u):
        visited.add(u); out.append(u)
        for v in g[u]:
            if v not in visited: go(v)
    go(s)
    return out

def bfs(g, s):
    visited = {s}
    q = deque([s]); out = []
    while q:
        u = q.popleft(); out.append(u)
        for v in g[u]:
            if v not in visited:
                visited.add(v); q.append(v)      # 入队即标记
    return out

def bfs_dist(g, s):
    """无权图单源最短距离"""
    dist = {s: 0}; q = deque([s])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in dist:
                dist[v] = dist[u] + 1; q.append(v)
    return dist

print("DFS from 1:", dfs(g, 1))          # [1, 2, 4, 6, 5, 3]
print("BFS from 1:", bfs(g, 1))          # [1, 2, 3, 4, 5, 6]
print("到 1 的最短距离:", bfs_dist(g, 1)) # {1:0, 2:1, 3:1, 4:2, 5:2, 6:2}

# 无向图判环：DFS 时遇到"已访问且不是双亲"的邻接点
def has_cycle(g):
    visited = set()
    def go(u, parent):
        visited.add(u)
        for v in g[u]:
            if v not in visited:
                if go(v, u): return True
            elif v != parent:
                return True
        return False
    for u in g:
        if u not in visited and go(u, None): return True
    return False
print("有环?", has_cycle(g))                          # True
print("树(无环)?", has_cycle({1:[2,3],2:[1],3:[1]}))  # False

# 连通分量数
def components(g):
    seen, c = set(), 0
    for u in g:
        if u not in seen:
            c += 1
            seen |= set(dfs(g, u))
    return c
print("连通分量数:", components(g))                    # 1

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

考点

考点

1. 必背结论

• 遍历必须带 visited[]，否则有环时死循环。
• 邻接矩阵上 DFS/BFS 均为 O(n²)；邻接表上均为 O(n + e)；空间 O(n)。
• 一次遍历只覆盖一个连通分量；外层循环调用次数 = 连通分量数。
• 连通图遍历产生 n − 1 条树边，构成生成树；BFS 树最矮，DFS 树偏高。
• 邻接矩阵表示唯一 → 遍历序列唯一；邻接表表示不唯一 → 序列不唯一。
• BFS 可求无权图的单源最短路径（层数即距离）。

2. 解题套路

• 手算 DFS：画递归树，"深入到底、碰壁回退"，回退后继续从下一个未访问邻接点深入，不要跳回起点。
• 手算 BFS：老老实实画队列，每出队一个就把它的未标记邻接点依次入队，入队时立刻标记。
• 判环（无向图）：DFS 时若遇到一个"已访问且不是当前顶点双亲"的邻接点 → 有环。注意双亲判断不可省，否则无向图每条边都会被误判成环。

3. 易错点

• BFS 中何时置 visited：必须在入队时置位。若等到出队时才置，同一个顶点可能被多个邻居重复入队，复杂度退化且序列出错。
• DFS 递归版在顶点数很大时可能爆栈，工程上要写非递归（显式栈）版本；考试一般不考非递归写法。
• 有向图的遍历不能用"双亲判断"来判环（那是无向图专属），有向图要用拓扑排序或 DFS 的回边（灰色结点）。
• 混淆"遍历序列"与"生成树边集"：序列是访问先后，树边只是其中"第一次到达"的那些边，回边不算树边。
• 复杂度里邻接表的 O(n + e)：无向图实际扫描 2e 个边结点，但仍记作 O(n+e)，常数 2 不影响渐进记号。
• 认为 DFS 也能量最短路。不能——DFS 找到的是"某条路径"，只有在无权图上用 BFS 才保证最短。

小结

• 图遍历靠 visited[] 防重复；DFS 用栈（递归）、BFS 用队列。
• 邻接矩阵 O(n²)、邻接表 O(n+e)；一次调用覆盖一个连通分量，外层循环次数即分量数。
• BFS 的层数 = 无权图最短距离；DFS 用于判环、拓扑排序等需要"回溯"的场景。
• 遍历序列在邻接表下不唯一，在邻接矩阵下唯一。
• 下一步：遍历是图算法的基础，把"生成树"加上权值最小化，就是最小生成树。

下一篇：最小生成树：Prim 与 Kruskal