Kruskal 算法
作用
求最小生成树（Minimum Spanning Tree）
思想
贪心算法
算法流程
- 将所有的边从小到大排序
- 按从小到大的顺序取边准备放入结果集，假设现在取的边为
E0,在放入结果集合前，要检查该边E0是否和已放入结果集中的边构成环，如果能构成环则E0不放入结果集，考虑下一条边E1;否则将该边E0放入结果集中，考虑下一条边E1 - 如此往复直到达到中止条件
中止条件
- n个节点的图，已放入n-1条边。
- 如果处理了所有的边，结果集中仍不足n-1条边，则说明该图不连通。
并查集
并查集(不相交的集合,find-union set,disjoint set)
动态维护若干个点，每个点属于且仅属于一个集合。
功能
查询某个点属于哪个集合。
把两个点所在的集合合并成一个集合。
应用
抽象地说，是维护动态连通性
在Kruskal算法中，主要用于判断是否形成环，以及加入边的操作
每个节点都有一个标号，表示它属于哪一个连通分量。
判断是否形成环 => 两个点是否在同一个连通分量（标号是否相同）
加入边的操作 => 合并两个点所在的连通分量
Prim算法
作用
求最小生成树（Minimum Spanning Tree）
与Kruskal算法的区别
Kruskal算法在加边的过程中，维护的不一定是一棵树（维护的是森林），而Prim算法始终是一棵树的延展。
思想
贪心算法
算法流程
初始 E = {} 空集合，V = {任意一个节点}
循环(n-1)次
选择一条边$(v_1,v_2)$,满足v1 属于 V，v2 不属于 V
(v1,v2)权值最小
E=E+(v1,v2)
V=V+v2最终E中的边即为最小生成树
Dijkstra算法
思想
贪心算法
算法的过程与Prim算法非常接近，只不过每次加入集合，会有更新权值的过程。
我觉得这个权值更新过程就是Dijkstra算法的关键。
算法流程
节点编号
0..n-1，起点编号 0 <= s < n
距离数组
起点 d[s] = 0
其他 d[i] = inf i != s
节点集合V={}空集合，举例初始化
循环n次
找到i不属于V且d[i]值最小的节点i
V = V + i
对所有满足j不属于V的边(i,j),更新 d[j] = min(d[j],d[i]+w(i,j))
参考资料
[1] 7月算法公开课-Kruskal算法
[2] 7月算法公开课-Prim算法
[3] 7月算法公开课-Dijkstra算法
[4] Prim算法实现
