I suspect that what you want is called a spanning tree on a directed graph. There are some fast algorithms for finding spanning trees. The best intro discussion I can find quickly is the Wikipedia article on minimum spanning trees which will give you a place to start. I also think the book Mastering Algorithms in Perl touches these topics.

Update: Now, if my gut instinct is wrong and you actually want every possible *tree* associated with a directed graph, then you have to know that the number of trees grows so rapidly as a function of the number of nodes that you're in for a time intensive process regardless.

Update 2: Argh, totally off base here. DAGs aren't necessarily rooted, as trees are.