图论的笔记

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$就更新 $dis(y)$

它只能处理非负边权！

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