[알고리즘] 최소 신장 트리(MST) - Kruskal, Prim, Sollin 알고리즘

최소 신장 트리(Minimum Spanning Tree, MST)이란?

 

최소 신장 트리를 배우기 앞서, 신장 트리란 무엇인지 알아야 한다. 이는 연결 그래프의 부분 그래프로, 모든 정점과 간선의 부분집합으로 구성된다. 신장 트리의 중요한 특징 중 하나는 모든 노드가 적어도 하나의 간선과 정점에 연결되어야 하며, 사이클을 만들면 안된다. 최소 신장 트리를 이해하기 위해서는 이러한 신정트리의 개념을 정확히 파악하고 있어야 한다.

 

아래와 같은 그래프가 신장 트리의 예시 중 하나이다.

신장 트리 예시

 

 

최소 신장 트리는 하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치의 합이 최소인 신장트리를 말한다.

 

이러한 최소 신장 트리 알고리즘은 대표적으로 Kruskal, Prim, Sollin 알고리즘이 있다. 이는 모두 그리디(Greedy)알고리즘이다. 그리디 알고리즘은 최적해(최솟값, 최댓값) 문제를 해결하기 위한 알고리즘 방식으로 알고리즘의 선택이 항상 "욕심내어" 최소 혹은 최댓값인 알고리즘이다.

 

다시말해, 최소 신장 트리 알고리즘은 현재의 선택이 최선의 선택이라고 생각하는 알고리즘이라는 것이다. 이제부터, 이 최소 신장 트리 알고리즘이 구체적으로 어떻게 동작하는 지 살펴보도록 하겠다.

 

 

 

 

Kruskal 알고리즘

 

Krusal 알고리즘의 핵심은 간선의 가중치를 기준으로 정렬한다는 것이다. 사실은 이게 전부인 간단한 알고리즘이다. 물론, 신장 트리의 정의 상 사이클을 만들면 안되기 때문에 이는 제외하며 이를 위해 Union - Find 알고리즘을 사용한다.

 

즉, 간선들을 선택하는데 "사이클을 만들지 않고, 항상 욕심내어 가중치가 작은 간선" 을 선택하고, 사이클의 형성 유무 판단을 위해 Union - Find를 사용한다고 정리할 수 있다.

 

그러면 어떻게 하면 Union - Find를 사용해 사이클이 만들어지는 지 확인할까? 이는 양 끝 정점이 같은 집합에 속했는 지에 따라 판단된다. 만약 다른 집합에 속해져 있다면 사이클을 돌고 있는 것이 아니지만, 같은 집합이라면 사이클을 돌고 있는 것이다.

 

 

 

 

 

 

Kruskal 알고리즘의 구현

 

개념 자체가 그리 어렵지 않기 때문에 구현도 쉽다. 아래는 자바로 구현한 Kruskal 알고리즘의 예시이다.

 

 

class KruskalMST {
    int N, M;
    List<Edge>[] graph;
    UnionFind uf;
    Edge[] tree;
    
    // 가중치를 기준으로 정렬하기 위한 코드(Comparator 사용)
    static class Weight_Comparison implements  Comparator<Edge> {
        public int compare(Edge e, Edge f) {
            if (e.weight > f.weight)
                return 1;
            else if (e.weight < f.weight)
                return -1;
            return 0;
        }
    }

	// 생성자 초기화
    public KruskalMST(List<Edge>[] adjList, int numOfEdges) {
        N = adjList.length;
        M = numOfEdges;
        graph = adjList;
        uf = new UnionFind(N);
        tree = new Edge[N-1];
    }

	// 실질적으로 최소 신장 트리를 구하는 부분
    public Edge[] mst() {
    	// 우선 순위 큐에 가중치 정렬을 위한 조건을 추가
        Weight_Comparison BY_WEIGHT = new Weight_Comparison();
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>(M, BY_WEIGHT);

        for(int i=0; i<N; i++) {
            for(Edge e : graph[i]) {
                pq.add(e);
            }
        }
        
        // u와 v 즉, 간선의 양 끝점이 같은 집합에 속하는 지 확인
        int count = 0;
        while(!pq.isEmpty() && count < N-1) {
            Edge e = pq.poll();
            int u = e.vertex;
            int v = e.adjvertex;
            
            // 양 끝 점이 다르다면, union을 통해 부모 통일, tree에 추가
            if (!uf.isConnected(u, v)) {
                uf.union(u, v);
                tree[count++] = e;
            }
        }
        return tree;
    }
}
class UnionFind {
    protected int[] p;
    protected int[] rank;

