提取由一组节点引起的图的子图的算法？

Question

我有一个无向图 G=(V,E)，我想提取 G 的子图，该子图由 V 的一组节点引起。现在我正在 Python?

中寻找执行此操作的算法

Answer 1

图应表示为字典，其中键是顶点的编号，值是该顶点的邻接表，表示为一个集合。

现在给定 S = {s1, s2, ..., sn} 使得 S 是 V 的子集。建立一个字典来表示归纳图。它应该包含 S 中的所有顶点，每个顶点都有空的邻接列表。

首先，我们初始化H:

H = {}  # Initialize empty dictionary.

for si in S:
    H[si] = set()

然后我们用正确的边填充H：

for si in S:
    adj = G[si]
    for v in adj:
        if v in S: 
            H[si].add(v) 
            H[v].add(si)

复杂度：O(V + E)。

Algorithm to extract subgraph of graph induced by a set of nodes?