Algorithme de comptage des composants connectés d'un graphe en Python

Question

J'essaye d'écrire un script qui compte les composants connectés d'un graphe et je n'arrive pas à trouver la bonne solution. J'ai un graphe simple avec 6 noeuds (vertex), les noeuds 1 et 2 sont connectés, et les noeuds 3 et 4 sont connectés (6 vertexes; 1-2,3-4,5,6). Donc le graphique contient 4 composants connectés. J'utilise le script suivant pour compter les composants connectés, mais je me trompe de résultat (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) 

Quelqu'un peut-il m'aider s'il vous plaît à trouver l'erreur?

Answer 1

Parfois, il est plus facile d'écrire du code que de le lire. Mettez cela à travers quelques tests, je suis sûr que cela fonctionnera toujours aussi longtemps que chaque connexion est bidirectionnelle (comme dans votre exemple).

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

Notez que j'ai supprimé l'ID de l'information de noeud puisque sa position dans le tableau est son ID. Faites-moi savoir si ce programme ne fait pas ce dont vous avez besoin.

Answer 2

Une structure de données à structure disjointe vous aidera vraiment à écrire du code clair ici, voir Wikipedia.

L'idée de base est que vous associez un ensemble à chaque noeud dans votre graphe, et que pour chaque arête vous fusionnez les ensembles de ses deux extrémités. Deux ensembles x et y sont les mêmes si x.find() == y.find()

est ici la mise en œuvre la plus naïve (qui a une mauvaise complexité dans le pire cas), mais il y a quelques Optimisations de la classe DisjointSet sur la page wikipedia ci-dessus qui, dans une poignée d'extra les lignes de code rendent cela efficace. Je les ai omis pour plus de clarté.

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)