Minimum Spanning Tree

graph-theory

Algorithms

Prim’s Algorithm

Definition

Prim's Algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a undirected network.

For dense graphs, $(|E|=\Theta (|V{|}^2))$, prim’s algorithm is better than Kruskal’s algorithm.

Link to original

Kruskal’s Algorithm

Definition

Kruskal's Algorithm

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a undirected network.

For sparse graph, $(|E|=\Theta (|V|))$, Kruskal’s algorithm is better than Prim’s algorithm.

Link to original