從門票打印路線

Question

今天我遇到了一個我無法解決的問題。

經常旅行者收集他所有的旅行門票。 一張票只有2個屬性，開始旅程地點名稱和目的地名稱。從德里到紐約的例子。 在年底，旅行者將所有的票都放在一起，並嘗試繪製全年的旅程。以可讀格式打印他可能的旅行路線。他不記得他的起始位置。他可以多次訪問一個位置，也可以多次來回地點。

最初我認爲它可以簡單地通過製作一張圖（票-A到B意味着一個有向邊A-> B）並使用一個簡單的深度第一次遍歷從一個不等於0（??）的節點來解決。但後來我意識到它不是獲得解決方案的正確方法，因爲它可能會打印隨機未連接的路線。
請建議正確的方法繼續。

Answer 1

首先你應該檢查你的圖是否有歐拉跡或歐拉循環。

有向圖具有歐拉循環當且僅當每個頂點有 在度和出度，和所有其頂點具有非零 度等於屬於單個強連通分量。等價地，有向圖具有歐拉循環當且僅當它可以分解爲邊緣不相交有向循環並且其具有非零度的所有頂點 屬於單個強連通分量。

有向圖具有歐拉線索當且僅當至多一個頂點 具有（出度） - （入度）= 1，至多一個頂點具有（入度） - （ out-degree）= 1，則每個其他頂點具有相等的入度和出度，且其非零度的所有頂點都屬於底層無向圖的單連通分量。

如果您的圖形具有歐拉循環，則可以從任意節點啓動DFS，並且可以確保您的路徑是正確的。

如果你的圖具有歐拉線索，首先找到(out-degree) − (in-degree) = 1節點，並調用它source與(in-degree) − (out-degree) = 1找到節點，並調用它sink。您應該從source開始您的DFS，並儘可能避免去sink。這意味着無論何時在進入節點sink和某個其他節點之間有一個選項，只有當您沒有其他選項（不完全正確但使其更簡單）時，您應該轉到其他節點並使用sink節點。通過這種方式，您可以確定您最終得到了正確的線索。