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