常用图论算法整理

Dijkstra 算法

解决单源最短路径问题，注意图中不能有负权边。

定义两个节点的集合 S 和 U，S 表示已经求出最短路径的节点的集合，U 表示还未求出最短路径的集合。

源点到本身的距离为 0，其他节点初始时距源点的距离为无穷大。

从 U 中选出一个距源点距离最短的节点， 把它从 U 移动至 S 中，并且更新该节点的相邻节点的距源点的距离（松弛）。

重复上述步骤，直到 S 包含所有的节点。

可视化

Prim 算法

解决最小生成树问题。

和 Dijkstra 有一点类似（贪心），但是 Prim 算法中更新的不是距源点距离，而是距已标记集合（S）的距离。

可视化

Kruskal 算法

同样是解决最小生成树的问题。

思路很简单，重复从图中选择未标记的且与已标记边不构成回路且权重最小的边进行标记，直到遍历完所有节点。

可视化