本次笔记内容:
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的稀疏图。