크루스칼 알고리즘

0. 최소 신장 트리

신장트리

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이크이 존재하지 않는 부분 그래프(트리)

최소신장트리 알고리즘

신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘

 

적용 예시
1. 도시간 최소 거리 구하기
2. 서버간 최서 거리 구하기

1. 서로소 집합

서로소 집합

공통원소가 없는 두 집합

서로소 집합 자료구조

• 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
• 트리 자료구조를 이용하여 집합 표현

주요 연산

1. Union(합집합) : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산

• 두 노드 A, B확인
  • A의 루트노드 root(A), B 루트노드 root(B)를 찾음
  • root(A)를 root(B)의 부모 노드로 설정(root(A)가 root(B)를 가리킴)

static void unionParent(int a, int b){
        a=findParent(a);
        b=findParent(b);
        if(a<b) parent[b]=a;
        else parent[a]=b;
    }

2. Find(찾기) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산

• A의 루트노드 root(A)를 찾는 연산

 static int findParent(int x){
        if(x==parent[x])return x;
        return parent[x]=findParent(parent[x]);
    }

위 코드는 외우면 좋음

2. 크루스칼 알고리즘

• 그리디 알고리즘으로 분류 됨
• 양방향 간선일 경우 사용
• (약속) 번호가 큰 노드가 작은 노드를 부모노드로 가리킴

원리

1. 간선 테이블을 오름차순으로 정렬
2. 간선을 하나씩 차례대로 확인하면서 간선이 사이클을 발생시키는지 확인
   
   • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
   • 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않고 무시
3. 모든 간선에 대해서 (2) 반복

간선	D-E	B-C	A-C	D-F	C-D	C-E	B-D	E-F	A-B
가중치	2	2	3	3	3	4	5	5	6

 

대표코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main {
    static int v, e;
    static int[] parent=new int[10001];
    static int result=0;
    static ArrayList<Edge> edges = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v=sc.nextInt();
        e=sc.nextInt();

        for (int i = 1; i <= v; i++) {
            parent[i]=i;
        }

        for (int i = 0; i < e; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            edges.add(new Edge(c, a, b));
        }
        Collections.sort(edges);

        for (Edge edge : edges) {
            int cost = edge.distance;
            int a = edge.nodeA;
            int b = edge.nodeB;

            if (findParent(a) != findParent(b)) {
                unionParent(a, b);
                result += cost;
            }

        }
        System.out.println(result);
    }
    static int findParent(int x){
        if(x==parent[x])return x;
        return parent[x]=findParent(parent[x]);
    }
    static void unionParent(int a, int b){
        a=findParent(a);
        b=findParent(b);
        if(a<b) parent[b]=a;
        else parent[a]=b;
    }


    static class Edge implements Comparable<Edge>{
        int distance;
        int nodeA;
        int nodeB;

        public Edge(int distance, int nodeA, int nodeB) {
            this.distance = distance;
            this.nodeA = nodeA;
            this.nodeB = nodeB;
        }

        @Override
        public int compareTo(Edge o) {
            return this.distance-o.distance;
        }
    }
}

 

문제

• https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

• https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리