Prim’s Algorithm

Prim’s Algorithm

In this post, we’ll look at what a minimal spanning tree is and how to turn a graph into one using Prim’s Algorithm. We will learn the prim’s algorithm and an example for better understanding. Finally, we’ll look into prim’s algorithm’s running time complexity and real-world applications.

What is a Minimum Spanning Tree?

An undirected graph is one that has no edges going in any direction and always has a route from one vertex to another. A spanning tree is a subgraph of an undirected connected graph that contains all of the graph’s nodes while having the least amount of edges feasible. Remember that the subgraph must contain all of the original graph’s nodes. It is not a spanning tree if any node is missing, and it also does not include cycles. The total number of spanning trees generated from a full graph is equal to n if the graph contains n nodes (n-2).

The edges of a spanning tree may or may not have weights attached to them. As a result, the spanning tree with the smallest possible total of edges is known as the minimal spanning tree. There can be several spanning trees in a same graph, but only one unique minimal spanning tree.

What is Prim’s Algorithm?

Prim’s method is a minimal spanning tree algorithm that assists in determining the edges of a graph in order to construct a tree that includes every node with the smallest sum of weights. Prim’s method begins with a single source node and then moves on to all of the source node’s nearby nodes and connected edges. We’ll pick the edges with the least weight and those that can’t generate cycles in the graph as we explore the graphs.

Prim’s Algorithm for Minimum Spanning Tree

Prim’s method, in order to identify the best answer, uses a greedy algorithm technique. To use Prim’s approach to determine the minimal spanning tree, we’ll start with a source node and keep adding the edges with the lowest weight.

The following is the algorithm:

Choose the source vertex to start the algorithm.

Add the lowest weight edge connecting the source node and another node to the tree.

Repeat this technique until the shortest spanning tree is found.

PseudoCode

T = ∅;

M = { 1 };

while (M ≠ N)

let (m, n) be lowest cost edge such that m ∈ M and n ∈ N — M;

T = T ∪ {(m, n)}

M = M ∪ {n}

We’re going to make two sets of nodes, M and M-N. The M set holds the list of nodes that have been visited, whereas the M-N set holds the list of nodes that have not been visited. After each step, we’ll link the least weight edge to transfer each node from M to M-N.

EXAMPLE

Python code

INF = 9999999
# number of vertices in graph
N = 5
#creating graph by adjacency matrix method
G = [[0, 19, 5, 0, 0],
[19, 0, 5, 9, 2],
[5, 5, 0, 1, 6],
[0, 9, 1, 0, 1],
[0, 2, 6, 1, 0]]
selected_node = [0, 0, 0, 0, 0]
no_edge = 0
selected_node[0] = True
# printing for edge and weight
print("Edge : Weight\n")
while (no_edge < N - 1):
minimum = INF
a = 0
b = 0
for m in range(N):
if selected_node[m]:
for n in range(N):
if ((not selected_node[n]) and G[m][n]):
# not in selected and there is an edge
if minimum > G[m][n]:
minimum = G[m][n]
a = m
b = n
print(str(a) + "-" + str(b) + ":" + str(G[a][b]))
selected_node[b] = True
no_edge += 1

Time Complexity:

Because each insertion of a node into the solution requires logarithmic time, the running time of prim's method is O(VlogV + ElogV), which is equivalent to O(ElogV). The number of edges is E, while the number of vertices/nodes is V. Using Fibonacci Heaps, we can reduce the running time complexity of prim's algorithm to O(E + logV).

Conclusion

The least spanning tree has its own significance in the actual world; learning the prim’s method, which leads us to the solution of many issues, is essential. Prim’s approach is the primary choice when it comes to determining the least spanning tree for dense graphs.