有向非循環グラフをツリーに変換する方法

Question

複数の親を持つノードを複製することで、有向非循環グラフ（DAG）をツリーに変換したいと考えています。そうする最も効率的な方法は何ですか？

Answer 1

奥行きの最初の検索や幅の広い最初の検索を使用できます。重要ではない。唯一の違いは、既に訪問した最初の頂点を複製したいということです（訪問先の深さ1に移動します）。

ここにはjavaのDFS：http://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.htmlがありますが、多くの実装があります。