MST(최소 신장 트리)를 찾는 두가지 방법: Prim, Kruskal

MST

방향이 없는 그래프에서 모든 정점을 연결하며 모든 간선의 합이 최소인 트리

Prim

다익스트라 알고리즘과 아주 유사함

출발 정점을 시작으로 이웃 정점들의 최소 간선을 갱신하면서 답을 찾아감

*시간복잡도: O(V^2 + E)

Java code

public class Prim {
    int vertexNum;
    HashMap<Integer, Integer>[] graph;
    
    int prim(){
        int[] minWeight = new int[vertexNum];
        int[] parent = new int[vertexNum];
 
        HashSet<Integer> Q = new HashSet<>();
        Q.add(0);
        minWeight[0] = 0;
        parent[0] = 0;
        for(int i=1; i<vertexNum; i++){
            Q.add(i);
            minWeight[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }
        
        int sumOfEdge = 0;
        while(!Q.isEmpty()){
            Iterator<Integer> itr = Q.iterator();
            int minVertex = 0;
            int min = Integer.MAX_VALUE;
            //아직 가지 않은 vertex 중 최소 찾기
            while(itr.hasNext()){
                int v = itr.next();
                if(minWeight[v] < min){
                    minVertex = v;
                    min = minWeight[v];
                }
            }
            Q.remove(minVertex);            
            sumOfEdge += min;
            
            for(int i : graph[minVertex].keySet()){
                if(Q.contains(i) && minWeight[i] > graph[minVertex].get(i)){
                    minWeight[i] = graph[minVertex].get(i);
                    parent[i] = minVertex;
                }
            }
        }
        return sumOfEdge;
    }
}

Kruskal

모든 간선을 오름차순으로 정렬한 후 각 정점이 사이클을 이루지 않게 간선들을 선택함

사이클 여부를 확인하기 위해 Disjoint Set을 사용함

*시간복잡도: O(E*logE)

Java code

public class Kruskal {
    UnionFind set;
    int vertexNum;
    HashMap<Integer, Integer>[] graph;
 
    static class Edge implements Comparable<Edge>{
        int va;
        int vb;
        int weight;
        
        Edge(int a, int b, int w){
            va = a;
            vb = b;
            weight = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }
    
    int kruskal(){
        //그래프의 모든 간선 리스트 만들기
        ArrayList<Edge> edges = new ArrayList<>();
        for(int here=0; here<vertexNum; here++){
            for(int there : graph[here].keySet()){
                edges.add(new Edge(here, there, graph[here].get(there)));
            }
        }
        Collections.sort(edges); //간선 리스트 오름차순 정렬
        set = new UnionFind(vertexNum);
        int sumOfEdge = 0;
        for(int i=0; i<edges.size(); i++){
            int a = edges.get(i).va;
            int b = edges.get(i).vb;
            int weight = edges.get(i).weight;
            if(set.find(a) == set.find(b)) continue; //이미 같은 집합이면 무시
            set.union(a, b);
            sumOfEdge += weight;
        }
        return sumOfEdge;
    }
}