NetworkX中运行Steiner算法遇图分裂，求合并连通组件方法

使用pcst_fast库计算Steiner路径时，由于原始路网图包含多个独立连通组件，导致仅生成了部分选中节点的连通路径，无法覆盖所有目标Steiner节点，需要解决如何处理多组件图以得到包含所有目标节点的完整结果。

用户代码如下：

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import random
import geopandas as gpd
import momepy
import pcst_fast
from pyproj import CRS
import fiona

roads = gpd.read_file("ala3.gpkg")
roads['length'] = roads.geometry.length
lens = list(roads.length.copy())
roads.crs = "EPSG:4326"
roads = roads.to_crs(crs='EPSG:4326')

pts = gpd.read_file("alapts.gpkg")

F = momepy.gdf_to_nx(roads, approach="primal", length="length")

gdf_F = momepy.nx_to_gdf(F)[1]

# 原代码变量错误：G未定义，应替换为F
coords = {}
for i, j, in enumerate(list(F.nodes)):
    coords[i] = j


lengths = nx.get_edge_attributes(F, "length")
nx.set_edge_attributes(F, values=lengths, name="weight")

G = nx.relabel.convert_node_labels_to_integers(F, label_attribute='old_label')

# define parameters for input, choose num of random nodes

num_steiners = 200
edge_list = [[int(u), int(v)] for u, v in G.edges()]
node_id = [i for i in range(len(G.nodes))]
prizes = [0]*len(G.nodes)

selection = random.sample(list(range(len(prizes))), num_steiners)

for s in selection:
    prizes[s] = 9999 # some high value to catch no matter what

costs = np.array(list(nx.get_edge_attributes(G, "length").values()))
root = -1
num_clusters = 1

vertices, eg = pcst_fast.pcst_fast(edge_list, prizes, costs, root, num_clusters, "gw", 1)

# 原代码变量错误：node_list应替换为vertices
print("Are all steiner nodes a subset of the outputed vertices?")
print(set(selection).issubset(set(vertices)))

方法1：对每个连通分量单独运行PCST（推荐） #

pcst_fast默认仅处理连通图，当输入图存在多组件时，只会处理包含最多目标节点的组件。因此拆分每个连通分量，分别计算分量内的Steiner树，再合并结果是最贴合真实路网的方案：

# 获取图的所有连通分量
components = list(nx.connected_components(G))

all_vertices = []
all_edges = []

for comp in components:
    # 提取当前分量的子图
    subG = G.subgraph(comp).copy()
    # 重新标记子图节点为连续整数（适配pcst_fast的输入要求）
    subG = nx.relabel.convert_node_labels_to_integers(subG)
    
    # 建立原节点ID与子图新ID的映射
    node_map = {old_id: new_id for new_id, old_id in enumerate(subG.nodes())}
    reverse_node_map = {v: k for k, v in node_map.items()}
    
    # 准备当前分量的PCST输入参数
    sub_edge_list = [[u, v] for u, v in subG.edges()]
    sub_prizes = [0] * len(subG.nodes())
    
    # 筛选当前分量内的目标Steiner节点
    sub_selection = [node_map[s] for s in selection if s in comp]
    for s in sub_selection:
        sub_prizes[s] = 9999
    
    # 无目标节点的分量直接跳过
    if not sub_selection:
        continue
    
    sub_costs = np.array(list(nx.get_edge_attributes(subG, "length").values()))
    
    # 运行PCST计算当前分量的Steiner树
    sub_vertices, sub_edges = pcst_fast.pcst_fast(sub_edge_list, sub_prizes, sub_costs, -1, 1, "gw", 1)
    
    # 将结果转换回原节点ID
    original_vertices = [reverse_node_map[v] for v in sub_vertices]
    original_edges = [(reverse_node_map[u], reverse_node_map[v]) for u, v in sub_edges]
    
    # 合并所有分量的结果
    all_vertices.extend(original_vertices)
    all_edges.extend(original_edges)

# 验证所有目标节点是否被包含
print("Are all steiner nodes a subset of the outputed vertices?")
print(set(selection).issubset(set(all_vertices)))

方法2：添加虚拟边强制连通图（仅适用于允许虚拟路径的场景） #

如果必须将整个图变为连通结构，可以添加虚拟边连接各分量的代表节点，设置虚拟边的成本远大于真实路网长度，避免干扰真实路径选择，但会引入非真实路网的连接：

# 获取每个连通分量的代表节点（取分量第一个节点）
component_reps = [list(comp)[0] for comp in components]

# 设置虚拟边成本为真实路网最大长度的10倍
max_real_cost = max(nx.get_edge_attributes(G, "length").values())
for i in range(len(component_reps)-1):
    G.add_edge(component_reps[i], component_reps[i+1], length=max_real_cost * 10)

# 重新运行原PCST流程
edge_list = [[int(u), int(v)] for u, v in G.edges()]
costs = np.array(list(nx.get_edge_attributes(G, "length").values()))

vertices, eg = pcst_fast.pcst_fast(edge_list, prizes, costs, root, num_clusters, "gw", 1)

# 验证结果
print("Are all steiner nodes a subset of the outputed vertices?")
print(set(selection).issubset(set(vertices)))

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