1. Problem
These two algorithm are all used to find a minimum spanning tree for a weighted undirected graph.
2.Kruskal's algorithm
2.1 Pseudocode
A = ∅
foreach v ∈ G.V:
MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
2.2 Complexity
O(E logE) , equivalently, O(E log V) time ,because
\[E \le V^2\ and\ logV^2=2logV
\]
\]
3. Prim's algorithm
3.1 Pseudocode
Remove all loops and parallel edges
Choose any arbitrary node as root node
Check outgoing edges and select the one with less cost
Repeat step 3 (until all vertices are in the tree).
3.2 Complexity
\(O(V^2)\) [adjacency matrix]
\(O(ElogV)\) [adjacency list]
4.Summary
Both of the algorithms are greedy algorithms and aim to find a subset of the edges which forms a tree that contains every vertex. However, Kruskal's algorithm chooses a node, whereas Prim's algorithm chooses an edge at each time.
5.Reference
原文链接: https://www.cnblogs.com/xiaofulan/p/10371714.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/289883
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!