我該如何做這個圖遍歷？

Question

我有一個定向循環圖，由節點a，b，c，d，e，f g組成，其中節點連接到每個其他節點。邊緣可以是單向的或雙向的。我需要打印出這樣的有效命令，例如。 f-> a-> c-> b-> e-> d-> g，這樣我就可以從起始節點到達末端節點。請注意，所有節點必須出現在輸出列表中。 另請注意，圖中可能有周期。

我想出了： 基本上首先我們可以嘗試找到一個開始節點。如果有一個節點使得它沒有傳入邊緣（最多可能有一個這樣的節點）。我可能會找到一個開始節點或者可能不會。另外我會做一些預處理來找到節點的總數（讓我們稱它爲n）。現在，我將從啓動節點標記節點開始創建一個DFS，並在訪問它們時計算我訪問的節點數量。如果我可以通過這種方法到達n個節點。我做完。如果我擊中了一個節點，而這個節點沒有到任何未訪問節點的傳出邊緣，那麼我已經遇到了一個死路，我只會將該節點再次標記爲未訪問，減少指針並轉到其前一節點以嘗試不同的路由。

這是我找到起始節點的情況。如果我沒有找到一個起始節點，我只需要在各個節點上嘗試。

我不知道我是否接近解決方案。任何人都可以在這方面幫助我嗎？

Answer 1

在我看來，如果沒有進入的邊緣節點，這意味着該節點是開始節點。您可以使用此開始節點遍歷圖形。如果這個起始節點不能訪問所有n個節點，那麼就沒有解決方案（正如你所說的，所有節點都必須出現在輸出列表中）。這是因爲如果你從其他一些節點開始，你將無法到達這個開始節點。

Answer 2

與解決方案的問題是，如果你進入一個循環，你不知道是否以及何時退出。

在這些條件，DFS搜索可以很容易地成爲非多項式的任務！

讓我爲您的問題介紹一個多項式算法。 看起來很複雜我希望有簡化的空間。

這裏我建議的溶液

1）對於每個節點構造它可以達到（如果能達到b和c的節點的表; b可以達到d; C可達到Ë;一個可達到b，c，d，即使強硬也沒有一條通過它們的路徑）。

如果沒有節點可以到達所有你做其他的人：有沒有你要找的路徑。

2）查找循環。這很簡單：如果一個節點可以到達它自己，就有一個循環。這應該是前一點建立表格的一部分。

一旦找到一個循環，就可以將它（及其節點）縮小爲代表節點，其代表節點的輸入（輸出）連接是循環中節點的輸入（輸出）連接的並集。

你不斷減少循環，直到你不能再做。

3）此時如果只剩下一個非循環圖，如果有連接的所有節點的路徑，存在連接到所有的單個節點，並從它開始可以執行深度優先搜索。

4） 通過用從循環入口點到出口點的循環替換代表性節點的遍歷來記錄路徑。