Re: [Boost-users] BGL: why is the prim algorithm only useable for undirected graphs?

boost@spyderworks.de wrote: [snip]

In literature, I can only find usage of Prims algorithm for undirected graphs, too. But I can see no reason, why it shouldn't work for directed graphs. Can you tell me more?

Let G=(V,E) be a connected undirected graph. The object Prim's algorithm creates (minimum spanning tree of G) is a free tree T=(V,E') (which by definition is an undirected connected acyclic graph) where E' is a subset of E. For T to be defined G must be connected which would mean if G was directed it would have to be strongly connected -- which amounts to the graph being undirected. Regards, Robert F. Morse