Edmond最大分支算法Python实现方案咨询

问题背景 #

我正在尝试实现Edmond最大分支算法的Python版本，该算法用于解决有向图的最大权重分支问题。

最大分支问题定义 #

给定有向图G=(V,E, w)，其中w为权重函数，对于V中的根节点r，要求找到以r为根的分支G'=(V,E')，满足：

• G'无环
• 所有节点入度不超过1
• 总权重最大

实现方案 #

方案1：调用成熟第三方库实现 #

最便捷的方式是直接使用networkx库的内置实现，networkx已经封装了经过工业界验证的Edmond最大分支算法，调用示例如下：

import networkx as nx

# 构造有向图
G = nx.DiGraph()
# 添加边，格式为(起点, 终点, 权重)
G.add_weighted_edges_from([
    (0, 1, 5),
    (0, 2, 3),
    (1, 2, 4),
    (2, 3, 2),
    (1, 3, 6)
])

# 计算以0为根的最大分支，算法参数adjustment为负表示求最大权重
max_branching = nx.maximum_branching(G, root=0)
# 输出总权重
print("最大分支总权重：", sum(d["weight"] for u, v, d in max_branching.edges(data=True)))
# 输出分支包含的边
print("分支边列表：", list(max_branching.edges()))

方案2：原生Python实现 #

如果你需要自行实现算法逻辑，参考核心实现代码如下：

def edmonds_max_branching(graph, root):
    # graph格式：{节点: {邻居: 权重}}
    n = len(graph)
    # 第一步：为每个非根节点选入度最大的边
    max_in = {}
    for u in graph:
        if u == root:
            continue
        max_weight = -float('inf')
        max_v = None
        for v in graph:
            if u in graph[v] and graph[v][u] > max_weight:
                max_weight = graph[v][u]
                max_v = v
        if max_v is None:
            raise ValueError("存在节点无法到达")
        max_in[u] = (max_v, max_weight)
    
    # 第二步：检测是否有环
    visited = set()
    cycle = None
    for u in max_in:
        if u in visited:
            continue
        path = []
        current = u
        while current is not None and current not in visited:
            visited.add(current)
            path.append(current)
            current = max_in[current][0] if current in max_in else None
        if current is not None and current in path:
            idx = path.index(current)
            cycle = path[idx:]
            break
    
    # 无环直接返回结果
    if cycle is None:
        edges = [(max_in[u][0], u, max_in[u][1]) for u in max_in]
        total_weight = sum(e[2] for e in edges)
        return total_weight, edges
    
    # 有环则收缩环为单个超级节点
    cycle_set = set(cycle)
    super_node = max(graph.keys()) + 1 if all(isinstance(k, int) for k in graph) else "super_" + str(hash(tuple(cycle)))
    new_graph = {}
    # 映射收缩前的边到收缩后的边，后续展开用
    edge_map = {}
    
    # 处理环外节点到环的边，选每个节点到环的最大权重边
    for v in graph:
        if v in cycle_set:
            continue
        new_graph[v] = {}
        max_to_cycle = -float('inf')
        best_u = None
        for u in graph[v]:
            if u in cycle_set:
                weight = graph[v][u] - max_in[u][1]
                if weight > max_to_cycle:
                    max_to_cycle = weight
                    best_u = u
        if best_u is not None:
            new_graph[v][super_node] = max_to_cycle
            edge_map[(v, super_node)] = (v, best_u)
        
        # 处理环到环外节点的边，选环里每个节点到环外的最大权重边
        for u in graph[v]:
            if u not in cycle_set and u != root:
                if super_node not in new_graph:
                    new_graph[super_node] = {}
                if u not in new_graph[super_node] or graph[v][u] > new_graph[super_node][u]:
                    new_graph[super_node][u] = graph[v][u]
                    edge_map[(super_node, u)] = (v, u)
    
    # 处理环外节点之间的边
    for v in graph:
        if v in cycle_set:
            continue
        for u in graph[v]:
            if u not in cycle_set and u != root and (v in new_graph) and (u not in new_graph[v]):
                new_graph[v][u] = graph[v][u]
                edge_map[(v, u)] = (v, u)
    
    # 递归计算收缩后的图的最大分支
    new_total, new_edges = edmonds_max_branching(new_graph, root if root not in cycle_set else super_node)
    
    # 展开超级节点，还原边
    total_weight = new_total + sum(max_in[u][1] for u in cycle)
    edges = []
    break_edge = None
    for e in new_edges:
        original_e = edge_map.get((e[0], e[1]), (e[0], e[1]))
        if original_e[1] in cycle_set:
            break_edge = original_e[1]
        edges.append(original_e)
    
    # 把环里除了break_edge对应的入边之外的其他边加回去
    for u in cycle:
        if u != break_edge:
            edges.append((max_in[u][0], u, max_in[u][1]))
    
    return total_weight, edges

# 调用示例
graph = {
    0: {1:5, 2:3},
    1: {2:4, 3:6},
    2: {3:2},
    3: {}
}
total, edges = edmonds_max_branching(graph, 0)
print("总权重：", total)
print("边列表：", edges)

补充说明 #

如果你已经参考相关方案完成了自己的实现，可以通过上述示例的测试用例验证实现的正确性，对比输出结果即可排查逻辑问题。

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