图论的笔记
最大/小生成树算法
一棵 n 个节点的树可以理解为一个 n 个节点; n-1条边的连通图(一个节点可以到达任意一个其它节点)
即,断开一条边,树分为两个连通块。则断开 k 条边树被分为 k+1 个连通块。
生成树是什么?
从一张 n 个节点 m 条边的图中选出 n-1 条边,组成一个(连通的)树
最小生成树:边权最小的生成树;最大生成树相反。
反向考虑一棵树的构建过程:
一开始是 n 个独立的点(连通块),然后每增加一条边就减少一个连通块。我们可以使用并查集来实现连通块的维护。
要构建一颗最小生成树,只要按照边权升序排序,依次考虑。
那怎么考虑呢?对于要考虑的两个节点 u、v,通过并查集查看它们是否在同一连通块中(find(u)==find(v)),如果是则不选(这样会形成环而最终的树中不应该有环);否则可以选。
Kruskal算法的流程:
1.初始化并查集 2.按边权排序,依次扫描每条边:
解决单源最短路径(SSSP
)的算法
流程:
dis(x) 表示从起点 S 到 x 的最短距离
它只能处理非负边权!
时间复杂度为 O(n^2)