Menu
I intuitively feel that if one is using Prim's algorithm to find a graph's minimum spanning tree, it doesn't matter which root node is picked - the resultant MST will have the same weight regardless. Is this correct?
562
Prim's and Kruskal's algorithms will always return the same Minimum Spanning tree (MST). Prim's algorithm for computing the MST only work if the weights are positive. An MST for a connected graph has exactly V-1 edges, V being the number of vertices in the graph.
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.
Does Prim's? Solution: Yes, both algorithms work with negative edge weights because the cut property still applies.
That is correct. Choosing a different starting node could give you a different spanning tree, but it will always have the same weight: the minimal possible.
141
This is because of uniqueness of minima.
Proof:
Suppose there are 2 "different" minimum weights W1 and W2
W1 is minimum
W2 is minimum
W1 != W2
This leads to contradiction because
if W1 != W2 then
W1 < W2 -> W1 is minima
or
W1 > W2 -> W2 is minima
Hence if W1 must equal W2.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
