使用寬度優先搜索的連接組件

我需要找到圖形的連接組件。我有節點的鄰居列表：使用寬度優先搜索的連接組件

neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]]

例如節點0有鄰居4，節點1有鄰居2和5等... 我想找到的是連接組件的列表。假設節點0具有鄰居4，但鄰居4也是節點9的鄰居。節點9也具有數目爲10和15的鄰居。所以名單會像

[4,10,15....] etc including following neihbours.

我想要使用的方法是廣度優先搜索。我寫了下面的算法：當我運行它

def bfs(neighbour_list, node): 

    label_list =[] 
    for sub_neighbour_list in neighbour_list: 

     label_list.append(node) 

     queue = [node] 

    while queue: 
     u = queue[0] 
     for sub_neighbour in neighbour_list[u]: 
      if sub_neighbour not in queue: 
      label_list[sub_neighbour] = 0 
      queue.append(sub_neighbour) 
      queue.pop(0) 

    print(label_list) 
    return (label_list)

沒有任何反應。哪裏不對？

感謝

來源

2014-10-01 Hannah

縮進「if」語句後面的三行，以及第一個「for」後面的所有行，但不包括「print」語句。 – Marichyasana 2014-10-01 23:49:15

@Marichyasana仍然沒有做任何事 – Hannah 2014-10-01 23:52:30

sub_neighbour_list被定義在哪裏？ – jedwards 2014-10-02 00:01:47

什麼：

neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], 
       [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], 
       [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], 
       [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], 
       [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]] 

def bfs(neighbour_list, root): 
    queue = [] 
    seen = set() 

    queue.append(root) 
    seen.add(root) 

    while queue: 
     cn = queue.pop(0) 
     print("Current node: %d" % cn) 
     for nn in neighbour_list[cn]: 
      if nn not in seen: 
       queue.append(nn) 
       seen.add(nn) 
       print(" Found %d" % nn) 

    return seen 

print bfs(neighbour_list, 0)

，輸出：

 
Current node: 0 
    Found 4 
Current node: 4 
    Found 9 
Current node: 9 
    Found 10 
    Found 15 
Current node: 10 
    Found 6 
Current node: 15 
    Found 21 
Current node: 6 
    Found 12 
Current node: 21 
    Found 27 
Current node: 12 
Current node: 27 
set([0, 4, 6, 9, 10, 12, 15, 21, 27])

注意set不排序。所以這個函數的結果會返回所有到達root的節點，但不會以算法達到它的任何順序返回。如果你想這樣做，你可以很容易地將seen更改爲列表。

來源

2014-10-02 00:10:21 jedwards

.append和.add之間的區別是什麼？ @jedwards你追加列表，但添加到詞典？ – Hannah 2014-10-02 00:15:52

你把'.append（）'放到一個列表中，'.add（）'放到一個集合中。一個集合是一個無序的集合，而一個列表是有序的。 – 2014-10-02 00:16:45

和queue.pop（0）和隊列[0]之間的區別是什麼？他們有沒有相同的結果？ @Tom Dalton – Hannah 2014-10-02 00:19:52

除了jedwards的回答，我會建議使用數據結構deque from collections import deque，然後queue = deque()和queue.popleft()。這應該加快性能。

來源

2017-05-04 09:09:05 Ale

使用寬度優先搜索的連接組件

回答

相關問題