Список ребер подключенных компонентов Python

Question

Я использую эти алгоритмы в python для нахождения связанных компонентов из ребер.

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 

Эти алгоритмы возвращают компоненты, как это:

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

Я хотел бы иметь список всех ребер связных компонент, как это:

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

в том же порядке, из Предыдущий список, но я не знаю, как создает этот список

Благодарим за помощь.

Answer 1

Примечание: Это не требует зависимости от python.

Я поделюсь своим подходом с рекурсивным поиском глубины. Я предполагаю, что граф двунаправлен, и следующий код можно легко манипулировать для ориентированного графа.

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

Создайте мини-график в python, используя apgl-библиотеку. Вы можете использовать модуль SparseGraph из apgl. from apgl.graph import SparseGraph

Инициировать разрез с требуемым количеством узлов. graph = SparseGraph(num_vertices)

Затем вы можете создать мини-граф, добавив ребра между узлами графа. graph.addEdge(component1, component2)

Затем просто найдите функцию findConnectedComponents, чтобы найти подключенные компоненты. graph.findConnectedComponents()