Graph(3): Minimum Spanning Tree (최소 신장 트리)

정의

Spanning Tree (신장 트리)

• 그래프의 최소 연결 부분 그래프
• (무향 그래프에서) 최소 간선 수로 모든 정점이 연결된 그래프
• 무향 그래프는 여러 개의 스패닝 트리를 가질 수 있다.

Minimum Spanning Tree

• 가중치가 있는(weighted) 무향(undirected) 그래프에서
• 가능한 최소의 간선 가중치를 갖는 스패닝 트리
• 역시 여러 개의 MST가 가능하다.

Cut Property

용어

• cut: 그래프의 정점들을 분리된 두 개의 부분집합으로 나누는 것
• crossing edge(교차 간선): 한 집합의 정점과 다른 집합의 정점을 연결하는 간선

cut property

For any cut C of the graph, if the weight of an edge E in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.
그래프의 컷을 지나는 간선 중 가장 가중치가 작은 간선이 MST에 무조건 속하게 된다.

해당 속성은 크루스칼 알고리즘과 프림 알고리즘을 이론적으로 뒷받침한다.

크루스칼 알고리즘

"가중치가 있는 무향 그래프"의 "최소 신장 트리"를 구성하는 알고리즘
1. Ascending Sort all edges by their weight.
2. Add edges in that order into the MST. Skip the edges that would produce cycles in the MST. (서로소집합으로 확인!)
3. Repeat step 2 until N-1 edges are added.

가중치가 작은 간선부터 차례대로 순환을 만들지 않으면 추가하는 알고리즘

• 시간 복잡도: O(E * logE) (정렬 시간 O(ElogE) + union-find O(Ea(V))(두 정점이 사이클 만드는지 확인))
• 공간 복잡도: O(V) (union-find 자료 구조)

class Solution {
    // Kruskal's Algorithm
    public int minCostConnectPoints(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int size = points.length;
        PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);
        UnionFind uf = new UnionFind(size);

        for (int i = 0; i < size; i++) {
            int[] coordinate1 = points[i];
            for (int j = i+1; j < size; j++) {
                int[] coordinate2 = points[j];
                // Calculate the distance between two coordinates.
                int cost = Math.abs(coordinate1[0] - coordinate2[0]) + 
                           Math.abs(coordinate1[1] - coordinate2[1]);
                Edge edge = new Edge(i, j, cost);
                pq.add(edge);
            }
        }

        int result = 0;
        int count = size - 1;
        while (!pq.isEmpty() && count > 0) {
            Edge edge = pq.poll();
            if (!uf.connected(edge.point1, edge.point2)) {
                uf.union(edge.point1, edge.point2);
                result += edge.cost;
                count--;
            }
        }
        return result;
    }

    class Edge {
        int point1;
        int point2;
        int cost;

        Edge(int point1, int point2, int cost) {
            this.point1 = point1;
            this.point2 = point2;
            this.cost = cost;
        }
    }

    class UnionFind {
        int root[];
        int rank[];

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

        public int find(int x) {
            if (x == root[x]) {
                return x;
            }
            return root[x] = find(root[x]);
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
            }
        }

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

프림 알고리즘

임의의 정점에서 시작하여, 연결되지 않은 정점 중 가장 가중치가 작은 정점을 트리에 추가해나간다.

• 시간 복잡도: O(E * logV)
• 공간 복잡도: O(V) (정점 저장)

class Solution {
    // Prim Algorithm
    public int minCostConnectPoints(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int size = points.length;
        PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);
        boolean[] visited = new boolean[size];
        int result = 0;
        int count = size - 1;
        // Add all edges from points[0] vertexs
        int[] coordinate1 = points[0];
        for (int j = 1; j < size; j++) {
            // Calculate the distance between two coordinates.
            int[] coordinate2 = points[j];
            int cost = Math.abs(coordinate1[0] - coordinate2[0]) + 
                       Math.abs(coordinate1[1] - coordinate2[1]);
            Edge edge = new Edge(0, j, cost);
            pq.add(edge);
        }
        visited[0] = true;

        while (!pq.isEmpty() && count > 0) {
            Edge edge = pq.poll();
            int point1 = edge.point1;
            int point2 = edge.point2;
            int cost = edge.cost;
            if (!visited[point2]) {
                result += cost;
                visited[point2] = true;
                for (int j = 0; j < size; j++) {
                    if (!visited[j]) {
                        int distance = Math.abs(points[point2][0] - points[j][0]) + 
                                       Math.abs(points[point2][1] - points[j][1]);
                        pq.add(new Edge(point2, j, distance));
                    }
                }
                count--;
            }
        }
        return result;
    }

    class Edge {
        int point1;
        int point2;
        int cost;

        Edge(int point1, int point2, int cost) {
            this.point1 = point1;
            this.point2 = point2;
            this.cost = cost;
        }
    }
}