Minimum Spanning Tree & Prim’s Algorithm

Before we Start Prims Algorithm or Even Minimum Spanning Tree (MST) lets understand Graph Data Structure,

Graphs:

Graph is a Data Structure which is a non-linear one consisting of Nodes and Edges. Nodes are also known or called as vertices and edges are line or arc which connects two vertices in a graph.

Graphs are commonly used in real-life problems; Graphs are usually used to represents networks because the show interconnection between two edges.

To understand or learn more about Graphs Data Structure you can Refer to GeeksforGeeks or Programiz.

MST:

Now that we know what is Graphs lets understand what is Minimum Spanning Tree (MST).

But Before minimum lets understand Spanning Tree

A spanning tree may be a sub-graph of associate afloat connected graph, which includes all of the vertices of the graph with a negligible viable vary of edges. If a vertex is missed, then it isn’t continually a spanning tree. the perimeters can also or won’t have weights assigned to them.

Now lets Get into Knowing Minimum Spanning Tree:

The cost of the spanning tree is that the total of the weights of all the sides within the tree. There may be several spanning trees. Minimum spanning tree is the spanning tree wherever the price is minimum among all the spanning trees. There can also be many minimum spanning trees. Minimum spanning tree has direct application in the style of networks. it’s utilized in algorithms approximating the roadman downside, multi-terminal minimum cut problem and minimum-cost weighted excellent matching

But why we should know About Minimum Spanning Tree is because of it use in Cluster Analysis, Handwriting Recognition , Image Segmentation and so many other important application Requires Minimum Spanning Tree.

Prim’s Algorithm Uses the Greedy algorithm, A greedy algorithm is an approach to solving a problem by choosing the best available option. It doesn’t worry if the current best score is the best overall score. The algorithm never reverses the previous decision, even if the choice is wrong.

Prim’s algorithms find the minimum spanning tree. In Prim’s algorithm, we develop the spanning tree from a beginning position. Unlike an edge in Kruskal, we add a node to the growing spanning tree in Prim.

Algorithm of Prims Algorithm:

Step 1: Select A Starting Vertex

Step 2: Repeat Step 3 and 4 until there are edge(fringe) vertices
[START OF LOOP]

Step 3: Select an Edge ‘a’ connecting the tree vertex and edge(fringe) vertex that has minimum weight

Step 4: Add the chosen Edge and the vertex to the minimal spanning Tree T

[END LOOP]

Step 5: EXIT

Complexity of Prim’s Algorithm:

Complexity of Prim’s Algorithm depends upon using which Data structure used for the representation of graph and ordering of edges.

Adjacency Matrix, Linear searching →O (|V|2)

Adjacency List and Binary Heap →O (|E| log |V|)

Adjacency List and Fibonacci heap →O (|E| + |V| log |V|)

Applications Where Prim’s Algorithm can be seen used:

Network for roads and Rail tracks connecting all the cities, Cluster Analysis, Cognitive Science And so many Other fields

Thanks for reading this blog.