
Boost Users : 
From: Robert F. Morse (rm43_at_[hidden])
Date: 20040513 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net