EdgeComponentAuxGraph.construct

classmethod EdgeComponentAuxGraph.construct(G)

构建一个辅助图，用于编码节点之间的边连通性。

参数:

GNetworkX 图

备注

给定 G=(V, E)，初始化一个空的辅助图 A。选择一个任意的源节点 s。初始化一个可用节点集 N（可用作汇点）。算法从 N - {s} 中选取一个任意节点 t，然后计算最小的 st-割 (S, T)，其割值为 w。如果 G 是有向图，则使用 st-割或 ts-割中的最小值。然后，将边 (s, t) 以权重 w 添加到辅助图中。算法首先使用 S 作为可用节点，s 作为源节点进行递归调用，然后使用 T 和 t 进行递归。当源节点是唯一可用的节点时，递归停止。