Dear reader, welcome to the article on the problem named "Minimum Wire Required To Connect All Pcs" .
The problem is popularly known as "Minimum Spanning Tree" . The algorithm, which we are going to learn today, is known as Prim's Algorithm.
- You are given a graph and a source vertex. The vertices represent computers and the edges represent the length of LAN wire required to connect them.
- You are required to find the minimum length of wire required to connect all PCs over a network.
- Print the output in terms of which all PCs need to be connected, and the length of wire between them.
Note: Input is given in the form of adjacency list. Please go through the output format once, before moving ahead in the article.
Minimum Spanning Tree:
First of all, let us see, what is a MINIMUM SPANNING TREE?
- Tree: A tree is an undirected acyclic and connected graph. If a tree has n nodes, then there will be n-1 edges present. Since the tree is connected, there cannot be more than 1 component.
- Spanning Tree: A spanning tree is a subgraph which covers all the vertices of the graph. Hence, if the graph has n vertices, then the spanning tree must contain all the n vertices in one connected component.
- Minimum Spanning Tree: There can be many spanning trees possible. The one whose sum of weights of edges is minimum, is known as minimum spanning tree.
So, for the graph drawn above, there can be many spanning trees possible:
Prim's algorithm is based on a greedy approach and is very similar to Dijkstra's algorithm.
In Dijkstra's algorithm, we were required to find the shortest path from source, hence we required the total sum of weights from source to destination to be minimum.
But in prim's algorithm, we need the sum of all edges taken in spanning tree to be minimum. So, instead of adding the summation of paths, we will require to add the edge weights directly into the priority queue.
Intuition behind the prim's algorithm is simple, i.e. pick the edges with the minimum weights possible, such that all vertices are connected in a single component.
Hence, we can use priority queue to find the minimum edge weight among all the edges of a source node.
Hence, the Pair objects that will be pushed into the priority queue will not have weight so far, but instead have simply the edge weight.Also, instead of having the path so far, they will store the information of the parent vertex, through which they are acquired (pushed into the priority queue).