CODEWITHSUNDEEP
algorithmtreeminimum-spanning-tree
venkysmarty
venkysmarty

Reputation: 11441

Generic minimum spanning tree

I am reading myself about Minimum Spanning trees in Cormen,etc. Following is the generic minimum spanning tree.

Assume we have a connected, undirected graph G = (V, E) witha a weight function w:E->R and we wish to find a minimum spanning tree for G. Here we use greedy approach. This greedy strategy is captured by the following "generic" algorithm, which grows the minimum spanning tree one edge at a time. The algorithm manages a set of edges A, maintaining the following loop invariant.

Prior to each iteration, A is subset of some minimum spanning tree.

GENERIC-MST(G,w) 
A = NULL
while A is not a spanning tree 
  do find an edge (u, v) that is safe for A 
  A = A ∪ {(u, v)}
end while

return A

Questions

  1. What does authore mean in invariant that "A" is subset of some minimum spanning tree? What is "some" in this statement? i taught there is only one MST.

  2. In above pseudocode what does author mean by "A is not a spanning tree"? i.e., how and when while loop exits?

  3. In pseudo code where "some" minimum spanning tree, here my understading is only one. am i right?

Can any one pls explain with small example?

Thanks!

Upvotes: 2

Views: 3138

Answers (4)

Existent
Existent

Reputation: 717

  1. This is false. A graph may have many MST even if only two edges are equal.

  2. A is not minimum spanning tree because of:

    2.1 First of all A is not a tree - it is disconnected.

    2.2 It does not span the graph

    The loop will exit when the above conditions are met

  3. It is correct to say that it is in some MST as there are many.

Upvotes: 1

Tom Swifty
Tom Swifty

Reputation: 2962

  1. Incorrect as per @davin

  2. The algorithm maintains the invariant that you have a forest, but the forest will not span the graph until you add enough edges. Thus you have to keep adding edges until none of them are safe (at which point the loop breaks).

  3. see 1.

Upvotes: 0

Nikunj Banka
Nikunj Banka

Reputation: 11385

  1. You are correct when you say a spanning tree of a graph is unique . But this is the case when all the edge lengths of the graph are different. As explained in the above answer, a graph with equal edge lengths can have many different spanning trees(all of them having the same total weight of course) .
  2. The while loop exists when you have included all the vertices of the graph in your spanning tree . For this you add a check in your while loop .

Upvotes: 0

davin
davin

Reputation: 45555

1. Absolutely not. MST are not necessarily unique. For example:

All edges are of equal weight.

u --- v
|     |
|     |
w --- x

The above graph has 4 MSTs, by removing any edge.

2. A spanning tree T = (V,e) in G = (V,E) is such that |e| = |V|-1

3. No.

Upvotes: 4

Related Questions