Python连接的组件边缘列表

Question

我在python中使用这些算法从边缘查找连接的组件。

​​

此算法返回这样的组件：

[ [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

使用apgl库在python中创建一个迷你图。 您可以使用apgl中的SparseGraph模块。 from apgl.graph import SparseGraph

启动一个具有所需节点数的稀疏图。 graph = SparseGraph(num_vertices)

然后，您可以通过添加图的节点之间的边来创建迷你图。 graph.addEdge(component1, component2)

然后，只需使用findConnectedComponents函数来查找连接的组件。 graph.findConnectedComponents()