Prim Algorithm for Finding the Minimum Spanning Tree

Posted on Views: Word count in article: 923 Reading time ≈ 3 mins.

Minimum Spanning Tree

For an undirected graph, the Minimum Spanning Tree is a connected subgraph of the original graph, which contains all the vertices of the original graph, and the sum of its edge weights is the smallest. We can use Prim algorithm to get the minimum spanning tree.

Prim Algorithm steps

The algorithm usually includes the following steps:

  • Step 1: Select any vertex from the graph as the root node of the tree.

  • Step 2: Find the edge with the smallest weight that is not yet connected to the tree and add it to the tree.

  • Step 3: Repeat step 2 until all vertices of the graph are in the tree.

Example

Take this undirected weighted graph above as an example to show the process of the Prim algorithm.

First, let's start with node A. As shown below:

Then, the set of visited nodes is: [A][A]. The closest node to the set of visited nodes is BB (with a weight of 5), which is added to the set of visited nodes. As shown below:

Then, the set of visited nodes is: [A,B][A,B]. The closest node to the set of visited nodes is DD (with a weight of 5), which is added to the set of visited nodes. As shown below:

Then, the set of visited nodes is: [A,B,D][A,B,D]. The closest node to the set of visited nodes is CC (with a weight of 20), which is added to the set of visited nodes. As shown below:

Then, the set of visited nodes is: [A,B,D,C][A,B,D,C]. The closest node to the set of visited nodes is FF (with a weight of 10), which is added to the set of visited nodes. As shown below:

Then, the set of visited nodes is: [A,B,D,C,F][A,B,D,C,F]. The closest node to the set of visited nodes is EE (with a weight of 20), which is added to the set of visited nodes. As shown below:

Then, the set of visited nodes is: [A,B,D,C,F,E][A,B,D,C,F,E]. The closest node to the set of visited nodes is GG (with a weight of 20), which is added to the set of visited nodes. As shown below:

Finally, all vertices are added to the tree, and we can get the following minimum spanning tree:

Code

The Prim algorithm is implemented using Python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import heapq

# Prim algorithm
def prim(adjacency_table_map):
    # Set of visited vertices. Use the first node as the starting node and add it to the visited_node_set.
    visited_node_set = {next(iter(adjacency_table_map.keys()))}

    # Priority queue to store candidate edges (visited_node, next_node, weight), sorted by weight
    candidate_edges_pq = []

    # Record the neighbor node information of the first node
    for neighbor_node, weight in adjacency_table_map[next(iter(adjacency_table_map.keys()))].items():
        heapq.heappush(candidate_edges_pq, (weight, next(iter(adjacency_table_map.keys())), neighbor_node))

    # Initialize the Minimum Spanning Tree with an empty edge list and total weight of zero
    mst_edges_list = []
    total_weight = 0

    # Process vertices until all vertices are visited
    while len(visited_node_set) < len(adjacency_table_map.keys()):
        # Pop the edge with the minimum weight from the priority queue
        weight, visited_node, next_node = heapq.heappop(candidate_edges_pq)
        print("Among the nodes aren't visited, the node closest to the visited nodes is : " + str(next_node)
              + ". The corresponding weight is:" + str(weight))

        # If the next node is not visited yet, add the edge to the MST and mark it as visited
        if next_node not in visited_node_set:
            mst_edges_list.append((visited_node, next_node))
            total_weight += weight
            visited_node_set.add(next_node)

            # Record the neighbor node information of the next node
            for neighbor_node, edge_weight in adjacency_table_map[next_node].items():
                if neighbor_node not in visited_node_set:
                    heapq.heappush(candidate_edges_pq, (edge_weight, next_node, neighbor_node))

    return mst_edges_list, total_weight

# Example usage:
# Use adjacency_table to represent the graph
adjacency_table_map = {
    "A": {"B": 5, "C": 20, "D": 5, "E": 20, "F": 50},
    "B": {"A": 5, "C": 30, "D": 30},
    "C": {"A": 20, "B": 30, "F": 10},
    "D": {"A": 5, "B": 30, "E": 25},
    "E": {"A": 20, "D": 25, "F": 50, "G": 40},
    "F": {"A": 50, "C": 10, "E": 50, "G": 20},
    "G": {"E": 40, "F": 20}
}

# Call the Prim's algorithm function
mst_edges, total_weight = prim(adjacency_table_map)

print("Minimum Spanning Tree Edges:", mst_edges)
print("Total Weight of the Minimum Spanning Tree:", total_weight)

The output is as follows:

1
2
3
4
5
6
7
8
Among the nodes aren't visited, the node closest to the visited nodes is : B. The corresponding weight is:5
Among the nodes aren't visited, the node closest to the visited nodes is : D. The corresponding weight is:5
Among the nodes aren't visited, the node closest to the visited nodes is : C. The corresponding weight is:20
Among the nodes aren't visited, the node closest to the visited nodes is : F. The corresponding weight is:10
Among the nodes aren't visited, the node closest to the visited nodes is : E. The corresponding weight is:20
Among the nodes aren't visited, the node closest to the visited nodes is : G. The corresponding weight is:20
Minimum Spanning Tree Edges: [('A', 'B'), ('A', 'D'), ('A', 'C'), ('C', 'F'), ('A', 'E'), ('F', 'G')]
Total Weight of the Minimum Spanning Tree: 80