Prim's Algorithm & Kruskal's algorithm

2019/02/13 20:46
阅读数 74

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

Prim's algorithm

Kruskal's algorithm

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部