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