크루스칼 알고리즘 : Kruskal's Algorithm

크루스칼 알고리즘 : Kruskal's Algorithm

최소 비용 신장 부분 트리(MST)를 찾는 알고리즘

Spanning Tree : 신장 트리

트리의 특수한 형태로 모든 정점들이 연결되어 있고 사이클을 포함하지 않는 트리
( * 한 노드에서 다른 노드에 이르는 경로가 오직 하나 뿐인 트리 )

MST(Minimum Spanning Tree) : 최소 신장 트리

Spanning Tree 내 모든 간선의 가중치의 합이 최소인 트리

시간 복잡도

O(ElogV)
* 변의 개수 : E, 꼭짓점의 개수 : V

과정

1. 정점별로 parent를 자기 자신으로 초기화 해준다.

2. 입력으로 주어진 간선들을 가중치를 기준으로 오름차순 정렬해준다.

3. 간선을 순서대로 순회하면서 양 끝 정점의 parent를 확인하고(find) 다른 경우 가중치를 더하고 union 해준다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
 
public class Kruskal {
 
    // 정점의 개수
    public static int V = 9;
    // union-find를 위한 parent 배열
    public static int[] parent;
    
    public static void init() {
        for(int i=0; i<parent.length; i++) parent[i] = i; 
    }
    
    public static int find(int a) {
        if(a==parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
    
    public static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        parent[pb] = pa;
    }
    
    public static int kruskal(List<int[]> adj) {
        int scc = 0;
        parent = new int[V];
        init();
        // 간선을 가중치가 작은 순서대로 정렬한다.
        Collections.sort(adj, new Comparator<int[]>() {
            @Override
            public int compare(int[] arg0, int[] arg1) {
                return Integer.compare(arg0[2], arg1[2]);
            }
        });
        for(int i=0; i<adj.size(); i++) {
            int[] edge = adj.get(i);
            // 간선의 양 끝 정점의 parent를 확인한다
            if(find(edge[0])!=find(edge[1])) {
                union(edge[0], edge[1]);
                scc+=edge[2];
                System.out.println(edge[0]+" - "+edge[1]+" : "+edge[2]);
            }
        }
        return scc;
    }
    
    public static void main(String[] args) {
        List<int[]> adj = new ArrayList<int[]>();
        int[][] graph = new int[][] {
            { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
            { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
            { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
            { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
            { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
            { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
            { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
            { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
            { 0, 0, 2, 0, 0, 0, 6, 7, 0 }            
        };
        for(int i=0; i<graph.length; i++) {
            for(int j=i+1; j<graph[i].length; j++) {
                if(graph[i][j]!=0) adj.add(new int[] {i, j, graph[i][j]});
            }
        }
        System.out.println(kruskal(adj));
    }
}