BGL: why is the prim algorithm only useable for undirected graphs?
Hi all,
in the documentation of prim_minimum_spanning_tree is mentioned "...
solving the minimum spanning tree problem for an undirected graph with
weighted edges ...".
In my application I use this graph type (the graph type is bidirectionalS
=> not directed):
typedef
adjacency_list
BGraph;
This type modells the VertexListGraph and IncidenceGraph concepts, which are required by the prim function. If I call the prim_minimum_spanning_tree, I get reasonalble results. 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? Best regards Stefan Rauch
Hi Stefan, On May 13, 2004, at 7:33 AM, boost@spyderworks.de wrote:
Hi all, in the documentation of prim_minimum_spanning_tree is mentioned "... solving the minimum spanning tree problem for an undirected graph with weighted edges ...". In my application I use this graph type (the graph type is bidirectionalS => not directed):
Oops, that's your problem. bidirectionalS is a directed graph... it is
a directed
graph that provides access to both in_edges and out_edges, whereas
directedS
only provides access to out_edges. If you want an undirected graph, use
undirectedS.
Cheers,
Jeremy
_______________________________________________
Jeremy Siek
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
participants (3)
-
boost＠spyderworks.de -
Jeremy Siek -
Robert F. Morse