[알고리즘] 그래프(3) - 최소신장트리 MST (1)

 목차 

1. 최소 신장 트리의 정의

2. Kruskal 알고리즘의 개념

3. Kruskal 알고리즘 구현

 

 정의 

최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다.

 

신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다.

 

어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다.

 

최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가 있을 때 간선의 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 합니다.

 

최소 신장 트리를 만드는 가장 보편적인 알고리즘은 Kruskal 알고리즘과 Prim 알고리즘이 있습니다. 이 번 포스팅에서는 먼저 두가지 알고리즘 중 Kruskal 알고리즘에 대해서 다루어보도록 하겠습니다.

 

 개념 

Kruskal 알고리즘의 동작 방식에 대해 알아보도록 하겠습니다.

1. 간선들의 가중치를 오름차순으로 정렬합니다.
2. 간선들을 탐색하면서 양쪽 정점을 포함한 컴포넌트가 연결되어있지 않으면 간선을 선택하여 연결합니다.
3. 간선의 개수가 V-1개 선택되면, 선택된 간선들과 정점들이 이루는 연결요소가 최소 신장 트리가 됩니다.

다음과 같은 가중치가 존재하는 무방향 그래프가 있습니다. Kruskal 알고리즘을 이용하여 최소 신장 트리를 만들어 보겠습니다.

먼저 가중치들을 정렬합니다.

cost	1	1	2	3	4	5	7	8	8	9
u	3	2	6	1	3	4	1	2	5	4
v	4	5	7	2	6	5	3	4	7	7

간선의 개수가 V-1개가 될 때까지 가중치가 적은 간선들 부터 선택해 나아가기 시작합니다. 이 때 새로운 간선의 두 정점이 연결요소에 포함되어 있으면 연결을 수행하지 않습니다.

 

처음 정점 3과 4를 연결하는 가중치 1인 간선을 선택하여 연결합니다.

 

그 다음 간선의 가중치가 최소가 되는 정점 2와 5를 연결합니다.

 

다음과 같은 순서를 계속 반복하다보면 위와 같은 최소 신장 트리가 만들어지게 됩니다.

 

Kruskal 알고리즘은 가장 작은 가중치를 갖는 간선부터 탐색해 나아간다는 점에서 일종의 그리디 알고리즘으로 볼 수 있습니다. 다음은 Kruskal 알고리즘의 시간복잡도에 대해서 알아보도록 하겠습니다.

 

우선 간선을 가중치 별로 정렬하는 데에는 E개의 간선을 정렬할 때 알고리즘의 시간복잡도인 O(ElogE) 정도의 시간복잡도가 소요될 것입니다.

 

그렇다면 간선의 개수만큼 탐색을 수행하면서 선택 된 간선과 양 끝 정점을 포함한 컴포넌트가 연결요소인지 아닌지 판단하기 위해서는 얼마만큼의 시간복잡도가 필요할까요?

 

이전 포스팅에서 작성한 Disjoint Set을 만들기 위한 Union-Find 알고리즘이 여기에서 사용되는데 Union-Find 알고리즘에 대해서는 이전 포스팅을 참고해주시고 Union-Find 알고리즘을 알고있다는 전제하에 설명을 이어나가도록 하겠습니다.

 

간선들을 탐색하면서 두 간선의 Find 결과를 비교한 다음 다르다면 두 집합을 Union 연산을 통해 연결합니다. Union-Find 알고리즘의 시간복잡도는 O(log *V)로 간선의 개수를 곱한 O(Elog *V)가 탐색을 수행하는데 필요한 시간복잡도 입니다.

 

최종적으로 Kruskal 알고리즘의 시간복잡도는 O(ElogE) + O(Elog *V) 가 되는데 이는 O(ElogE)라고 볼 수 있습니다.

 

 구현 

코드를 통해 Kruskal 알고리즘을 구현해 보도록 하겠습니다. Kruskal 알고리즘을 어떻게 응용하고 문제를 해결하는지에 따라 많은 구현방법이 있겠지만 가장 기본적인 형태를 구현해보도록 하겠습니다.

// Union-Find : Find 연산을 수행합니다.
static int find(int v) {
    if(group[v] < 0) return v;
    return group[v] = find(group[v]);
}

// Union-Find : Union 연산을 수행합니다.
static boolean union(int u, int v) {
    u = find(u); v = find(v);
    if(u == v) return false;
    group[v] = u;
    return true;
}

// 간선 정보를 저장할 클래스를 생성합니다. 이 때 우선순위 큐를 사용하기 위해서
// Comparable을 상속받아 CompareTo()를 재정의합니다.
static class Edge implements Comparable<Edge>{
    int u, v, cost;
    Edge(int u, int v, int cost){
        this.u = u;
        this.v = v;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge e) {
        // TODO Auto-generated method stub
        return this.cost - e.cost;
    }
}

...

public static void main(String[] args) {

    ... 

    int cost = 0;
    int edge = 0;
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    // 모든 간선을 탐색하면서 연결합니다,
    while(!pq.isEmpty()){
        // 간선의 개수가 v - 1개 일경우 최소 신장 트리가
        // 완성 되었으므로 탐색을 종료합니다.
        if(edge == v - 1)
            break;
        Edge e = pq.poll();
        // 간선을 구성하는 두 정점이 연결요소가 아니라면 
        // 연결요소로 만들고 총 가중치의 합과 간선 개수를 증가시킵니다.
        if(union(e.u, e.v)){
            cost += e.cost;
            edge += 1;
        }
    }
}

위의 코드에서는 Union-Find 알고리즘의 초기화 및 그래프의 정점과 간선, 가중치를 초기화하는 코드를 생략하였습니다.

간선의 정보를 따로 관리하기 위해 Edge라는 객체를 만들었습니다.

 

List 나 배열에 담아 Arrays.sort() 또는 Collections.sort() 를 이용해서 정렬을 해도 되지만, 우선순위 큐를 사용하기 위해 Comparable 클래스를 상속받아 CompareTo() 메소드를 재정의 하였습니다.

 

간선의 개수 만큼 Kruskal 알고리즘을 수행하며 연결 요소를 만들어 나아가고 간선의 개수가 연결요소의 간선의 개수가 V - 1개가 되면 최소 신장 트리가 만들어진 것이므로 실행을 종료합니다.

 

다음 포스팅에서는 최소 신장 트리를 만드는 또 다른 알고리즘인 Prim 알고리즘에 대해 포스팅 해보도록 하겠습니다.