	// 초기화, 처음에는 자기 자신이 부모가 된다.
    public UnionFind(int N) {
        p = new int[N];
        rank = new int[N];
        for(int i=0 ;i<N; i++) {
            p[i] = i;
            rank[i] = 0;
        }
    }

	// find를 통해서 부모를 반환
    protected int find(int i) {
        if (i!=p[i]) {
            p[i] = find(p[i]);
        }
        return p[i];

    }
    
    // 부모가 같은 지 확인하는 함수
    public boolean isConnected(int i, int j) {
        return find(i) == find(j);
    }

	// i와 j의 부모를 확인하고 같도록 업데이트
    public void union(int i, int j) {
        int iroot = find(i);
        int jroot = find(j);
        if (iroot == jroot) return;
        if (rank[iroot] > rank[jroot]) {
            p[jroot] = iroot;
        } else if(rank[iroot] < rank[jroot]) {
            p[iroot] = jroot;
        } else {
            p[jroot] = iroot;
            rank[iroot]++;
        }
    }
}

class Edge {
    int vertex, adjvertex;
    int weight;
    public Edge(int u, int v, int wt) {
        vertex = u;
        adjvertex = v;
        weight = wt;
    }
}

 

 

조금 주의해서 보아야 할 것은 Union-Find 클래스이다. 이 클래스에서 union 함수는 은 두 그룹의 대표 부모가 다를 때, 한 그룹을 다른 그룹에 합치는 함수이다. 이때 rank라는 트리의 높이를 나타내는 배열을 사용하는 것을 확인해 볼 필요가 있다.

 

rank 트리의 높이를 나타낸다고 했는데, 이를 적절히 조절하며 union한다면 트리의 불균형을 줄일 수 있다. 이를 랭크 최적화라고 한다. 랭크 최적화를 통해서 전체 연산의 효율성을 향상 시킬 수 있는 이점이 있다.

 

아무튼, union 시 이러한 rank를 확인하는 과정이 존재한다. rank가 낮은 트리를 높은 트리에 맞춘다. 그렇게 해야 트리의 좌우 불균형이 해소될 수 있기 때문이다. 아래 그림을 보면 조금 더 이해가 쉬울 것이다.

 

 

두 랭크가 같은 경우라면, 둘 중 임의의 부모를 선택하고 rank를 올려줄 수 밖에 없기는 하다. Union - Find의 과정은 생각보다 많이 중요하므로, 꼭 숙지해 놓도록 하자.

 

프로그램 실행 결과는 아래와 같다.

 

 

 

Prim 알고리즘

 

 

Prim 알고리즘도 간단하다. Prim 알고리즘은 임의의 시작점에서 가장 가까운 정점을 추가하여 간선이 하나의 트리를 만들고, 만들어진 트리에 가장 가까운 정점을 하나씩 추가하여 MST를 만들 수 있다.

 

다시말해 하나의 정점에서 시작하는데, 그 정점과 연결되어 있는 정점 중, 가장 가중치가 작은 값을 선택한다. 이후, 선택한 값에서 다시 연결되어 있는 정점을 찾고, 가중치 작은 값을 찾는 과정을 반복한다.

 

이때, 트리에 속하지 않는 각 정점과 작은 가중치의 값을 찾기 위해 하나의 배열을 이용하는 것이 특징이다. 코드를 통해 구현 과정을 살펴보도록 하자.

 

 

 

Prim 알고리즘의 구현

 

class Edge {
    int adjvertex;
    int weight;
    public Edge(int v, int wt) {
        adjvertex = v;
        weight = wt;
    }
}

class PrimMST {
    int N;
    List<Edge>[] graph;

    public PrimMST(List<Edge>[] adjList) {
        N = adjList.length;
        graph = adjList;
    }

