算法在Python统计图的连接组件 [英] Algorithm for counting connected components of a graph in Python

问题描述

我尝试写计数图的连接组件的脚本，我不能得到正确的解决方案。 我有6个节点（顶点），节点1和2被连接，并且节点3和4连接（6顶点; 1-2,3-4,5,6）的简单图形。因此，图包含4连接​​组件。我用下面的脚本来计算连接的组件，但我得到错误的结果（2）。

I try to write a script that counts connected components of a graph and I can't get the right solution. I have a simple graph with 6 nodes (vertexes), nodes 1 and 2 are connected, and nodes 3 and 4 are connected (6 vertexes; 1-2,3-4,5,6). So the graph contains 4 connected components. I use following script to count connected components, but I get wrong result (2).

nodes = [[1, [2], False], [2, [1], False], [3, [4], False], [4, [3], False], [5, [], False], [6, [], False]]
# 6 nodes, every node has an id, list of connected nodes and boolean whether the node has already been visited    

componentsCount = 0

def mark_nodes( list_of_nodes):
    global componentsCount
    componentsCount = 0
    for node in list_of_nodes:
      node[2] = False
      mark_node_auxiliary( node)

def mark_node_auxiliary( node): 
    global componentsCount
    if not node[2] == True: 
      node[2] = True
      for neighbor in node[1]:
        nodes[neighbor - 1][2] = True
        mark_node_auxiliary( nodes[neighbor - 1])
    else:
      unmarkedNodes = []
      for neighbor in node[1]:
        if not nodes[neighbor - 1][2] == True:  # This condition is never met. WHY???
          unmarkedNodes.append( neighbor)
          componentsCount += 1   
      for unmarkedNode in unmarkedNodes:
        mark_node_auxiliary( nodes[unmarkedNode - 1])

def get_connected_components_number( graph):
    result = componentsCount
    mark_nodes( graph)
    for node in nodes:
      if len( node[1]) == 0:      # For every vertex without neighbor...  
        result += 1               # ... increment number of connected components by 1.
    return result

print get_connected_components_number( nodes)

任何人都可以请帮我找错了吗？

Can anyone please help me find the mistake?

推荐答案

有时更容易编写code，而不是阅读。

Sometimes it's easier to write code than to read it.

将这个经过一些测试，我是pretty的肯定它会永远只要努力，因为每个连接是双向的（如在你的例子）。

Put this through some tests, I'm pretty sure it'll always work as long as every connection is bidirectional (such as in your example).

def recursivelyMark(nodeID, nodes):
    (connections, visited) = nodes[nodeID]
    if visited:
        return
    nodes[nodeID][1] = True
    for connectedNodeID in connections:
        recursivelyMark(connectedNodeID, nodes)

def main():
    nodes = [[[1], False], [[0], False], [[3], False], [[2], False], [[], False], [[], False]]
    componentsCount = 0
    for (nodeID, (connections, visited)) in enumerate(nodes):
        if visited == False:
            componentsCount += 1
            recursivelyMark(nodeID, nodes)
    print(componentsCount)

if __name__ == '__main__':
    main()

请注意，我删除的ID从节点信息，因为它在数组中的位置是其ID。让我知道如果这个程序没有你所需要的。

Note that I removed the ID from the node information since its position in the array is its ID. Let me know if this program doesn't do what you need.

这篇关于算法在Python统计图的连接组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！