图遍历算法

快速概览

图遍历算法是理解组装、路径查找和图清理的基础工具，从基础的DFS/BFS到复杂的Hamiltonian path问题，构成了图算法的核心。

• 重点理解DFS和BFS的差异，以及Hamiltonian path的NP难性质
• 图遍历算法在组装中用于路径恢复、错误检测和图简化

前置知识

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

图遍历算法是指系统地访问图中所有顶点和边的方法。在生物信息学中，特别是基因组组装中，图遍历算法用于：

• 在de Bruijn graph中寻找重建序列的路径
• 检测和清理图中的错误结构（tips、bubbles）
• 分析图的连通性和拓扑结构
• 解决路径搜索问题

为什么重要

在基因组组装中，图遍历算法的价值体现在：

• 路径恢复：从图中找到代表原始序列的路径
• 错误检测：通过遍历识别低频错误边和异常结构
• 图简化：通过遍历策略简化复杂图结构
• 复杂度理解：Hamiltonian path问题解释了为什么组装在理论上很难

基础遍历算法

深度优先搜索（DFS）与广度优先搜索（BFS）

DFS（深度优先）沿着一条路径走到黑再回溯，适合路径延伸；BFS（广度优先）逐层扩散，适合寻找最短路径和识别局部结构（如 Bubble）。

DFS

Depth-First Search，沿着一条路径尽可能深地搜索，遇到无法继续时回溯。

适用场景

寻找路径、检测环、拓扑排序。

实现方式

通常使用栈或递归实现。

算法描述

算法1：深度优先搜索

输入：图 G = (V, E)，起始顶点 s
输出：访问顺序

1. visited = ∅
2. stack = [s]
3. while stack 不为空:
   a. v = stack.pop()
   b. if v ∉ visited:
      - 将 v 加入 visited
      - for each 邻接顶点 u of v:
         if u ∉ visited:
           stack.push(u)
4. return visited

时间复杂度：$O(|V| + |E|)$

空间复杂度：$O(|V|)$

在组装中的应用

• 路径延伸：从某个顶点开始，沿着一条路径尽可能延伸
• 环检测：检测图中是否存在环（重复序列可能导致）
• 连通分量分析：识别图中的连通分量

广度优先搜索（BFS）

BFS

Breadth-First Search，逐层访问顶点，先访问所有邻接顶点，再访问邻接的邻接。

适用场景

最短路径、层次遍历、可达性分析。

实现方式

通常使用队列实现。

算法描述

算法2：广度优先搜索

输入：图 G = (V, E)，起始顶点 s
输出：访问顺序

1. visited = ∅
2. queue = [s]
3. while queue 不为空:
   a. v = queue.dequeue()
   b. if v ∉ visited:
      - 将 v 加入 visited
      - for each 邻接顶点 u of v:
         if u ∉ visited:
           queue.enqueue(u)
4. return visited

时间复杂度：$O(|V| + |E|)$

空间复杂度：$O(|V|)$

在组装中的应用

• 最短路径：在图中寻找两点间的最短路径
• 层次分析：分析图的层次结构
• 可达性：判断某个顶点是否可以从另一个顶点到达

Hamiltonian Path

Hamiltonian path

访问图中每个顶点恰好一次的路径。

Hamiltonian cycle

访问图中每个顶点恰好一次并回到起点的环。

复杂度

Hamiltonian path问题是NP完全问题，没有已知的多项式时间算法。

为什么重要

在基因组组装中：

• 理想情况下，我们希望找到一条Hamiltonian path来重建序列
• 但由于NP难性质，实际组装器使用启发式方法
• 这解释了为什么组装问题在理论上很难

与Eulerian Path的区别

维度	Eulerian Path	Hamiltonian Path
定义	访问每条边恰好一次	访问每个顶点恰好一次
复杂度	多项式时间可解	NP完全
组装应用	de Bruijn graph的路径问题	OLC组装的路径问题
判断条件	基于顶点度数	无简单判断条件

算法描述

由于Hamiltonian path是NP完全问题，通常使用回溯或启发式方法：

算法3：回溯法寻找Hamiltonian path

输入：图 G = (V, E)
输出：Hamiltonian path（如果存在）

1. path = []
2. visited = ∅
3. function backtrack(current_vertex):
   a. 将 current_vertex 加入 path 和 visited
   b. if |path| == |V|:
      return path  // 找到Hamiltonian path
   c. for each 邻接顶点 u of current_vertex:
      if u ∉ visited:
         result = backtrack(u)
         if result ≠ null:
           return result
   d. 将 current_vertex 从 path 和 visited 中移除
   e. return null

