[Algoritm 기초] 최소 신장 트리(Minimum Spanning Tree)

 

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

- 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법

 

비교예시

 

 

크루스칼 (Kruskal)

- 간선 중 최소 값을 가진 간선부터 연결

- 사이클 발생 시 다른 간선 선택

- 주로 간선 수가 적을 때 사용 

알고리즘 복잡도 : O(ElogE)

경로 최적화를 이용하지 않는 경우 O(ElogV), 경로 최적화를 이용하는 경우 O(Elog∗V)

 

 

프림(Prim)

- 임의의 노드에서 시작

- 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택

- 간선의 개수가 많을 때 쿠르스칼 보다 유리

알고리즘 복잡도 : O(ElogV)

바이너리 힙을 이용하는 경우 O(E+VlogV)

 

 

import java.util.Arrays;

//최소 신장 트리 - 크루스칼 

public class kruskal {
    static int parents[];

    public static int kruskal(int[][] data, int v , int e){
        int weightSum = 0;
        Arrays.sort(data, (x, y) -> x[2] - y[2]);

        parents = new int[v + 1];

        for (int i = 1; i < v + 1; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < e; i++) {
            if (find(data[i][0]) != find(data[i][1])){
                union(data[i][0], data[i][1]);
                weightSum += data[i][2];
            }
        }

        return weightSum;
    }

    public static void union(int a, int b){
        int aP = find(a);
        int bP = find(b);

        if (aP != bP) {
            parents[aP] = bP;
        }
    }

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

    public static void main(String[] args)  {
        int v = 7;
        int e = 10;

        int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

        System.out.println(kruskal(graph, v, e));

    }
}

 

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

//최소 신장 트리 - 프림

public class prim {
    static class Node{
        int to;
        int weight;

        public Node(int to, int weight){
            this.to = to;
            this.weight = weight;
        }
    }


    public static int prim(int[][] data, int v , int e){
        int weightSum = 0;

        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
            graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
        }

        boolean[] visited = new boolean[v + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.add(new Node(1, 0));

        int cnt = 0;
        while (!pq.isEmpty()){
            Node cur = pq.poll();
            cnt += 1;

            if (visited[cur.to]){
                continue;
            }

            visited[cur.to] = true;
            weightSum += cur.weight;

            if (cnt == v){
                return weightSum;
            }

            for (int i = 0; i < graph.get(cur.to).size() ; i++) {
                Node adjNode = graph.get(cur.to).get(i);
                if (visited[adjNode.to]){
                    continue;
                }
                pq.offer(adjNode);
            }
        }

        return weightSum;
    }

    public static void main(String[] args)  {
        int v = 7;
        int e = 10;

        int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

        System.out.println(prim(graph, v, e));

    }
}