边数m≤n+157的图的O(n)时间MST算法求解及思路问询

问题背景 #

给定带权无向连通图 ( G=(V,E) )，所有边权互不相同（因此MST是唯一的），已知图的边数 ( m \leq n+157 )。我们需要设计一种**线性时间（( O(n) )）**的MST算法，比传统的Kruskal（( O(m \log m) )）和Prim（( O(m + n \log n) )）算法更高效。

核心解决思路 #

这个问题的突破口在于图的稀疏性：生成树本身需要 ( n-1 ) 条边，而题目里的边数仅比生成树多157条左右，也就是说冗余边的数量是常数级的。结合MST的经典性质——边权互异时，任何环中的最大边一定不属于MST——我们可以通过“先建初始生成树，再用冗余边迭代替换非最优边”的方式，实现线性时间复杂度。

实现步骤详解 #

1. 快速构建初始生成树

   • 用DFS或者BFS遍历整个图，生成一棵任意的生成树 ( T_0 )。这个过程的时间复杂度是 ( O(n+m) )，但因为 ( m \leq n+157 )，所以等价于 ( O(n) )。
   • 此时，我们得到了 ( n-1 ) 条树边，剩下的 ( m-(n-1) \leq 158 ) 条边就是非树边（也就是冗余边）。

2. 用非树边优化生成树

   • 对每一条非树边 ( e=(u, v, w_e) )，执行以下操作：
     • 在当前的生成树里，找到 ( u ) 到 ( v ) 的唯一路径 ( P )。
     • 找出路径 ( P ) 中权值最大的边 ( e_{\text{max}} )，记它的权值为 ( w_{\text{max}} )。
     • 因为所有边权都不一样，所以如果 ( w_e < w_{\text{max}} )，说明 ( e_{\text{max}} ) 是当前生成树里的“坏边”——它不在MST里，我们把它从生成树中移除，加入边 ( e )；如果 ( w_e > w_{\text{max}} )，那这条非树边本身就不属于MST，直接丢弃即可。
   • 这里要注意：非树边的数量最多只有158条，哪怕每次找路径和最大边的操作是 ( O(n) )，总时间也只是 ( O(158n) )，属于线性时间（常数系数不影响渐进复杂度）。

3. 得到最终的MST

   • 等所有非树边都处理完，剩下的生成树就是图 ( G ) 的唯一最小生成树了。

伪代码示例 #

function findMST(G):
    # 步骤1：构建初始生成树（DFS/BFS实现）
    T = build_spanning_tree(G)
    non_tree_edges = [e for e in G.edges if e not in T.edges]
    
    # 步骤2：迭代优化生成树
    for e in non_tree_edges:
        u, v, w_e = e.u, e.v, e.weight
        # 在生成树T中找到u到v的路径及路径上的最大边
        path, max_edge = find_path_and_max_edge(T, u, v)
        if w_e < max_edge.weight:
            T.remove_edge(max_edge)
            T.add_edge(e)
    
    # 步骤3：返回最终MST
    return T

复杂度分析 #

• 初始生成树构建：( O(n+m) = O(n) )，因为 ( m ) 只比 ( n ) 多常数个。
• 非树边处理：每条非树边的处理是 ( O(n) )，总共 ( O(158n) = O(n) )。
• 总时间复杂度：( O(n) )，完全满足题目的要求，而且比Kruskal和Prim算法的复杂度更低。

额外思路提示 #

• MST性质是核心：一定要记住“边权互异时，环内最大边不在MST中”这条性质，这是我们敢替换边的根本原因。
• 不用纠结初始生成树的优劣：哪怕初始生成树很“差”，只要通过常数次的替换操作，就能得到最优的MST，因为冗余边数量很少。
• 路径最大边的查找可以优化：如果觉得多次DFS/BFS找路径太麻烦，可以预处理生成树的父节点数组和每个节点到父节点的边权，然后用单次DFS记录每个节点到根的路径最大边，再通过LCA（最近公共祖先）快速计算任意两点路径的最大边。不过对于只有158条非树边的情况，直接用DFS找路径的实现更简单，而且复杂度还是线性的。

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