如何使用循環尋找算法找到歐拉路徑？

我試圖理解描述here的算法，但解釋真的不是很清楚：如何使用循環尋找算法找到歐拉路徑？

'tour' is a stack 

find_tour(u): 
    for each edge e=(u,v) in E: 
     remove e from E 
     find_tour(v) 
    prepend u to tour 

to find the tour, clear stack 'tour' and call find_tour(u), 
where u is any vertex with a non-zero degree.

什麼意思「前面加上」 u到堆棧？ tour中的元素如何用於find_tour？如果有人能向我解釋，會很高興，謝謝！

來源

2009-12-13 int3

閱讀我的博客，尋找無向圖的歐拉軌跡。 Hierholzer算法運行良好。 http://jeewanthad.blogspot.com/2012/11/eulerian-trail.html – Jeewantha 2012-12-04 05:11:14

堆棧'prepend'是一個推動。所以你將頂點u推到棧頂。這個想法是，你從任何至少有一個邊的頂點開始。沿着所有邊緣離開起始頂點，在移除邊緣後遞歸地調用函數（這樣你就不會回來那個相同的邊緣）。

旅遊中的元素根本不被find_tour使用。它只是一個數據存儲庫，用於獲取算法完成後遍歷圖的順序。只要繼續調用tour.pop（）直到堆棧爲空，就可以返回巡視。如果該頂點有許多邊，它可能會多次包含相同的頂點，但是因爲每次在遞歸調用find_tour之前，都會刪除離開頂點的邊，該函數將最終完成。

Oh和E是圖中的所有的邊緣上，（U，V）是從u到v的邊緣。

來源

2009-12-13 13:27:57

現在你已經解釋了它，它看起來很明顯。謝謝！ – int3 2009-12-13 15:41:20

即算法是用於向圖。對於無向圖請記住：

(u,v) == (v, u)

來源

2012-07-02 09:09:47 PerseP

如何使用循環尋找算法找到歐拉路徑？

回答

相關問題