Kruskalアルゴリズム&連合検索アルゴリズム

Union-Find algorithm

各ノードの親ノードを配列に格納します。 最上位の親ノードに再帰的に移動し、それに基づいてセットを分割します。

インプリメンテーション

class UnionFind {

    public boolean hasSameParent(int[] parentNodes, int a, int b) {
        return findParent(parentNodes, a) == findParent(parentNodes, b);
    }

    public void union(int[] parentNodes, int a, int b) {
        int parentA = findParent(parentNodes, a);
        int parentB = findParent(parentNodes, b);
        if (parentA > parentB) parentNodes[parentA] = parentB;
        else parentNodes[parentB] = parentA;
    }
    
    private int findParent(int[] parentNodes, int node) {
        if (parentNodes[node] == node) return node;
        return findParent(parentNodes, parentNodes[node]);
    }
}

Kruskal algorithm

edgeをコストの昇順に並べ替えます。 ソートedge順にループを形成しないedgeを選択し、MSTに追加します。 すべてのノードが親ノードとして同じノードを持つ場合、MSTは完了し、アルゴリズムは終了する。

インプリメンテーション

public int kruskal(int n, int[][] costs) {
    Arrays.sort(costs, (Comparator.comparingInt(o -> o[COST])));
    int[] parentNodes = createCycleTable(n);
    int answer = 0;
    for (int[] edge : costs) {
        if (!hasSameParent(parentNodes, edge[0], edge[1])) {
            union(parentNodes, edge[0], edge[1]);
            answer += edge[COST];
        }
        if (pathCreated(parentNodes)) break;
    }
    return answer;
}