    public int[] mst (int s) {
    // 방문 체크 배열
        boolean[] visited = new boolean[N];
        int[] D = new int[N];

        int[] previous = new int[N];
        
        // 초기화, 방문을 모두 false, 이전 방문 노드를 -1로 초기화, D 배열은 사실 상 가중치를 모아두는 배열
        for(int i=0; i<N; i++) {
            visited[i] = false;
            previous[i] = -1;
            D[i] = Integer.MAX_VALUE;
        }
        previous[s] = 0;
        D[s] = 0;

		
        for(int k=0; k<N; k++) {
            int minVertex = -1;
            int min = Integer.MAX_VALUE;

        // 방문하지 않았으며, D 배열에서 가장 작은 값 찾기(가장 작은 가중치 값)
            for(int j=0; j<N; j++) {
                if ((!visited[j]) && (D[j] < min)) {
                    min = D[j];
                    minVertex = j;
                }
            }
            // 가장 작은 가중치 값을 가진 이웃 정점 방문(minVertex 방문)
            visited[minVertex] = true;
            
            // minVertex의 이웃노드 탐색
            for(Edge i : graph[minVertex]) {
            	// 그 이웃을 방문하지 않았다면,
                if (!visited[i.adjvertex]) {
                	// 트리에 추가되지 않은 값이라면, MAX_VALUE의 값을 가질 것임
                    int currentDist = D[i.adjvertex];
                    // 이웃의 가중치
                    int newDist = i.weight;
                    // 트리에 추가되지 않은 이웃이라는 뜻
                    if (newDist < currentDist) {
                    	// D 배열에 이웃의 가중치 값 추가
                        D[i.adjvertex] = newDist;
                        // 이웃의 이전 값에 minVertex 추가, 즉 방문이 확정된 것임
                        previous[i.adjvertex] = minVertex;
                    }
                }
            }
        }
        // 방문이 확정된 previous 배열을 리턴 = MST 값 반환
        return previous;
    }

}

 

 

눈여겨 볼 것은 (가장 작은 가중치의 값을 착고) + (MST 트리에 추가되지 않은 minVertex의 이웃 정점) 이라는 두 조건을 만족시키기 위해 가중치 값을 담은 D 배열을 사용했다는 것이다.

 

초기에 D 배열을 Integer.MAX_VALUE 값으로 지정해두고, MST 트리에 추가되지 않은 minVertex의 이웃 D값 만을 실제 가중치 값으로 둔다. 이로 인해, (MST 트리에 추가되지 않은 minVertex의 이웃 정점) 이라는 조건을 지킬 수 있는 것이다.

 

이 이후, for문을 돌면서 D 배열 중 가장 작은 값만 찾게되면 가장 작은 가중치를 얻게되는 것이다.

프로그램의 실행 결과는 아래와 같다.

 

 

 

 

Sollin 알고리즘

 

마지막으로 Sollin 알고리즘이다. Sollin 알고리즘의 핵심은 각 정점을 독립된 트리로 보는 것이다.

즉, 각 트리에 이웃한 정점에서 가중치가 가장 작은 간선을 선택해 나간다. 이후 트리가 합해지는 경우가 생기고 이는 1개의 트리가 만들어질 때까지 반복된다. 사실 상 이해하기는 제일 쉬운 알고리즘이다. 바로 구현을 살펴보자.

 

 

 

 

Sollin 알고리즘의 구현

 

 

import java.util.ArrayList;
import java.util.List;

