算法设计:从大边缘列表中找到包含特定节点的CCs

Question

给出的是：大边缘列表，约有9000万到1亿个边，200万个节点.这些边构成了一个由数千个连通部件组成的巨型图。

我还有一个感兴趣的节点列表。我只想提取包含这些节点的CCs的边缘。

例如，下面是一个很小的例子:考虑一个包含3 CCs的小图。

edge_list = [(1,2), (3,2), (1,1), (4,5), (5,6), (4,6), (7,8), (8,9), (9,7)] #three CCs
## Below commands for visualization sake
G = nx.Graph() 
G.add_edges_from(edges)
nx.draw(G, with_labels=True)

我有感兴趣的节点：NOI = [1,5]

我想要一个做以下工作的函数：

CC_list = find_ccs(edge_list, NOI)
print(CC_list)
#output: [[(1,2), (3,2), (1,1)],
#          [(4,5), (5,6), (4,6)]]

注意，只返回包含NOIs的两个CCs的边缘。我想大规模地做这件事。

我对任何使用Networkx、StellarGraph或(最好是PySpark )的解决方案都是开放的。我可以读取边缘列表使用吡火花和一旦我有过滤边缘列表，我可以转换成一个CC使用任何库。

注意：整个图本身太大，无法使用networkx或stellarGraph完全构建。因此，我必须获得一个边缘列表，只提取我想要的ccs。上面的networkx示例仅用于可视化目的。

Answer 1

选择一个感兴趣的节点。从其中运行BFS以找到包含它的已连接组件。每次向CC中添加一个节点时，检查它是否是感兴趣的节点，并将其从集合中删除，以检查是否是。重复，直到找到所有包含感兴趣节点的CCs。

运行时间为O(V+E)，其中V&E是CCs的节点和边，包含感兴趣的节点，而不是较大的图。