All algorithms are in pseudocode Minimum spanning trees (MSTs). 3.1 (5p) The not

Question

All algorithms are in pseudocode

Minimum spanning trees (MSTs).
3.1 (5p) The notion of a minimum spanning tree is applicable to a con-
nected 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 nd 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

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.