Networkx中是否存在可根据输入节点返回连通子图的函数

你需要的是包含指定终端节点集的最小连通子图，G.subgraph无法满足需求的原因是它仅保留你输入的节点，不会自动补充连接这些节点所需的中间路径节点，因此输入节点不连通时返回的子图也会是多连通分量结构。 #

方案1：调用内置steiner_tree函数（推荐） #

NetworkX 内置的nx.steiner_tree函数完全匹配需求，它会自动补充连接所有终端节点所需的最短路径中间节点，返回连通的子图结构。
代码示例：

import networkx as nx

# G 为你的原始图对象
terminals = ["A", "B", "G", "I"]
# 未加权图设置weight=None，加权图可传入对应权重字段名，比如weight='length'
target_subgraph = nx.steiner_tree(G, terminals, weight=None)

# 输出结果节点，你的示例场景中会返回 ['A','B','G','E','I']
print(list(target_subgraph.nodes()))

注意：nx.steiner_tree默认返回权重最小的树结构，仅保留连接所需的最少边。如果你需要保留结果节点在原图中的所有关联边，可通过G.subgraph(target_subgraph.nodes())二次生成子图。

方案2：手动实现（兼容旧版本NetworkX） #

如果你的NetworkX版本较低没有内置steiner_tree，可以通过收集所有终端节点对的最短路径节点，再生成子图的方式实现，效果和方案1一致：

import networkx as nx

terminals = ["A", "B", "G", "I"]
required_nodes = set(terminals)

# 遍历所有终端节点对，收集最短路径上的所有节点
for u in terminals:
    for v in terminals:
        if u >= v:
            continue
        shortest_path = nx.shortest_path(G, source=u, target=v)
        required_nodes.update(shortest_path)

# 生成最终连通子图，默认保留所有节点间的原图边
target_subgraph = G.subgraph(required_nodes)

内容的提问来源于stack exchange，提问作者Acbogu