图算法

首先明确图的性质：有向还是无向、加权还是无权、稀疏还是稠密，以及是否可能存在负权边或环。随后明确输出目标——可达性、一条路径、所有距离，还是一个连接子图。

决策地图

问题	条件	算法	常见表示下的时间
可达性／结构	一般邻接表	DFS 或 BFS	$O(V+E)$
最少边数路径	无权／各边成本相同	BFS	$O(V+E)$
单源最短路径	权重非负	Dijkstra	$O((V+E)\log V)$
单源最短路径	允许负权边	Bellman–Ford	$O(VE)$
所有点对最短路径	稠密图或较小的 $V$	Floyd–Warshall	$O(V^3)$
最小生成树	加权无向图	Prim	$O(E\log V)$
最小生成树	可排序的边表	Kruskal	$O(E\log E)$

最短路径树最小化从源点到各顶点的距离；最小生成树最小化连接所有顶点所需的总权重。即使 Dijkstra 和 Prim 都使用优先队列，这两个目标也互不蕴含。

邻接表占用 $O(V+E)$ 存储空间，适合稀疏图。邻接矩阵占用 $O(V^2)$ 空间，能以常数时间查询边，并可简化稠密图上的所有点对算法。若不说明表示方式，复杂度结论是不完整的。

V 包含孤立顶点，E 表示边数（无向邻接表每条边存两项）。表中的堆时间界使用简单图假设；多重图的惰性堆可能需要把 log V 改为 log E。E 为零或孤立点很多时，也要计入 O(V) 初始化。BFS 对等权且非负的边给出最小总成本，负权不适用。

没有边不等于存在零权边。不可达距离记为无穷大，并区分“没有路径”和源点到自身的零长度路径。负环只有在源点能到达它、它又能到达终点时才影响该查询。无向图求最短游走时，一条可达负边就允许来回走出任意小的成本；MST 输出无环，不受此问题影响。

例如三角形 A—B:2、B—C:2、A—C:3，MST 总成本为 4，但其中 A 到 C 的树上路径成本是 4，不是真正最短距离 3。以 A 为根的最短路径树总成本则为 5。

探索关联