时间戳

首页 > 解决方案 > 断边联合查找算法

algorithm - 断边联合查找算法

问题描述

我需要一些帮助来解决联合查找问题。
这是问题。

有一个无向连通图，n 个节点标记为 1..n。但是一些边已经断开，断开了图形。找到修复边缘的最小成本，以便所有节点再次可以相互访问。

输入：

n，一个int，表示节点的总数。
边，整数对列表，表示由边连接的节点。
edgeToRepair，一个列表，其中每个元素是一个三元组，表示当前断开一条边的节点对和重复该边的成本
（例如 [1, 2, 12] 表示重复节点 1 和 2 之间的一条边，成本为 12)。

示例 1：
输入：n = 5，edges = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]],
edgesToRepair = [[1, 2 , 12], [3, 4, 30], [1, 5, 8]]

输出：20
由于断边有 3 个连通分量：[1]、[2, 3] 和 [4, 5]。我们可以通过重复节点 1 和 2 以及节点 1 和 5 之间的边以最小成本 12 + 8 = 20 将这些组件连接成单个组件。

public int minCostRepairEdges(int N, int[][] edges, int[][] edgesToRepair){

    int[] unionFind = new int[N+1];
    int totalEdges=0;
    for(int[] edge : edges){
        int ua = edge[0]; //node1
        int ub = edge[1]; //node2
        unionFind[ua] = ub;
        totalEdges++;
    }

    //change unionFind for some broken edge 
    for(int[] broken : edgesToRepair){
        int ua = Find(unionFind, broken[0]);
        int ub = Find(unionFind, broken[1]);
        if(ua == ub){
            unionFind[ua] = 0;
        }
    }

    Arrays.sort(edgesToRepair, (a,b)->(a[2]-b[2]));

    int cost=0;
    for(int[] i : edgesToRepair){
        int ua = Find(unionFind, i[0]);
        int ub = Find(unionFind, i[1]);

        if(ua != ub){
            unionFind[ua] = ub;
            cost += i[2];
            totalEdges++;
        }
    }
    return edgesToRepair==N-1 ? cost : -1;
}

public int find(int[] uf, int find){
    if(uf[find]==0) return find;
    uf[find] = find(uf, uf[find]);
    return uf[find];
}

以上是我到目前为止的代码。

我的想法是
首先将所有边（给定边 [] []）添加到 UnionFind，然后根据给定的边修复信息更新它。（如果边缘被破坏，那么将在 union -find 中更新它）
然后尝试执行基本的 union-find 算法以最小的成本连接两个节点。

这里有什么错误的方法吗？
首先，当它被破坏时，我无法更新 unionFind。
我不知道如何处理两个节点之间的完整边缘。

任何意见将是有益的。

标签： algorithmunion-find

解决方案

您应该使用 Kruskal 算法来找到由现有边和损坏（修复）边组成的最小成本生成树：

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

只需考虑现有边的成本为 0，而损坏的边有修复成本。

推荐阅读