本次笔记内容：
8.1.1 Prim算法
8.1.2 Kruskal算法
文章目录
最小生成树问题什么是最小生成树（Minimum Spanning Tree）贪心算法Prim算法Kruskal算法最小生成树问题
什么是最小生成树（Minimum Spanning Tree）
是一棵树：
没有回路；|V|个顶点一定有|V|-1条边。
是生成树：
包含全部顶点；|V|-1条边都在图里。
边的权重和最小。
如上图，向最小生成树里加一条边都一定能构成回路。并且“最小生成树存在”和“图连通”是充分必要条件。
贪心算法
“贪”：每一步都是最好的；
“好”：权重最小的边。
约束：
只能用图里有的边；只能正好用掉|V|-1条边；不能有回路。
Prim算法
让一棵小树长大。类似Dijkstra算法。
void Prim(){MST = {s};while (1){V = 未收录顶点中dist最小者;if (这样的V不存在)break;将V收录进MST;for (V的每个邻接点W)if (W未被收录)if (E(V, W) < dist[W]){dist[W] = E(V, W);parent[W] = V;}}if (MST中收的顶点不到 | V | 个)Error("生成树不存在");}
其中，dist[V]=E(s,V)或正无穷；
为了巧妙存储树，用parent定义树（节点的父节点），其中根节点parents[s]=-1。
Prim的时间复杂度是O(N2)O(N^2)O(N2)，适于稠密图。
Kruskal算法
将森林合并成树。
对边遍历：初始时，将每个节点都视为一棵树。逐渐地，将各树连接起来。
void Kruskal(Graph G){MST = {};while (MST中不到 | V | -1条边 && E中还有边){从E中取一条权重最小的边E(V, W); // 使用最小堆将E(V, W)从E中删除； if (E(V, W) 不在MST中构成回路) //并查集将E(V, W) 加入MST;else 彻底无视E(V, W);}if (MST中不到 | V | -1条边)Error("生成树不存在");}
时间复杂度为O(E×log2(E))O(E \times \log_2(E))O(E×log2(E))，适于V的数量约等于E的稀疏图。
