finding all minimal spanning trees

algorithm graph minimum-spanning-tree
user182513 picture user182513 · Dec 31, 2010 · Viewed 8.3k times · Source

Possible Duplicate:
All minimum spanning trees implementation

How can I find all minimum spanning trees in an undirected graph in an efficient way?

Answer

Dervin Thunk picture Dervin Thunk · Dec 31, 2010

Apologies for the academic answer... but algorithm S in Knuth's TAOCP, Volume 4, Fascicle 4 is exactly about generating all spanning trees (pp. 26ff). There are a few musings when he talks about generating (spanning) trees, but your best bet in TAOCP.

Related questions

Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Is Minimum Spanning Tree afraid of negative weights?

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?. I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to …

Read More
How is a minimum bottleneck spanning tree different from a minimum spanning tree?

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum spanning tree). Please …

Read More