최소 신장 트리를 위한 프림, 크루스칼 알고리즘

 

정점과 가중치가 존재하는 간선이 주어진 상태에서

우리는 모든 정점을 가장 적은 비용으로 연결한 그래프를 최소 신장 트리라고 말한다.

 MST(Minimum Spanning Tree) 라고 말하며 이러한 문제에서 사용되는 알고리즘이 바로

 

프림과 크루스칼 알고리즘이다. 

같은 목적을 지니고 있지만 접근방식이 조금 다른데 유념해서 알아보자

 

프림 알고리즘

한 정점에서 시작해서 연결된 간선들 중 가장 가중치가 낮은 간선을 선택하며 트리를 확장하는 방식이다.시작점에서 점진적으로 최소 스패닝 트리를 완성해 나가는 그리디한 방식인데 순서는 다음과 같다.

 

 

• 초기화:
  • 임의의 정점을 선택해 시작한다.
  • 선택한 정점을 기준으로 연결된 간선 중 가중치가 가장 작은 간선을 선택한다.
• 트리 확장:
  • 선택된 간선에 연결된 정점을 트리에 추가한다.
  • 이제 트리에 포함된 정점들로부터 다시 가장 작은 가중치를 가진 간선을 선택해 트리를 확장한다.
  • 이 과정을 모든 정점이 트리에 포함될 때까지 반복한다.
• 시간 복잡도: 시간 복잡도는 일반적으로 O(E log E) 이다. 여기서 E는 간선의 수, V는 정점의 수이다.

 

우선순위큐를 통해 가중치가 낮은 간선을 선택하며 확장하는것이 특징.

 

 

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 간선의 가중치를 기준으로 간선들을 정렬한 뒤, 가장 작은 간선부터 하나씩 선택해 트리를 형성하는 방식이다. 이 과정에서 사이클이 발생하지 않도록 Union-Find 자료구조를 사용해 간선을 추가한다.

• 간선 정렬:
  • 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.

• 간선 선택:
  • 가장 가중치가 작은 간선부터 시작해, 해당 간선이 사이클인지 판단하고, 트리에 추가한다.
  • Union-Find 자료구조를 사용해 두 정점이 이미 같은 집합에 속해 있는지 확인한다.
  • 이 과정을 트리가 완성될 때까지 반복한다.
• 시간 복잡도:
  • 크루스칼 알고리즘의 시간 복잡도는 간선 정렬에 드는 시간이 대부분을 차지하며, O(E log E) 이 된다

 

유니온 파인드?

 

그래프에서 서로소 집합을 관리하는 알고리즘이다.

서로 다른 집합인지, 원소가 어떤 집합에 속해있는지에 대한 연산을 처리하기 위함이다.

크루스칼 알고리즘에서는 사이클이 존재하는지 판단하기 위해서 사용된다.

 

• Union
  • 두 집합을 하나로 합칠때 사용하는 연산
  • Rank나 Size 기반으로 합쳐 트리의 높이를 최소화 해야한다.

• Find
  • 주어진 원소의 집합을 찾는 연산
  • 집합의 루트를 반환, 경로 압축을 통해 트리의 높이를 줄일 수 있다.

 

class UnionFind {
    private int[] parent;
    private int[] rank;
 
    // 초기화: 각 원소는 자기 자신을 가리키며, 랭크는 1로 설정한다.
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
 
    // Find 연산: 경로 압축을 적용해 트리의 높이를 줄인다.
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 재귀적으로 부모를 따라 올라가 루트를 찾음
        }
        return parent[x];
    }
 
    // Union 연산: 랭크를 기준으로 두 집합을 합친다.
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
 
        if (rootX == rootY) {
            return false; // 이미 같은 집합에 속해 있는 경우
        }
 
        // 랭크가 더 큰 집합 아래에 작은 집합을 붙인다.
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}
 

 

배열의 인덱스를 통해 관리하고, 트리로 변환하는 과정에서 높이를 낮춰 효율을 올릴 수 있다.

 

 

결론 

 

프림의 경우 정점을 기준으로 확장하고

크루스칼의 경우 모든 간선을 가중치 기준으로 정렬 후 선택을 시작한다.

 

프림은 간선이 많은 밀집 그래프에서 효율적이고,

크루스칼은 간선이 적은 희소 그래프에서 정렬과 유니온 파인드에서 특성이 두드러진다.