Minimum spanning tree

[nicoletsg]

How can I solve this?
g(v,e) undirected with weight >=0
give an algorithm which test
if G has Minimum spanning tree uniq
two MST

[mf]

One simple algorithm is: take some minimum spanning tree T, and for each edge e in T, compute MST of graph G without the edge e. If cost of every new MST is greater that the cost of T, then T is the unique MST of G.

If this algorithm is too slow, you can also modify Kruskal's algorithm to check MST's uniqueness, but it's little complicated.

[nicoletsg]

So you think I can use KrusKal to enumerate 2nd MST ?
Why kruskal and not PRIM

[mf]

So you think I can use KrusKal to enumerate 2nd MST ?

Yep.

Why kruskal and not PRIM

Well, I don't see a way to modify Prim's algorithm to do that. If you can find one, that'd be great.

[nicoletsg]

Which would be modifications in the algorithm's Kruskal?

[mf]

Kruskal's algorithm goes like this: it loops over graph's edges in order of increasing cost, and adds current edge to the MST, unless doing so would create a cycle in it.

When some edges have equal cost, the algorithm is indeterministic: by changing the order in which the algorithm loops over these equal-cost groups of edges, it could produce different MSTs. So the modification needed is to check, for each of these groups, whether it is possible to make Kruskal's algorithm select a different subset of edges by changing the order of edges within this group.

Here's a pseudo-code:

Code: Select all

for each group A of edges having the same weight, starting from cheapest:
    remove from A every edge (u, v) such that Find(u) = Find(v)
    (Kruskal's algorithm will ignore these edges anyway)

    for each edge (u, v) in A (in any order):
        if Find(u) = Find(v):
            print "MST is not unique", and terminate.
            (In this case, edge (u,v) is part of some cycle in A,
            and e.g. by moving it in front of the group A, we can
            make Kruskal's algorithm include it into MST.)
        else:
            Union(u, v)
print "MST is unique"

Here Find and Union are the disjoint-sets data structure's operations.

[nicoletsg]

Can someone suggest some good algorithm for this ?

[nicoletsg]

Thanks for the ideas of solving.

Kruskal's algorithm goes like this: it loops over graph's edges in order of increasing cost, and adds current edge to the MST, unless doing so would create a cycle in it.

When some edges have equal cost, the algorithm is indeterministic: by changing the order in which the algorithm loops over these equal-cost groups of edges, it could produce different MSTs. So the modification needed is to check, for each of these groups, whether it is possible to make Kruskal's algorithm select a different subset of edges by changing the order of edges within this group.

Here's a pseudo-code:

Code: Select all

for each group A of edges having the same weight, starting from cheapest:
    remove from A every edge (u, v) such that Find(u) = Find(v)
    (Kruskal's algorithm will ignore these edges anyway)

    for each edge (u, v) in A (in any order):
        if Find(u) = Find(v):
            print "MST is not unique", and terminate.
            (In this case, edge (u,v) is part of some cycle in A,
            and e.g. by moving it in front of the group A, we can
            make Kruskal's algorithm include it into MST.)
        else:
            Union(u, v)
print "MST is unique"

Here Find and Union are the disjoint-sets data structure's operations.

[joshi13]

Hi.

What about if we are asked the number of different MST ?

Thanks in advance.

[mf]

What about if we are asked the number of different MST ?

http://forums.topcoder.com/?module=Thre ... 17#1033786