图的连通分量算法

Question

我正在寻找最有效的算法，以便找到网络中的连通分量数以及每个连通分量的节点数。

示例：

给定以下输入：

no_of_nodes = 8

graph_to = [1,1,3,5,6]

graph_from = [2,6,4,7,3]

我会收到以下输出：

[[1, 2, 3, 4, 6], [5, 7], [8]]

这是我目前拥有的：

def connections(no_of_nodes, graph_from, graph_to):

    nodes = list(range(1, no_of_nodes+1))
    
    singles = []
    
    # removes all unconnected nodes

    for node in nodes:
        if node not in graph_from + graph_to:
            singles.append([node])
    
    conns = [[graph_from[0],graph_to[0]]]
    
    graph_from.pop(0)
    graph_to.pop(0)
    
    n=0
    k = 0
    
    while n < len(graph_from):
        
        x = graph_from[n]
        y = graph_to[n]

        if x in conns[k]:
            conns[k].append(y)
            graph_from.pop(n)
            graph_to.pop(n)
        else:
            conns.append([x,y])
            k += 1
            print(conns)
            n+=1
    
    return conns + singles

我找到了一种迭代节点的方法，假设所有连接都相邻地放置在 graph_from 列表中，但这当然不会适用于所有情况。

编辑：我正在寻找一种无需导入模块即可执行此操作的方法

Answer 1

使用networkx:

import networkx as nx

no_of_nodes = 8
graph_to = [1, 1, 3, 5, 6]
graph_from = [2, 6, 4, 7, 3]

g = nx.Graph(zip(graph_from, graph_to))
g.add_nodes_from(range(1, no_of_nodes + 1))

res = list(nx.connected_components(g))
print(res)

输出

[{1, 2, 3, 4, 6}, {5, 7}, {8}]

Answer 2

使用上面回答的总结过程，我能够制定以下内容，在测试后检查一下。

def connected(graph_nodes, graph_from, graph_to):
 
    
    unseen = [i for i in range(1,graph_nodes + 1)]
    
    edges = [[graph_from[i],graph_to[i]] for i in range(len(graph_from))]
    
    
    connects = []
    
    while unseen != []:
        start = unseen[0]
        connection = []

        queue = [start]
        unseen.remove(start)

        while queue != []:

            end = queue[-1]

            if end not in connection:
                connection.append(end)

            queue = queue[:-1]
            
            for k in edges:

                if k[0] == end:
       
                    queue.append(k[1])
                    unseen.remove(k[1])
            
        connects.append(connection)

        
   
    return connects

Answer 3

基本的连通集算法是：

将所有节点放入一个集合unseen.
如果 unseen 不为空，则从中删除一个随机元素并将其放入队列中。如果 unseen 为空，则您完成了。
当队列中有元素时，执行以下操作
- 移除队列的前端元素。
- 找到连接到该前面元素的所有 unseen 个元素。从 unseen 中删除它们并将它们添加到队列中。
重复直到队列为空。一旦队列为空，您就从图中删除了一个连接的组件。返回第 2 步。

[已编辑以改进格式。我想出了如何做双重嵌套]

图的连通分量算法

Algorithm for Connected Components of Graph

python

algorithm

graph-theory