1

我需要找到图形的连通分量。我有一个邻居节点列表：

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)

当我运行它时没有任何反应。怎么了？

谢谢

4

2 回答 2

1

关于什么：

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)

哪个输出：

当前节点：0
  找到 4
当前节点：4
  找到 9
当前节点：9
  找到 10
  找到 15
当前节点：10
  找到 6
当前节点：15
  找到 21
当前节点：6
  找到 12
当前节点：21
  找到 27
当前节点：12
当前节点：27
设置（[0, 4, 6, 9, 10, 12, 15, 21, 27]）

请注意，set不是订购的。所以这个函数的结果将返回所有可到达的节点root，但不是按照算法到达它的任何顺序。如果你愿意，你可以很容易地seen变成一个列表。

于 2014-10-02T00:10:21.853 回答
0

此生成器函数将在表示为邻接列表的图中生成所有连接的组件。它还使用collections.deque队列而不是队列list开头的有效弹出。

from collections import deque

def connected_components(graph):
    seen = set()

    for root in range(len(graph)):
        if root not in seen:
            seen.add(root)

            component = []
            queue = deque([root])

            while queue:
                node = queue.popleft()
                component.append(node)
                for neighbor in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        queue.append(neighbor)
            yield component

演示：

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]]

print(list(connected_components(neighbour_list)))
# [[0, 4, 9, 10, 15, 6, 21, 12, 27],
#  [1, 2, 5, 3, 8, 14],
#  [7, 13, 19, 20, 18, 26, 17, 30, 31, 11],
#  [16, 22, 23, 24, 28, 25, 29]]
于 2019-10-03T15:31:55.397 回答