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

From: Robert F. Morse (rm43_at_[hidden])
Date: 2004-05-13 13:15:58

boost_at_[hidden] 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