Pythonでグラフの連結成分をカウントするためのアルゴリズム

Question

私は数がグラフのコンポーネントを接続して、私は適切なソリューションを得ることができないというスクリプトを記述してみてください。 私は、6つのノード（頂点）との簡単なグラフを有する1ノードと2が接続され、ノード3及び4が接続されている（; 1-2,3-4,5,6 6つの頂点）。だから、このグラフは、4つの連結成分が含まれています。私は連結成分をカウントするには、次のスクリプトを使用しますが、私は間違った結果（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)

缶誰も助けてください、私は間違いを見つける？

Answer 1

時には、それはそれを読むことよりも書き込みコードに簡単です。

私はかなり確信している、いくつかのテストを介してこれを入れてよ、常に仕事の長いすべての接続は、（例えば、あなたの例のように）双方向性である限ります。

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を除去することを

注意。このプログラムはあなたが必要なものを行っていない場合、私に教えてくださいます。

Answer 2

A互いに素セットデータ構造は本当にウィキペディア。

基本的な考え方は、あなたのグラフの各ノードとのセットを関連付けることで、各エッジのためにあなたは、その2つのエンドポイントのセットをマージします。 x

場合、2つのセットyとx.find() == y.find()は同じです ここで最も単純な実装（悪い最悪の場合の複雑さを持っている）のですが、コードの余分な行の一握りで、これが効率的にその上にWikipediaのページでDisjointSetクラスの最適化のカップルがあります。私は、明確にするためにそれらを省略します。

nodes = [[1, [2]], [2, [1]], [3, [4]], [4, [3]], [5, []], [6, []]]

def count_components(nodes):
    sets = {}
    for node in nodes:
      sets[node[0]] = DisjointSet()
    for node in nodes:
        for vtx in node[1]:
            sets[node[0]].union(sets[vtx])
    return len(set(x.find() for x in sets.itervalues()))

class DisjointSet(object):
    def __init__(self):
        self.parent = None

    def find(self):
        if self.parent is None: return self
        return self.parent.find()

    def union(self, other):
        them = other.find()
        us = self.find()
        if them != us:
            us.parent = them

print count_components(nodes)