Python Connected Components 边列表

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)