[그래프] 최소 신장 트리 (프림/크루스칼/유니온 파인)

• 연결 그래프
  • 간선의 방향이 없는 그래프에서 모든 정점들 간에 간선을 따라 서로 다다를 수 있는 그래프
• 그래프 이론에서 '트리'란 "싸이클이 없는 연결된 그래프"로 정의됨
• 트리
  • 최소한의 간선을 사용하면서 연결된 그래프
• 신장 트리 비용
  • 그래프의 간선에 가중치가 있다면, 신장 트리를 구성하는 간선의 가중치를 다 더한 것
• 최소 신장 트리
  • 가중치가 있는 무향 그래프로부터 만들 수  있는 모든 신장 트리 중, 비용이 가장 낮은 트리
• 프림 알고리즘
  • 하나의 정점 집합을 점점 키워나가는 방식
• 크루스칼 알고리즘
  • 여러 정점 집합으로 시작해서 집합들을 합쳐나가는 방식

 

 

프림 알고리즘

• 최소 신장 트리를 찾는다는 것은 궁극적으로 |V|-1개의 간선을 찾는 과정
• 프림 알고리즘은 아무 간선도 없는 상태에서 간선을 하나씩 더하는 작업을 |V|-1번 한다
• 정점 집합 S를 운용함
  • 처음에는 시작정점 r 하나로 시작해서 한 번에 정점을 하나씩 더해감
  • 정점을 하나 더할 때 대응되는 간선이 하나씩 더해짐
  • 정점 |V|-1개를 더하면 모든 정점이 집합 S에 들어오기됨
• |V|-1개의 간선이 최소 신장 트리를 이룸
• 인접한 정점 중 현재까지의 계산 결과 정점 v를 신장트리에 연결시킬 떄 가장 최소 비용의 드는 정점 u를 저장함
• 이완
  • 집합 S로 들어간 정점에 의해서 최소 연결 비용에 변동이 생기는 것. 값이 바뀌는 것

 

 

크루스칼 알고리즘

• 여러 정점 집합으로 시작해서 집합들을 합쳐나가는 방식으로 작동
• 크루스칼 알고리즘은 여러 정점 집합들을 운영함
  • 각 정접 집합은 싸이클이 없는 연결된 그래프로 하나의 트리에 해당함
  • 트리를 합쳐서 하나의 트리를 만들려면, 양 끝점이 두 집합에 걸쳐 있는 간선이 필요함
  • 처음에  n개의 트리로 시작하여서, 두 트리를 하나로 합치는 과정을 n-1번 수행하면 하나의 트리가 됨
• 간선을 더하는 규칙
  • 중간의 한 시점을 귀납적으로 보면, 그 시점에 구축된 서로 다른 집합을 연결하는 모든 간선 중 최소 비용 간선을 선택함
  • 한 번에 최소 비용 간선을 하나씩 더하는데, 기존에 확정해놓은 간선 집합과 싸이클을 만들지 않는 범위에서 더함
• 크루스칼 알고리즘은 먼저 모든 간선을 비용이 작은 순서로 정렬함
  • 정점들을 n개의 집합으로 초기화함
  • 비용이 가장 작은 간선부터 차례로 한 번씩 살핌
  • 해당 간선이 두 정점 집합을 하나로 합칠 수 있으면 간선은 선택되어 최소 신장 트리의 일부로 확정됨. 그렇지 않으면 그 간선은 버림
  • 이런 식으로 n-1번의 성공정 집합 합치기가 이루어질 때까지 진행

 

프림 알고리즘과 크루스칼 알고리즘

• 두 알고지름은 사실 한 가지 원리를 바탕으로 함
• n-1개의 간선을 더해가는 순서를 나름대로 정해줌
• 이렇게 더해나가는 간선이 궁극적으로 최소 신장 트리에 이르는 길을 놓치지 않아, 해당 간선을 일단 최소 신장 트리에 포함시키는 것이 안전하다는 것을 의미

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」

 

(+)

유니온 파인드(Union-Find) 알고리즘

• 주로 두 요소가 같은 집합에 속하는지 빠르게 판단하고, 두 집합을 합치는 데 사용됨
• 이 알고리즘은 주로 그래프에서 연결된 구성 요소를 찾거나, 사이클이 있는지 검사할 때 사용함
• Find : 어떤 요소가 속한 집합의 대표(루트)를 찾기
• Union : 두 집합을 하나의 집합으로 합치기
• [구현 방법]
  • 초기화
    • 각 요소의 부모를 자기 자신으로 설정. 이 때, 각 요소는 자신만을 포함하는 집합의 대표(루트)
  • Find 연산
    • 특정 요소의 루트를 찾기 위해, 부모 요소를 따라가면서 루트를 찾기
    • 경로 압축(Path Compression)을 사용하여, Find 연산 도중 만나는 모든 요소의 부모를 루트로 직접 연결(다음 번 Find 연산이 더 빨라짐)
  • Union 연산
    • 두 요소의 루트를 찾기
    • 두 루트가 다르면, 한 루트를 다른 루트의 자식으로 만들기(두 집합을 하나로 합쳐짐)

//예시 코드
class UnionFind {
    private int[] parent;

    public UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]); // 경로 압축
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}