[erlang-questions] graphs and trees

Thomas Lindgren <>
Thu Dec 20 10:23:35 CET 2007

--- mats cronqvist <>

>   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

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 ...)


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

More information about the erlang-questions mailing list