爲什麼DFS樹不能包含交叉邊緣

Question

在深度優先搜索時，爲什麼不需要交叉邊緣？

Answer 1

因爲如果存在交叉邊緣，它不再是樹（樹不能包含週期）。

任何具有n個節點的樹都包含n-1條邊。如果你正在添加一個邊，任何邊（十字，後面等），你現在有n個邊。剛剛通過添加此邊連接的兩個節點之間已經有一條路徑（因爲樹中任意兩個節點之間存在路徑），並通過添加此邊來關閉一個圓。所以現在這個圖不再是一棵樹。