图与最短路径的生信入门

更新：2026-10-26；状态：可用；验证范围：2026-10-26核对原始与官方资料；本页Python微型计算已执行；人工数据不代表专业软件或真实研究性能。

图由节点和边构成，适合表达“谁与谁连接”，例如工作流依赖、序列片段连接、单细胞近邻和相互作用网络。最短路径则需要先定义“短”：边数少、总权重小或生物代价低并不是同一任务。读完应能建立邻接表、手动执行BFS，并判断算法适用条件。

前置是列表、字典和队列，参见算法输入输出复杂度与数据结构。本页只实现无权图的广度优先搜索，不把“几条边”解释成真实遗传距离。

先把节点和边说清楚

对象	节点	边	不能忽略的条件
工作流	任务	必须先完成	有向、应无环
de Bruijn图	一种表示中为(k−1)-mer	k-mer连接	重复、覆盖度、分叉
细胞近邻图	细胞	高维邻近关系	距离、k、批次、权重
蛋白网络	蛋白	实验或计算关联	证据类型与置信度

有向边A→B不自动意味着B→A；无向图邻接表通常需要双向记录。无边节点也属于输入，不能因没有邻居就在分析前静默丢弃。路径的意义由建图规则决定，网络布局图上画得近不等于图距离短。

BFS为什么找到最少边路径

从起点s开始，先访问距离0的节点，再通过队列依次展开距离1、2等各层。节点第一次入队时就记录距离并标记已发现；否则带环图会反复入队。假设每条边代价都是1，首次发现节点时不存在尚未处理的更短路径，因而得到最少边数。

邻接表实现访问每个可达节点和相应边一次，时间O(V+E)，额外存储O(V)。它不会访问不可达节点。带非负不同权重时应考虑Dijkstra；允许负边时需别的算法与负环检查。参考MIT算法课程的图与最短路径部分。

跟着队列走一遍

设A连向B和C，B连向D，C也连向D，D连回A，还有独立Z。队列先为[A]；展开A后变[B,C]；展开B发现D，队列[C,D]；展开C不会再加入D。最终A=0、B=C=1、D=2，Z不可达。D的前驱可能随同层访问顺序改变，但最短距离仍为2。

本页例子在项目根目录的Python中运行；标准库例子无需安装包，含NumPy/SciPy的例子先按R包Python包与可复现环境建立项目环境。Windows命令使用python，macOS/Linux可使用python3；代码块可复制进该环境的Python交互会话，或保存为项目根目录下的临时脚本再用该环境解释器运行；不要保存到examples目录或任意外部目录后假定项目导入路径仍相同。除特别说明外，只向屏幕输出，不写文件。

from collections import deque
graph = {'A':['B','C'], 'B':['D'], 'C':['D'], 'D':['A'], 'Z':[]}
distance, parent, queue = {'A':0}, {'A':None}, deque(['A'])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in distance:
            distance[neighbor] = distance[node] + 1
            parent[neighbor] = node
            queue.append(neighbor)
print('distances', sorted(distance.items()))
print('unreachable', sorted(set(graph) - set(distance)))
assert distance['D'] == 2 and 'Z' not in distance

输出A0、B1、C1、D2以及不可达Z；程序正常结束，说明已发现标记阻止了环的无限展开。可沿parent从D回到A恢复一条路径，再反转。真实图若允许邻接表只列起点，应先补全所有被引用节点；这里显式列全了。

两个常见误用

第一，把无权BFS用于带权距离。若A→B权10、A→C权1、C→B权1，最少边路径A→B成本10，总权重最小路径却为A→C→B成本2。第二，把图连通当成生物因果。细胞近邻受特征选择、降维和参数影响；蛋白网络的一条路径也不证明调控链。

工作流还需要拓扑排序：输出满足所有依赖顺序的节点序列，有环时不存在合法拓扑序。拓扑排序、最短路径和遍历回答不同问题，不能因都使用队列而互换。

排错与自测

症状	检查	处理
队列越来越大	是否首次入队即标记	使用visited或distance
缺少孤立节点	是否只从边生成节点	单独维护完整节点集合
最短距离与手算不符	方向、权重、起点定义	先在三节点反例上核对
工作流无法排序	是否存在依赖环	输出环涉及的任务再修依赖

问：D不可达时应给距离0吗？ 答：不应。0表示起点，未知或无穷距离必须另标。问：同一节点有两条最短路径，BFS错了吗？ 答：没有；若要所有最短路径，需要保存多个前驱或额外统计，而非把一条parent当作全部答案。向专业场景延伸见单细胞降维邻居图与聚类原理。

接着读什么

算法输入输出复杂度与数据结构 → 单细胞降维邻居图与聚类原理 → R包Python包与可复现环境 → 基础算法可复现练习 → 方法与算法系统学习指南。学习顺序与练习入口见方法与算法系统学习指南。

运行本页的完整小例

先下载项目并进入含README与examples的根目录，环境准备见方法与算法系统学习指南。用项目环境的Python运行以下命令（macOS/Linux路径示例；Windows用.venv\Scripts\python.exe）：

.venv/bin/python examples/methods_foundations_demo.py --case bfs --output examples/output/methods-bfs

输出summary.json保存本页计算与检查结果。目录非空时拒绝覆盖，再练习请更换--output目录；页面内短代码只打印结果。标准库case也可用系统Python直接运行。

公式里的矩阵、下标或对数不熟时，可回查读懂方法公式的最小数学基础。