如何將有向無環圖轉換爲樹

Question

我想通過複製具有多個父節點的節點將有向無環圖（DAG）轉換爲樹。這樣做最有效的方法是什麼？

Answer 1

您可以使用深度優先搜索或廣度優先搜索。沒關係。唯一的區別是你想複製你已經訪問的第一個頂點（進入訪問的深度1，而不是更多）。

這裏是DFS的java：http://algs4.cs.princeton.edu/41graph/DepthFirstSearch.java.html，但有很多實現。