图论的笔记

Kruskal

最大/小生成树算法

一棵 n 个节点的树可以理解为一个 n 个节点； n-1条边的连通图（一个节点可以到达任意一个其它节点）

即，断开一条边，树分为两个连通块。则断开 k 条边树被分为 k+1 个连通块。

生成树是什么？

从一张 n 个节点 m 条边的图中选出 n-1 条边，组成一个（连通的）树

最小生成树：边权最小的生成树；最大生成树相反。

反向考虑一棵树的构建过程：

一开始是 n 个独立的点（连通块），然后每增加一条边就减少一个连通块。我们可以使用并查集来实现连通块的维护。

要构建一颗最小生成树，只要按照边权升序排序，依次考虑。

那怎么考虑呢？对于要考虑的两个节点 u、v，通过并查集查看它们是否在同一连通块中（find(u)==find(v)），如果是则不选（这样会形成环而最终的树中不应该有环）；否则可以选。

Kruskal算法的流程：

1.初始化并查集 2.按边权排序，依次扫描每条边：

• 如果 u、v 在同一连通块中，扫描下一条；
• 否则选择

动态算法演示

Dijkstra

解决单源最短路径（SSSP）的算法

流程：

dis(x) 表示从起点 S 到 x 的最短距离

• 初始化 dis(S) 为 0，其它为 正无穷
• 在未被标记的节点中找到 dis 最小的并标记
• 将上一步找到的最小的设为 x，扫描 s 的所有出边 (x,y,z)（即从 x 到 y 的距离为 z），如果 dis(y)>dis(x)+z

它只能处理非负边权！

时间复杂度为 O(n^2)