Prim's Algorithm

Introduction

Prim's algorithm is a greedy algorithm that finds a MST (minimum spanning tree) for a weighted undirected graph.
This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Steps

1. Create an array or a min heap named 'visited'.
2. Select one node and add it to 'visited'.
3. Select one minimum weighted edge that is connected to the selected node.
4. Add the node to 'visited' which is connected to the selected edge.
5. Select a minimum weighted edge that connects one node that is in 'visited' and another node that is not in 'visited'.
6. Repeat step 4 and 5 until all nodes are in 'visited'.

Example

1. Create an array or a min heap named 'visited'.

Visited: null

2. Select one node and add it to 'visited'.

Visited: 1

3. Select one minimum weighted edge that is connected to the selected node.
4. Add the node to 'visited' which is connected to the selected edge.

Selected edge: (1, 3)
Visited: 1, 3

5. Select a minimum weighted edge that connects one node that is in 'visited' and another node that is not in 'visited'.

Selected edge: (3, 2)
Visited: 1, 3, 2

6. Repeat step 4 and 5 until all nodes are in 'visited'.

Selected edge: (3, 4)
Visited: 1, 3, 2, 4


Selected edge: (4, 5)
Visited: 1, 3, 2, 4, 5


Selected edge: (4, 6)
Visited: 1, 3, 2, 4, 5

Time Complexity

If the number of the nodes are V and the number of edges are E,
1. Using array: O(V^2)
2. Using min heap: O(E log V)

More Information

Prim's Algorithm
Kruskal's Algorithm