在無向圖中發現週期的大O複雜性

我需要找到找到由50個節點組成的無向圖中的所有周期的複雜性。而且，如果圖形變大，複雜性會發生變化，如果網絡增長很大，情況會怎樣。另外，如果我只找到幾個週期，那麼我怎麼才能找到在圖中找到幾個週期的複雜性。在無向圖中發現週期的大O複雜性

感謝您的期待！

2010-10-06 Hassu

如果您事先知道有50個節點，那麼複雜度爲O（1），因爲它只需要一定的時間來查找所有的週期。 TSP也是恆定時間。 :-)只有當圖（或其他輸入）的大小無界時，算法複雜性才成爲問題，並且複雜性不會隨着圖的增大而變化，因爲它不取決於大小輸入。如果您更改算法，複雜性只會發生變化。 – 2010-10-06 15:06:36

感謝您的回答。實際上，我有一個算法，通過計算消息路徑或圖中所有節點的節點ID，匯聚節點在無向圖中找到幾個週期。例如，在一個圖表中存在10個不同大小的週期，它只能找到其中的前五個，所以在那種情況下，算法的複雜性是什麼。 – Hassu 2010-10-06 15:28:27

http://stackoverflow.com/questions/526331/cycles-in-an-undirected-graph可能的重複 – 2010-10-25 00:53:48

使用深度優先搜索和主動標記節點，您可以簡單地發現週期，只要注意您在搜索中遇到標記節點時的任何時間。

這是一個O(V+E)的方法，我相信，其中V是頂點或節點的數量，E是邊或連接的數量。

如果將節點放在堆棧的特定分支上，還可以輕鬆確定循環路徑。只要確保每次回溯時都彈出一個節點。

來源

2010-10-06 14:57:20

給定的圖可以具有指數週期數（以圖的大小）。考慮一個二分圖，其中，v _我連接到瓦特_{I + 1％N}並且w _我連接到V _{I + 1％N}。

所以除非你有特定類型的圖表，否則多項式時間解決方案沒有希望。以指數形式運行的解決方案非常易於構建。考慮頂點的所有排列，看看這個排序是否會導致一個循環。

當然，實際上你可以想出比這更快的解決方案。

來源

2010-10-25 00:22:58 user485440

在無向圖中發現週期的大O複雜性

回答

相關問題