Algoritmo per contare componenti collegati di un grafico in Python

Question

Io cerco di scrivere uno script che conta collegati componenti di un grafico e non riesco a ottenere la giusta soluzione. Ho un semplice grafico con 6 nodi (vertici), i nodi 1 e 2 sono collegati, e nodi 3 e 4 sono collegati (6 vertici; 1-2,3-4,5,6). Quindi il grafico contiene 4 componenti collegati. Io uso seguente script per contare componenti collegati, ma ottengo risultato sbagliato (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)

Qualcuno può aiutarmi a trovare l'errore?

Answer 1

A volte è più facile scrivere il codice che per leggerlo.

Mettere questo attraverso alcuni test, sono abbastanza sicuro che sarà sempre il lavoro il più a lungo ogni connessione è bidirezionale (come nel tuo esempio).

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()

Si noti che ho rimosso l'ID del nodo informazioni dalla sua posizione nella matrice è il suo ID. Fatemi sapere se questo programma non fa quello che è necessario.

Answer 2

Un disgiunto-set datastructure sarà davvero aiutare a scrivere codice chiaro qui, vedi Wikipedia .

L'idea di base è che si associa un set con ogni nodo nel grafico, e per ogni bordo si uniscono i gruppi di suoi due punti finali. Due set x e y sono la stessa cosa, se x.find() == y.find()

Ecco il più ingenuo attuazione (che ha un cattivo caso peggiore complessità), ma c'è un paio di ottimizzazioni della classe DisjointSet sulla pagina di Wikipedia di sopra del quale in una manciata di righe di codice extra rendono questo efficiente. Li omesso per chiarezza.

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)