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

turtleJ·2022년 8월 4일
0

최소 신장 트리(MST, Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘

  • 예) 도시가 여러 개 있을 때 각 도시를 도로로 연결하고자 할 때 비용을 최소화하는 방법


출처


그래프 이론을 통해 최소 신장 트리(Minimum Spanning Tree)를 공부해 본다.

용어

노드(Node) = 정점 = 도시 : 그래프 상에서 동그라미에 해당하는 부분
간선(Edge) = 거리 = 비용 : 그래프 상에서 선에 해당하는 부분
(* 최소 신장 트리에서 간선의 개수 = 노드 - 1)

풀이법

  • 이 알고리즘의 핵심은 간선(Edge)의 거리가 짧은 순서대로 그래프에 포함시킨다는 것이다.
  • 간선(Edge) 정보(가중치, 비용, 거리 등)를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함시킨다.
  • 이때 트리에 사이클이 형성되지 않도록 주의한다.
  • 대상이 되는 두 노드의 Root Node를 확인하여 그 둘이 같으면 사이클이 형성되는 것으로 간주한다.
  • Root Node가 같다면 같은 유니온(Union)에 속해있는 것이기 때문이다.
  • 따라서 최소 신장 트리(Minimum Spanning Tree)는 유니온파인드(Union-Find) 알고리즘에 가중치, 비용, 거리 등이 오름차순으로 정렬된 간선 정보를 추가하여 해결할 수 있다.

Code

public class Main {
    private static int[] parent;

    private static class Edge implements Comparable<Edge> {
        int node1;
        int node2;
        int weight;

        public Edge(int node1, int node2, int weight) {
            this.node1 = node1;
            this.node2 = node2;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return weight - o.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        parent = new int[V + 1];
        Edge[] edges = new Edge[E];

        // 각각의 노드들이 자신을 바라보도록 설정한다.
        // 유니온 파인드 초기화
        for (int i = 1; i < parent.length; i++) {
            parent[i] = i;
        }

        // Edge들을 배열에 넣어준다.
        for (int i = 0; i < edges.length; i++) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edges[i] = new Edge(node1, node2, weight);
        }

        // 클래스를 comparable인터페이스로 정렬기준을 오버라이딩 해놨기 때문에 가중치 기준으로 오름차순 정렬된다.
        Arrays.sort(edges);

        int res = 0;
        for (int i = 0; i < edges.length; i++) {
            Edge edge = edges[i];
            int node1 = edge.node1;
            int node2 = edge.node2;
            int weight = edge.weight;

            if (find(node1) != find(node2)) {
                union(node1, node2);
                res += weight;
            }
        }

        System.out.println(res);
    }

    private static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    private static void union(int a, int b) {
        int root1 = find(a);
        int root2 = find(b);

        if (root1 > root2) {
            parent[root1] = root2;
        } else {
            parent[root2] = root1;
        }
    }
}
profile
꾸준함을 무기로 성장하는 개발자가 되겠습니다.

0개의 댓글