Given a graph which consists of several edges connecting its nodes, find a subgraph of the given graph with the following properties:
One specific node is fixed as the starting point of finding the subgraph using Prim's Algorithm.
Find the total weight or the sum of all edges in the subgraph.
Starting from node , select the lower weight edge, i.e. , weight .
Choose between the remaining edges, , weight , and , weight .
The lower weight edge is weight .
All nodes are connected at a cost of . The edge is not included in the subgraph.
Complete the prims function in the editor below.
prims has the following parameter(s):
The first line has two space-separated integers and , the number of nodes and edges in the graph.
Each of the next lines contains three space-separated integers , and , the end nodes of , and the edge's weight.
The last line has an integer , the starting node.
There may be multiple edges between two nodes.
Sample Input 0
1 2 3
1 3 4
4 2 6
5 2 2
2 3 5
3 5 7
Sample Output 0
The graph given in the test case is shown as :
Applying the Prim's algorithm, edge choices available at first are :
(WT. 3) and (WT. 4) , out of which is chosen (smaller weight of edge).
Now the available choices are :
(WT. 4) , (WT. 5) , (WT. 2) and (WT. 6) , out of which is chosen by the algorithm.
Following the same method of the algorithm, the next chosen edges , sequentially are :
Hence the overall sequence of edges picked up by Prim's are:
and the total weight of the MST (minimum spanning tree) is :