Liste des arêtes des composants connectés Python

Question

J'utilise ces algorithmes en python pour trouver des composants connectés à partir d'arêtes.

components = [] 

def connected_components(pairs): 
    for a, b in pairs: 
     for component in components: 
      if a in component: 
       for i, other_component in enumerate(components): 
        if b in other_component and other_component != component: # a, and b are already in different components: merge 
         component.extend(other_component) 
         components[i:i+1] = [] 
         break # we don't have to look for other components for b 
       else: # b wasn't found in any other component 
        if b not in component: 
         component.append(b) 
       break # we don't have to look for other components for a 
      if b in component: # a wasn't in in the component 
       component.append(a) 
       break # we don't have to look further 
     else: # neither a nor b were found 
      components.append([a, b]) 
    return components 

Ce algorithmes de retour des composants comme ceci:

[ [n1,n2,n4],[n3,n5] ] 

Je voudrais avoir la liste de tous les bords des composants connectés comme ceci:

[ [(n1,n2),(n2,n4),(n4,n1)],[(n3,n5)] ] 

dans le même ordre du liste précédente mais je ne sais pas comment crée cette liste

Nous vous remercions de votre aide.

Answer 1

Remarque: Cela ne nécessite aucune dépendance python.

Je vais partager mon approche, avec une recherche récursive en profondeur. Je suppose que le graphique est bidirectionnel et le code suivant peut être facilement manipulé pour le graphique dirigé.

pairs = [] // edge list 
adj_list = {} // adjacency list 
vis = [] // visited_list 
connected_components = [] // contains all the connected components 
temp_component = [] 

// basic depth first search 
def dfs(node): 
    vis[node] = "true" 
    temp_component.append(node) 
    for neighbour in adj_list[node]: 
     if vis[neighbour] == "false": 
      dfs(neigbour) 

//main 
for a,b in pairs: 
if a not in adj_list: 
    adj_list[a] = [] 
if b not in adj_list: 
    adj_list[b] = [] 
adj_list[a].append(b) 
adj_list[b].append(a) 
vis["a"] = "false" 
vis["b"] = "false" 

for a,b in pairs: 
    temp_component = [] 
    if vis[a] == "false": 
    dfs(a) 
if len(temp_component) > 0: 
    connected_components.append(temp_component) 

// once you have connected components you can get the edge lists in connected component as well 
answer = [] 
for component in connected_components: 
    temp_pairs = [] // contains the pair of edges for the current connected component 
    for node in component: 
     for i,j in pairs: 
      if (node == i or node == j) and (i,j) not in temp_node: 
       temp_node.append(i,j) 
    answer.append(temp_pairs) 

Answer 2

Créez un mini-graphique en python à l'aide de la bibliothèque apgl. Vous pouvez utiliser le module SparseGraph d'apgl. from apgl.graph import SparseGraph

Initier un segment avec le nombre de nœuds requis. Ensuite, vous pouvez créer un mini graphique en ajoutant des arêtes entre les nœuds du graphique. Ensuite, utilisez simplement la fonction findConnectedComponents pour trouver les composants connectés. graph.findConnectedComponents()