Minimum-Spanning Tree

問題の説明

各エッジにコストがある無方向図で、周期がなく、エッジのコスト合計が最小のツリーを求める問題.

図の例

primアルゴリズム

最初に、MSTの要素として任意の頂点を選択します.次に、エレメントの幹線で、最小コストのedgeを選択し、そのedgeおよび接続ノードをMSTのエレメントとして追加します.
MSTに接続されたノードでは、Cycleを作成しないで最小コストのedgeを探し、そのedgeと接続されたノードをMSTの要素として繰り返し追加します.




次のステップをスキップ

インプリメンテーション

Edge.java

package com.company;

public class Edge implements Comparable<Edge>{
    public int node1;
    public int node2;
    public int cost;

    public Edge(int node1, int node2, int cost) {
        this.node1 = node1;
        this.node2 = node2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        if(this.cost < o.cost) return -1;
        if(this.cost > o.cost) return 1;
        return 0;
    }
}

Main.java

package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Main {
    public static void prim(Edge[] edges, int startNode, int numOfNodes){
        HashSet<Integer> mstNodes = new HashSet<>();
        ArrayList<Edge> mstEdges = new ArrayList<>();
        PriorityQueue<Edge> candidateEdges = new PriorityQueue<>();
        boolean[] edgeUsed = new boolean[edges.length];
        Arrays.fill(edgeUsed, false);

        mstNodes.add(startNode);
        for(int i = 0;i< edges.length;i++){
            if(edges[i].node1 == startNode || edges[i].node2 == startNode){
                candidateEdges.add(edges[i]);
                edgeUsed[i] = true;
            }
        }

        while(mstNodes.size() != numOfNodes){
            Edge candidate = candidateEdges.poll();
            if(mstNodes.contains(candidate.node1) && mstNodes.contains(candidate.node2))
                continue;
            mstEdges.add(candidate);
            mstNodes.add(candidate.node1);
            mstNodes.add(candidate.node2);

            for(int i = 0;i<edges.length;i++){
                if(edgeUsed[i]) continue;
                if(edges[i].node1 == candidate.node1 || edges[i].node1 == candidate.node2
                        || edges[i].node2 == candidate.node1 || edges[i].node2 == candidate.node2){
                    candidateEdges.add(edges[i]);
                    edgeUsed[i] = true;
                }
            }
        }

        for(int i = 0;i<mstEdges.size();i++){
            System.out.println(mstEdges.get(i).node1 + ", " + mstEdges.get(i).node2 + " -> " + mstEdges.get(i).cost);
            // Edge들 출력
        }
    }

    public static void main(String[] args) {
        Edge[] edges = {
                new Edge(1, 2, 7),
                new Edge(1, 3, 3),
                new Edge(2, 4, 10),
                new Edge(3, 4, 1),
                new Edge(3, 5, 6),
                new Edge(3, 6, 4),
                new Edge(4, 5, 13),
                new Edge(5, 6, 10)
        };

        int numOfNodes = 6;
        int startNode = 1;

        prim(edges, startNode, numOfNodes);
    }
}

時間の複雑さ

while文はO(n)回実行され、while文は1回実行されるごとに内部のfor文の実行回数もO(n)*O(n)=O(n^2)となる.

Kruskalアルゴリズム

すべてのEdgeをコストの小さい順に昇順に並べます.各頂点に番号を付けます.次に、ループを作成しないedgeで最も短いedgeを選択してMSTに追加し、edgeの各ノードが属するグループを接続します.(Disjoint Setアルゴリズムのリンク関数を使用)

例

まず,最小長(3,4)をMSTに追加し,2つのノードを1つのグループに構成する.

次に最小長(1,3)をMSTに追加し、1を3が属するグループに接続する.

次に最小長さ(5,6)を接続し、ノード5と6をグループ化する.

このように,ループを作成しないedgeでは,最小コストのedgeをMSTに繰り返し追加する.
次のステップをスキップ

インプリメンテーション

Edge.java

primアルゴリズムのコードと同じです.

Main.java

package com.company;


import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
    public static int find(int[] par, int x){
        if(par[x] == x) return x;
        else return find(par, par[x]);
    }

    public static void link(int[] par, int x, int y){
        par[find(par, y)] = find(par, x);
    }

    public static void kruskal(Edge[] edges, int startNode, int numOfNodes){
        int[] par = new int[numOfNodes + 1];
        for(int i = 1;i<=numOfNodes;i++){
            par[i] = i;
        }

        PriorityQueue<Edge> candidateEdges = new PriorityQueue<>();
        ArrayList<Edge> mstEdges = new ArrayList<>();

        for(Edge e: edges){
            candidateEdges.add(e);
        }

        while(mstEdges.size() < numOfNodes - 1){
            Edge candidate = candidateEdges.poll();
            if(find(par, candidate.node1) != find(par, candidate.node2)){
                // 최고 조상이 같지 않으므로 연결되지 않은 것임
                // 이미 연결된 node들을 edge로 연결하면 cycle 만들어짐
                link(par, candidate.node1, candidate.node2);
                mstEdges.add(candidate);
            }
        }

        for(Edge e: mstEdges){
            System.out.println(e.node1 + ", " + e.node2 + " -> " + e.cost);
        }
    }

    public static void main(String[] args) {
        Edge[] edges = {
                new Edge(1, 2, 7),
                new Edge(1, 3, 3),
                new Edge(2, 4, 10),
                new Edge(3, 4, 1),
                new Edge(3, 5, 6),
                new Edge(3, 6, 10),
                new Edge(4, 5, 13),
                new Edge(5, 6, 4)
        };

        int numOfNodes = 6;
        int startNode = 1;

        kruskal(edges, startNode, numOfNodes);
    }
}

Reference

https://www.codeground.org/common/popCodegroundNote