寻求UCG转UAG的剪枝算法：最大化边权且满足连通性要求

你的需求本质就是求解无向图的最大生成树，完全匹配所有约束条件：

1. 生成树天然保证所有节点连通、任意两点间仅有唯一路径（满足条件1、2）
2. 最大生成树在所有生成树中边权总和最大；同时生成树的边数固定为节点数-1，所有符合要求的解边数一致，自动满足“总权重相同时选边数更少”的约束

具体实现策略 #

可以用两种经典算法实现，只需将常规最小生成树的权重排序逻辑反转：

1. Kruskal算法（按边权降序处理） #

• 操作步骤：
  • 把所有边按权重从大到小排序
  • 用并查集（Union-Find）结构跟踪节点的连通状态
  • 依次遍历排序后的边：如果边的两个节点不在同一连通分量，就保留这条边；否则跳过（保留会形成环）
  • 直到选够节点数-1条边，停止遍历

2. Prim算法（按边权降序扩展） #

• 操作步骤：
  • 任选一个起始节点，标记为已访问
  • 每次从“已访问节点”到“未访问节点”的边中，选权重最大的那条，把对应未访问节点加入已访问集合，同时保留这条边
  • 重复直到所有节点都被访问

针对示例的验证 #

你的示例图有9个节点，需要保留8条边：
按Kruskal算法排序边后，前8条权重最高且不形成环的边正好是示例中保留的绿色边，剩下的权重60和10的边因会形成环被剪枝，完全符合要求。

代码实现（基于你的代码修改） #

用igraph内置的最大生成树函数可以快速实现：

import pandas as pd
import igraph as ig
import matplotlib.pyplot as plt

fig, ax = plt.subplots()

df = pd.DataFrame(
    [
        [0, 1, 100],
        [0, 2, 110],
        [2, 3, 70],
        [3, 4, 100],
        [5, 3, 90],
        [1, 6, 85],
        [6, 7, 90],
        [7, 8, 100],
        [5, 6, 10],
        [4, 5, 60],
    ],
    columns=["nodeA", "nodeB", "weigth"],
)

g = ig.Graph.DataFrame(df, directed=False)
# 生成最大生成树，指定权重列和最大化模式
mst = g.spanning_tree(weights=g.es["weigth"], mode='max')

# 标记原图中保留/剪枝的边
edge_colors = []
for edge in g.es:
    edge_colors.append("green" if mst.are_connected(edge.source, edge.target) else "red")

ig.plot(
    g,
    target=ax,
    edge_label=g.es["weigth"],
    edge_color=edge_colors,
)
fig.show()

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