如何找到连通分量？

Question

我正在为一个类 Graph 编写一个函数 get_connected_components ：

 def get_connected_components(self):
    path=[]
    for i in self.graph.keys():
        q=self.graph[i]
        while q:
            print(q)
            v=q.pop(0)
            if not v in path:
                path=path+[v]
    return path

我的图表是：

 {0: [(0, 1), (0, 2), (0, 3)], 1: [], 2: [(2, 1)], 3: [(3, 4), (3, 5)], \
4: [(4, 3), (4, 5)], 5: [(5, 3), (5, 4), (5, 7)], 6: [(6, 8)], 7: [], \
8: [(8, 9)], 9: []}

其中键是节点，值是边。我的功能给了我这个连接的组件：

 [(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), \
(5, 4), (5, 7), (6, 8), (8, 9)]

但是我会有两个不同的连接组件，例如：

 [[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), \
(5, 3), (5, 4), (5, 7)],[(6, 8), (8, 9)]]

我不明白我在哪里犯了错误。谁能帮我？

原文由 fege 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

让我们简化图形表示：

 myGraph = {0: [1,2,3], 1: [], 2: [1], 3: [4,5],4: [3,5], 5: [3,4,7], 6: [8], 7: [],8: [9], 9: []}

这里我们有一个函数返回一个字典，它的键是根，它的值是连接的组件：

 def getRoots(aNeigh):
    def findRoot(aNode,aRoot):
        while aNode != aRoot[aNode][0]:
            aNode = aRoot[aNode][0]
        return (aNode,aRoot[aNode][1])
    myRoot = {}
    for myNode in aNeigh.keys():
        myRoot[myNode] = (myNode,0)
    for myI in aNeigh:
        for myJ in aNeigh[myI]:
            (myRoot_myI,myDepthMyI) = findRoot(myI,myRoot)
            (myRoot_myJ,myDepthMyJ) = findRoot(myJ,myRoot)
            if myRoot_myI != myRoot_myJ:
                myMin = myRoot_myI
                myMax = myRoot_myJ
                if  myDepthMyI > myDepthMyJ:
                    myMin = myRoot_myJ
                    myMax = myRoot_myI
                myRoot[myMax] = (myMax,max(myRoot[myMin][1]+1,myRoot[myMax][1]))
                myRoot[myMin] = (myRoot[myMax][0],-1)
    myToRet = {}
    for myI in aNeigh:
        if myRoot[myI][0] == myI:
            myToRet[myI] = []
    for myI in aNeigh:
        myToRet[findRoot(myI,myRoot)[0]].append(myI)
    return myToRet

让我们试试看：

 print getRoots(myGraph)

{8: [6, 8, 9], 1: [0, 1, 2, 3, 4, 5, 7]}

原文由 jimifiki 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我喜欢这个算法：

 def connected_components(neighbors):
    seen = set()
    def component(node):
        nodes = set([node])
        while nodes:
            node = nodes.pop()
            seen.add(node)
            nodes |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

不仅短小精悍，而且速度很快。像这样使用它（Python 2.7）：

 old_graph = {
    0: [(0, 1), (0, 2), (0, 3)],
    1: [],
    2: [(2, 1)],
    3: [(3, 4), (3, 5)],
    4: [(4, 3), (4, 5)],
    5: [(5, 3), (5, 4), (5, 7)],
    6: [(6, 8)],
    7: [],
    8: [(8, 9)],
    9: []}

edges = {v for k, vs in old_graph.items() for v in vs}
graph = defaultdict(set)

for v1, v2 in edges:
    graph[v1].add(v2)
    graph[v2].add(v1)

components = []
for component in connected_components(graph):
    c = set(component)
    components.append([edge for edges in old_graph.values()
                            for edge in edges
                            if c.intersection(edge)])

print(components)

结果是：

 [[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), (4, 3), (4, 5), (5, 3), (5, 4), (5, 7)],
 [(6, 8), (8, 9)]]

谢谢，阿帕帕拉发现了这个错误。

原文由 pillmuncher 发布，翻译遵循 CC BY-SA 4.0 许可协议