Things to be discussed here.
- Prim's Algorithms
- Practice Problem
The prerequisite for this article is "Graph Theory Problem Solving - Session 10", as most of the concept related to Minimum Spanning Tree is already discussed there.
Prim's Algorithm
Prim's Algorithm
Prim's Algorithm is also a Greedy Algorithm to find MST. In Prim's Algorithm, we grow the spanning tree from a starting position by adding a new vertex. In Kruskal's Algorithm, we add an edge to grow the spanning tree and in Prim's, we add a vertex.
Algorithm:
- Store the graph in an Adjacency List of Pairs.
- Maintain a min Priority Queue (pq) that sorts edge based on min edge cost. This will be used to determine the next node to visit and the edge used to get there.
- Start the algorithm on any node s, mark s as visited, and iterate over all edges of s, adding them to the (pq).
- While the (pq) is not empty and the MST has not been formed, dequeue the next cheapest edge from the (pq).
- If the dequeued edge is outdated ( means that the node it points has already been visited) then skip it and dequeue the next edge. Otherwise mark the current node as visited and add the selected edge to the MST.
- Iterate over the new current node's edges and add all its edges to the (pq).
- Do not add edges to the (pq) which points the already visited nodes.
Here is a Video from Youtube which explains the above algorithm.
Implementation in C++
In this implementation I have just found the Minimum Cost, you need to manipulate the code to store the MST Edges. If you find this difficult and need implementation for this then do Comment.
This Implementation is for Lazy Version of Prims. Later, when we will study about Fibbinacci Heap in our Data Structure then we will be implementing Eager Version of Prim's Algorithm.
Application and Practice Problem is the same for both Kruskal's Algorithm and Prim's Algorithm.
That's all for this article, in the next session we will be discussing Directed Graphs and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA
In this implementation I have just found the Minimum Cost, you need to manipulate the code to store the MST Edges. If you find this difficult and need implementation for this then do Comment.
This Implementation is for Lazy Version of Prims. Later, when we will study about Fibbinacci Heap in our Data Structure then we will be implementing Eager Version of Prim's Algorithm.
Application and Practice Problem is the same for both Kruskal's Algorithm and Prim's Algorithm.
Applications:
- In electronic circuit design to minimize the wire length.
- To find routing path in networks
- Airplane network routes.
- Network Design etc.
Practice Problem
That's all for this article, in the next session we will be discussing Directed Graphs and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).
If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.
Thank You
With 💙 by Learn DSA