将列表列表转换为图的连通分量以查找节点度

Question

我有一个列表列表（Python）的输入，如下所示：

lst = [['1', '2'], ['1', '3', '2'], ['5'], ['4', '6']]

其中每个整数字符串代表图中的一个节点，列表中的每个列表代表节点之间的连通性。所以，在上面的例子中，节点

{1, 2, 3}

 全部相连，

{4, 6}

 相连，

{5}

 相连。我想计算出上图的节点度。因此，输出将是连接到每个节点的边的数量，即：

node_degrees = {'1': 2, '2': 2, '3': 2, '4': 1, '5': 0, '6': 1}

因为 2 个节点连接到节点

'1'

，2 个节点连接到节点 

'2'

，依此类推。可以注意到重复项被忽略，因为我们关心的是每个节点的连接组件和节点度。

为了最大限度地减少重新计数的工作量，我正在考虑一种算法来遍历每个列表列表，创建一个集合，然后以某种方式计算集合的大小，但这行不通，因为病理情况下

lst = [['1', '2'], ['2', '3'], ['3', '4'], ['4', '5']]

这会产生

{'1': 1, '2': 2, '3': 2, '4': 2, '5': 1}

。

我不确定如何最大程度地减少已完成的工作 - 集合交集可能有效，而且我还探索了联合查找，但我相信这不是必需的，因为我需要做的就是迭代列表列表，查找并跟踪在字典中连接到节点的边的数量，如果之前没有遇到过该节点，则不断更新它。然而，暴力破解是

O(n^2)

，并不理想。

是否有一种算法可以有效地遍历这种输入数据格式，并且无需在此过程中创建不必要的数据结构？

我还试图看看除了图算法之外是否可以用不同的方式建模 - 也许以某种方式看到集合交集的等效公式或更简单的链表实现，但我不确定如何考虑另一种方法除了图表之外。表述这一点的另一种方法是考虑列表列表中不同元素之间的关联。

Answer 1

只需为您的图构建邻接表即可。

这里是Python：

from itertools import combinations

lst = [['1', '2'], ['1', '3', '2'], ['5'], ['4', '6']]

adj = {}
for clique in lst:
    for u,v in combinations(clique, 2):
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
# adj = {'1': {'2', '3'}, '2': {'1', '3'}, '3': {'2', '1'}, '4': {'6'}, '6': {'4'}}

degrees = {v: len(neighbours) for v,neighbours in adj.items()}
# degrees = {'1': 2, '2': 2, '3': 2, '4': 1, '6': 1}