class Edge {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

public class SollinMST {
    public static List<Edge> findMST(List<Edge> edges, int V) {
        List<Edge> minSpanningTree = new ArrayList<>();
        int[] cheapest = new int[V]; // cheapest[i]는 i번 정점을 연결하는 가장 가중치가 낮은 간선의 가중치를 저장
        int[] closest = new int[V];  // closest[i]는 i번 정점과 연결되는 가장 가중치가 낮은 간선의 목적 정점을 저장
        int[] component = new int[V]; // 각 정점이 속한 연결 요소의 번호

        // 초기화
        for (int i = 0; i < V; i++) {
            cheapest[i] = Integer.MAX_VALUE; // 모든 cheapest 배열 값 초기화
            closest[i] = -1; // 모든 closest 배열 값 초기화
            component[i] = i; // 모든 정점이 처음에는 자신을 단일 연결 요소로 가짐
        }

        int numComponents = V; // 초기 연결 요소 수는 정점 수와 같음

        // 최소 신장 트리를 구성할 때까지 반복
        while (numComponents > 1) {
            // 모든 간선을 순회하며 cheapest와 closest 배열을 업데이트
            for (Edge edge : edges) {
            	// 현재 간선의 출발점과 도착점이 속한 연결 요소를 가져온다.
                int component1 = component[edge.src];
                int component2 = component[edge.dest];
				
                // 서로 다른 연결 요소이기 때문에 후보 간선이 된다.
                if (component1 != component2) {
                	// 최소 가중치 선정
                    if (edge.weight < cheapest[component1]) {
                        cheapest[component1] = edge.weight;
                        closest[component1] = edge.dest;
                    }
                    if (edge.weight < cheapest[component2]) {
                        cheapest[component2] = edge.weight;
                        closest[component2] = edge.src;
                    }
                }
            }

            // 모든 정점을 순회하며 연결 요소를 병합하면서 최소 신장 트리를 구성
            for (int i = 0; i < V; i++) {
                if (closest[i] != -1) {
                
                	// 현재 정점과 연결 요소를 가져옴
                    int component1 = component[i];
                    int component2 = component[closest[i]];

                    if (component1 != component2) {
                        // 두 연결 요소를 병합
                        minSpanningTree.add(new Edge(i, closest[i], cheapest[i]));
                        numComponents--;

                        int oldComponent = component1;
                        int newComponent = component2;
                        // 연결 요소를 업데이트
                        for (int j = 0; j < V; j++) {
                            if (component[j] == oldComponent) {
                                component[j] = newComponent;
                            }
                        }
                    }
                    closest[i] = -1;
                }
            }
        }

        return minSpanningTree;
    }

    public static void main(String[] args) {
        int V = 4; // 정점의 수
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 2));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(1, 2, 2));
        edges.add(new Edge(1, 3, 4));
        edges.add(new Edge(2, 3, 1));

        List<Edge> minSpanningTree = findMST(edges, V);

        System.out.println("최소 신장 트리 간선:");
        for (Edge edge : minSpanningTree) {
            System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);
        }
    }
}

 

 

논리적으로는 이해하기 쉬우나, 생각 외로 코드 구현은 시간이 거리는 듯 싶다. 최소 신장 트리를 구성하기 위해 모든 정점을 하나의 트리로 보아 병렬적으로 탐색을 하고, 최소 가중치를 각각 찾는다. 이후, 가장 작은 가중치를 가진 간선들을 연결시켜주고 트리가 합쳐지는 경우도 처리한다.

 

 

 

 

각 알고리즘의 시간 복잡도

 

 

• Kruskal
  • 간선을 정렬하는데, 소요되는 시간 : O(mlogn)
  • 신장트리가 만들어 질 때까지 간선에 대해 isConnected()와 union() 수행하는 시간 : O((m+n) log * n)
  • O(mlogn) + O((m+n) log * n) = O(mlogn)
• Prim
  
  • minVertex를 찾기 위해 이진 힙(Binary Heap)을 사용하면, 각 간선에 대한 D 원소를 갱신하며 힙 연산을 수행해야하므로, O(mlogn)
  • 이진 힙은 각 정점에 대응되는 D 원소를 저장하므로, 힙의 최대 크기는 n
  • 가중치가 갱신되어 감소되었을 때의 힙 연산에는 O(logn)시간
  • 입력 그래프가 희소 그래프라면, m = O(n)이면, 수행 시간이 O(mlogn) = O(nlogn)이므로 이진 힙을 사용하는 것이 효율적이다.
  • 만약 피보나치 힙을 사용한다면 O(nlogn + m) 시간 소요, 다만 구현이 어려워 이론적인 자료구조이다.
• Sollin
  • repeat - 루프가 각 쌍의 트리가 서로 연결된 간선을 선택하는 경우는 최대 logn 수행
  • 각 트리가 자신에 닿아 있는 모든 간선을 검사하여 최소 가중치를 가진 간선을 선택하므로 O(m)시간 소요
  • 총 수행 시간은 O(mlogn)