算法 - 搜索網絡拓撲中的所有環路

Question

我得到了由節點和鏈路定義的網絡。我必須搜索網絡中的所有環路。將不會給出節點的座標。

是否有任何現有的算法或庫可以做到這一點。或者你能否給我一些想法我可以解決這個問題？我在.NET中編程。

我畫一個圖來說明什麼，我需要here

Answer 1

嘗試Distance vector Routing.

該算法找到最短路徑到所有其他節點的節點網絡。

Answer 2

假設您的邊緣沒有被定向，並且節點之間存在最大的一條邊，那麼深度優先的生成樹將覆蓋所有節點並指示週期的哪裏（這正是我認爲你的意思是循環）將發生。我們使用這種算法來查找化學結構中的「環」。有許多語言許多實現 - 在這裏是用一個小程序（http://oneweb.utc.edu/~Christopher-Mawata/petersen2/lesson20.htm）

Answer 3

的循環被稱爲cycles的教程，並this answer有很多信息給你的。