在Python中找到更好的代碼尋找環節

我用非常愚蠢的方式編寫了一個環檢測程序。任何人都可以幫助改善它嗎？以下代碼是查找所有5個成員的環。我需要一個能夠找到N元環的通用函數，其中N通常小於10.感謝100萬！在Python中找到更好的代碼尋找環節

在我的問題中，我有大約2000分。每個點連接到其他幾個點，這些連接點存儲在neighbor_list中。 point[i].neighbor_list()返回點[i]的鄰居列表。下面的代碼中的想法是從一個點開始，遍歷它的鄰居列表並且它是鄰居的鄰居列表，以此類推，以找到路線/週期/環以返回到原始點。我的代碼的核心部分是以下內容，它僅查找由5個點組成的環。我需要一個通用代碼來查找所有N成員環。如果有任何不清楚的地方，請留下評論。

for r0 in range(2000): #ring member 0 
    rin.append(r0) 
    for r1 in point[r0].neighbor_list(): 
     rin.append(r1) #ring member 1 
     for r2 in point[r1].neighbor_list(): 
      if r2 == r0: continue # to avoid the case of a-b-a ... 
      else: rin.append(r2) 
      for r3 in point[r2].neighbor_list(): 
       if r3 == r1: continue 
       else: rin.append(r3) 
       for r4 in point[r3].neighbor_list(): 
        if r4 == r2: continue 
        else: rin.append(r4) 
        for r5 in point[r4].neighbor_list(): 
         if r5 == r0: 
          rin.append(r5) 
          rings.append(list(rin)) # find a ring, save it 
          rin.pop() 
         else: continue 
        rin.pop() 
       rin.pop() 
      rin.pop() 
     rin.pop() 
    rin.pop()

來源

2013-08-27 Greg

'ring'是什麼意思？ – That1Guy

這些對象是什麼讓'neighbor_list（）'起作用？（儘管顯而易見，它又會迴歸什麼！） –

to That1Guy和Jon Clements：謝謝你的迴應。我很抱歉這個令人困惑的消息。每個點連接到多個點，這些連接點存儲在其neighbor_list中。並且點[i] .neighbor_list（）返回這些鄰居的列表。所以這個想法是從一個點開始的，遍歷它的鄰居列表並且它是鄰居的鄰居列表，看看是否有路由返回到原始點。路線被定義爲一個環。讓我知道如果它仍然不清楚。 – Greg

您試圖在無向圖中查找大小爲N的週期。

你可以找到所有的週期，然後選擇合適大小的週期。看到這個答案。 Finding all cycles in undirected graphs

來源

2013-08-27 16:06:17 MatthieuW

感謝您的回答。我需要一些時間來學習「廣度優先搜索」，看看它是否適合我。 – Greg

我放的第一個鏈接是不正確的，這是爲了檢測一個週期。我很快將其編輯爲「所有循環」，但速度不夠快。你很幸運，甚至有一個回答這個問題的Python代碼。（我沒有測試它） – MatthieuW

再次感謝。鏈接中的python代碼似乎不適合我的問題。我有2000點和大約8000個邊緣，這可能使找不到所有的週期。我試圖給休息一下，「如果len（path）> 10：break」，到圖中邊緣的循環：「，這似乎也沒有幫助。我從來沒有找到任何循環的代碼，而我的代碼需要1秒鐘來找到所有的5分循環。 – Greg

在Python中找到更好的代碼尋找環節

回答

相關問題