4. for each vertex v in V:
   result = backtrack(v)
   if result ≠ null:
     return result
5. return null  // 不存在Hamiltonian path

时间复杂度：最坏情况 $O(|V|!)$

空间复杂度：$O(|V|)$

示例

考虑图：

A -- B -- C
|         |
D -------- E

寻找Hamiltonian path：

1. 从A开始：A → B → C → E → D（成功）
2. 或者：D → A → B → C → E（成功）

这个图存在Hamiltonian path。

贪心路径延伸

由于Hamiltonian path太复杂，实际组装器使用贪心策略：

算法4：贪心路径延伸

输入：图 G = (V, E)，边权重 w（coverage）
输出：路径集合

1. paths = []
2. visited_edges = ∅
3. while 存在未访问边:
   a. 选择权重最大的未访问边（u, v） 作为起点
   b. path = [u, v]
   c. 标记（u, v） 为已访问
   d. current = v
   e. while current 有未访问出边:
      - 选择权重最大的未访问出边（current, next）
      - if next ∈ path:
         * 停止当前路径延伸（避免环）
      - else:
         * 将 next 加入 path
         * 标记（current, next） 为已访问
         * current = next
   f. 将 path 加入 paths
4. return paths

时间复杂度：$O(|E| \log |E|)$，如果使用优先队列

空间复杂度：$O(|V| + |E|)$

图清理中的遍历策略

Tip检测与清理

Tips是图中的短分支，通常由测序错误引起：

算法5：Tip检测

输入：图 G = (V, E)，最小路径长度 L，最大路径长度 U
输出：所有tips

1. tips = []
2. for each 顶点 v in V:
   a. if out_degree(v) == 0 or in_degree(v) == 0:
      path = [v]
      current = v
      while len(path) < U:
         if out_degree(current) == 1:
           next = 唯一出边邻居
           path.append(next)
           current = next
         else:
           break
      if L ≤ len(path) ≤ U:
         tips.append(path)
3. return tips

Bubble检测与清理

Bubbles是图中的平行路径，通常由重复序列或变异引起：

算法6：Bubble检测

输入：图 G = (V, E)，起点 s，终点 t
输出：s和t之间的所有路径

1. paths = []
2. function dfs(current, path):
   a. path.append(current)
   b. if current == t:
      paths.append(path.copy())
   c. else:
      for each 邻接顶点 u of current:
         if u not in path:
           dfs(u, path)
   d. path.pop()

3. dfs(s, [])
4. return paths

复杂度分析

算法	时间复杂度	空间复杂度	适用场景
DFS	$O(	V	+
BFS	$O(	V	+
Hamiltonian Path（回溯）	$O(	V	!)$
贪心路径延伸	$O(	E	\log

在生物信息学中的位置

图遍历算法在生物信息学中的核心应用：

• de Bruijn graph组装：使用DFS/BFS进行路径延伸和图清理
• OLC组装：Hamiltonian path问题的启发式求解
• 错误检测：通过遍历识别异常结构
• 图简化：使用遍历策略简化复杂图结构

常见误区

• Hamiltonian path是组装的唯一解：
• 不是。由于NP难性质，实际组装器使用启发式方法，不一定找到Hamiltonian path，而是找到"足够好"的路径。
• DFS总是比BFS好：
• 不是。DFS和BFS各有优势：
• DFS适合寻找路径和检测环
• BFS适合寻找最短路径和层次分析

参考资料

• Cormen, T. H., et al. Introduction to Algorithms, Chapters 22-23
• West, D. B. Introduction to Graph Theory
• Pevzner, P. A., et al. (2001). “An Eulerian path approach to DNA fragment assembly”

相关页面

• de Bruijn graph组装
• OLC：Overlap-Layout-Consensus
• 重复序列、分叉与图清理
• 概率、图与动态规划预备

de Bruijn graph 组装

基于 k-mer 与 de Bruijn 图的组装方法

延伸阅读

OLC：Overlap-Layout-Consensus

基于重叠关系的经典组装范式

延伸阅读

重复序列、分叉与图清理

图清理策略在组装中的应用

延伸阅读

概率、图与动态规划预备

图论基础概念与算法预备知识

延伸阅读

测序杂交（SBH）

欧拉路径问题在测序中的经典应用

延伸阅读