[erlang-questions] graphs and trees

[Thomas Lindgren]

--- mats cronqvist <mats.cronqvist@REDACTED>
wrote:

>   so i've made a directad acyclic graph by calling
> various functions in
> the digraph module. i theory, the resulting graph
> should be a tree. is
> there some snazzy graph theory trick to show that
> the graph is indeed a
> tree?

Here is a straightforward algorithm, O(number of
nodes):

Visit all nodes starting from the root, marking each
node when visited. If you visit an already seen node,
it's not a tree.

If some node remains unmarked after this traversal,
it's not a tree either. (It's not connected, or there
is no unique root, or ...)

Best,
Thomas




      ____________________________________________________________________________________
Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping