DFS邊緣分類是否有效？

Question

DFS可用於邊緣分類到樹，向前，背部和橫。

給定邊的分類和頂點數，我們可以確定線性複雜度，它是DFS的有效結果嗎？如果是這樣 - 如何？

例如，這裏是無效的分類：（這是不可能得到一個這樣的，不管根頂點我們選擇和探望的順序）

Answer 1

道歉有點簡短回答：是的，這是一個算法。驗證樹邊確實形成一棵樹。對於其他邊緣，計算其端點的最葉共同祖先。對於前沿，這應該是尾巴。對於後邊緣，這應該是頭部。對於交叉邊緣，這應該既不是。

假設目前一切看起來不錯，從交叉邊緣的頭部和尾部的根部路徑經由不同的孩子到達LCA。在生成給定分類的每個可能的DFS順序中，在尾巴的孩子之前訪問頭部的孩子。收集所有這些限制條件並確認沒有循環。

我聲稱，這些檢查一起聲音和完整。通過使用拓撲排序線性化約束並構建合理的DFS順序來驗證完整性。