how to convert a directed acyclic graph into a tree

1
votes

I want to convert a directed acyclic graph (DAG) into a tree, by duplicating the nodes that has more than one parent. what is the most efficient way of doing so?

1
javagraphtreedata-conversion
I don't understand the question. Is this graph not connected? All acyclic graphs are already trees. - flakes
Great language-agnostic answer: stackoverflow.com/questions/624778/… - DouglasDD

1 Answers

0
votes

You can use depth first search or breadth first search for that. Does not matter. The only difference is that you want duplicate the first vertices that you already visited (go into depth 1 of visited, not more).

Here is DFS for java: http://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html, but there are many implementations.