(15p) Minimum spanning trees (MSTs). 3.1 (5p) The notion of a minimum spanning t
ID: 3700369 • Letter: #
Question
(15p) Minimum spanning trees (MSTs).
3.1 (5p) The notion of a minimum spanning tree is applicable to a connected weighted graph. Do we have to check a graph’s connectivity before applying Prim’s algorithm or can the algorithm do it by itself? What is the result of Prim’s algorithm on a disconnected graph?
3.2 (5p) What about Kruskal’s algorithm ? Does it work on a disconnected graph ? How would you modify Kruskal’s algorithm to find a minimum spanning forest on a disconnected graph.
3.3 (5p) Does Prim’s and Kruskal’s algorithms always work correctly on graphs with negative edge weights? Find an easy way to prove your answer.
Explanation / Answer
SOLUTION:-
(3.1):- It is not required to check a graph's connectivity before applying Prim's algorithm because Prim's algorithm will check it automatically. We can not apply Prim's algorithm on disconnected graph becasue we can not reach to all vertices if we found there any single vertex is isolated.
(3.2):- Yes, Kruskal's algorithm can work on a disconnected graph.
If we will do the extension of | E | = | V | - 1
we will get | V | - | C | , it means number of edges along with vertices | V | & connected components | C | will be exactly equals to | V | - | C | in the Minimum Spanning Forest. This algorithm can never visit to ( | V | - 1 ) edges of tree, if graph is not connected.
So the appropriate solution is that we will substitute [while ( (EdgeCounter) < ( | V | - 1) ) ] to [ while ( k < |E| ) ] in order to halting the execution of Kruskal's algorithm once classification of edges list is done.
(3.3):- Yes, Prim's and Kruskal's algorithms always work correctly on graphs with negative edge weights.
STEP-1:- Just add any big positive number to all weights of graph along with negative weights.
STEP-2:- All new weights will become positive
STEP-3:-WE can interpret the working of algorithms on newly built graph with respect to previous graph.
By all these steps we can say that accuracy of both algorithms does not rely on positive edges.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.