Kruskal’s Algorithm

• a greedy algorithm
• always add the next minimum/maximum link that does not form a circle (loop) with the already selected links
• grows 1 tree until it spans the entire graph

using binary heap and adjacency list

𝑂(𝐸 𝑙𝑜𝑔 𝑉))

• 𝐸 - num edges
• 𝑉 - num nodes

Prim’s Algorithm

• a greedy algorithm
• grow a spanning tree by adding in each step the minimum/maximum link between the existing tree and the rest of the graph (this automatically guarantees loop avoidance)
• merges a forest of nodes until it becomes a tree

using binary heap and adjacency list

𝑂(𝐸 𝑙𝑜𝑔 𝑉))

• 𝐸 - num edges
• 𝑉 - num nodes