Count number of MSTs in a graph

Question

I thought about this problem many hours, but I didn't find any solutions

The problem is :

How many MSTs does the given graph have (MST := Minimum Spanning Tree)

the graph G is an undirected, connected graph

it's Guaranteed that no vertex's degree exceeds 3 :)

prefer C/C++ solutions (can understand like-code-formed Algorithm too)

and please with a low order :) (running time)

UPDATE

first of all finding all MSTs :) O( |E| log |E| )

others where worse :(

Can you share your attempt or thoughts about how to solve it? — Abhishek Bansal, Nov 20 '13 at 16:45
Duplicate question: http://stackoverflow.com/questions/13853801/how-to-find-total-number-of-minimum-spanning-trees-in-a-graph — Juser1167589, Nov 20 '13 at 16:48
is the answer correct ? it isnt good :| isnt there any better way, if we limit vertex degrees — user3014012, Nov 20 '13 at 16:52
How do you distinguish between two minimum spanning trees? If two MSTs use the same set of edges, but the vertex considered to be the root of the tree is different, are the MSTs equivalent, or different? In other words, given a graph of two vertices with a single edge between them, is there one MST or two? — twalberg, Nov 20 '13 at 17:43

Ante · Answer 1 · 2013-12-04T09:16:43.550

You can try with a backtracking. In each step for one of 'leaf' vertices decide how many 'out' edges to use.

function add_some_vertex_edges(leaves, edge):
  if |leaves| == |V|:
    num_of_MSTs += 1
    return
  v = leaves.pop()  # takes one vertex and removes it from leaves
  let v_edge be set of incident edges to v that are not already in edges and that don't make cycle if added to edges
  for each combination of edges from v_edge:
    add_edges(leaves + incident_vertices, edges + edge_combination)

add_some_vertex_edges({v}, {})

Since vertices degree is <= 3, for each leaf one edge is used to 'enter' it, and because of that |v_edge| <= 2, and because of that search tree is narrow.

Worst case running time is O(2^n), but probably in practical cases it is fast. There are examples with worst case number of MSTs. Example that I can think of is with two parallel lines of vertices and connections between them.

O---O---O---O---O---O---O---O---O---
 \ /     \ /     \ /     \ /     \ /
  X       X       X       X       X ...
 / \     / \     / \     / \     / \
O---O---O---O---O---O---O---O---O---

In this example there are exactly 2^(n/2) MSTs. To calculate this, take 2 leftmost vertices. They can be connected to the rest of a graph in 4 ways.

O---O   O   O   O   O   O---O
         \ /     \ /     \ /
          X       X       X
         / \     / \     / \
O---O , O   O , O---O , O   O

For each group of interconnected 4 vertices there are 4=2^2 possibilities to choose from.

Count number of MSTs in a graph

1 Answers1