[알고리즘] 최소 신장 트리

1. 개념

그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리이다.

 

2. 특징

• 사이클은 없어야 한다. 사이클이 있으면 가중치의 합이 최소가 될 수 없기 때문이다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.
• 에지 리스트의 형태로 구현하는 것이 간단하다.

 

3. 종류

1) 크루스칼 

모든 에지를 가중치 기준으로 오름차순으로 정렬한 후, 가중치가 작은 간선부터 선택하면서 사이클을 형성하지 않도록 하여 최소 신장 트리를 만든다.

 

2) 프림

시작 노드부터 출발하여 가장 가까운 노드를 선택하며, 해당 노드와 연결된 에지 중 가장 가중치가 작은 간선을 선택하는 방식으로 최소 신장 트리를 만든다.

 

4. 크루스칼 

1) 원리

• 에지 리스트를 생성한다.
  • 에지 리스트는 가중치 기준으로 오름차순 정렬한다.
• 가중치가 낮은 에지부터 연결 시도
  • 유니온 파인트 배열을 생성한다.
    • 그래프에 사이클이 있는지 없는지를 확인하기 위해 사용한다.
    • 각 노드가 특정 집합에 속해있다고 하고, 에지로 두 노드가 연결된 경우에 두 노드는 같은 집합에 속하게 된다. 
  • 하나의 에지를 선택하면 해당 에지에 연결되어 있는 노드 2개도 선택된다. 이때, 각 노드에 find 연산을 해서 대표 노드를 구한다.
    • 만약 대표 노드가 다르다면 두 노드를 union한다. 이게 에지를 연결하는 행위.
    • 만약 대표 노드가 같다면 두 노드를 union하면 사이클이 생긴다. 그래서 union하지 않는다.
      • 예시 상황은 다음과 같다. 2-4를 연결해서 2와 4가 한 집합에 있고, 2-5를 연결해서 2와 5가 한 집합에 있게 되어, 2 4 5 는 모두 한 집합에 있다. 그런데, 4-5 에지를 선택해서 4와 5의 대표노드가 같다. 이때 4-5를 연결하면 사이클이 생긴다.
• 연결한 에지의 개수가 N-1개가 될 때까지 에지 연결 시도를 반복한다.
• 완성된 최소 신장 트리의 총 에지 비용을 출력한다.

 

2) 코드

public static void mst(){
    while(usedEdge < N-1){
        Edge edge = pq.poll();
        if(find(edge.s) != find(edge.e)){
            union(edge.s, edge.e);
            result += edge.v;
            usedEdge++;
        }
    }
}

public static void union(int a, int b){
    a = find(a);
    b = find(b);
    if(a!=b){
        parent[b] = a;
    }
}

public static int find(int a){
    if(parent[a] == a){
        return a;
    }else{
        return parent[a] = find(parent[a]);
    }
}

 

5. 관련 문제

백준 1197

GitHub - Lee-Min-Jung/coding_test_practice

백준17472

GitHub - Lee-Min-Jung/coding_test_practice