신장 트리와 크루스칼 알고리즘

신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)

신장 트리(Spanning Tree)와 크루스칼 알고리즘(Kruskal Algorithm)에 대해서 배워보자.

신장 트리

신장 트리(Spanning Tree)란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

크루스칼 알고리즘

크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree, MST)를 구하기 위해서 사용되는 알고리즘 이다. 크루스칼 알고리즘은 그리디(Greedy) 알고리즘으로 분류된다. 크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다.

크루스칼 알고리즘을 구현할 때에는 Union-Find 알고리즘을 사용하므로, 잘 모른다면 링크를 통해서 미리 배우도록 하자.

위 그림이 최소 신장 트리를 나타낸다. 위 그래프에서 각 A, B, C 도시간 도로를 건설하는 비용이 10, 11, 12라고 할때 최소 비용으로 모든 도로를 연결하기 위한 비용은 10 + 11 = 21 일 것이다. 따라서, 최소 신장 트리 알고리즘이란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이라고 할 수 있다.

시간 복잡도는 다음과 같다.

$$O(ElogE)$$

E 는 간선의 개수를 의미하며, 간선을 정렬하는 작업이 시간이 가장 오래 걸리는 작업니다. E 개의 데이터를 정렬 했을 때의 시간 복잡도가 바로 O(ElogE)인 것이다.

동작 과정

• 간선 데이터를 비용에 따라 오름차순으로 정렬
• 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
  • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 O
  • 사이클이 발생하면 최소 신장 트리에 포함 X

최소 신장 트리에서 간선의 개수는 노드의 개수 - 1과 같다.

구현

// Edge : 간선에 연결되어 있는 노드들과 비용을 저장하기 위한 클래스
class Edge implements Comparable<Edge> {

    private int cost;
    private int nodeA;
    private int nodeB;

    public Edge(int cost, int nodeA, int nodeB) {
        this.cost = cost;
        this.nodeA = nodeA;
        this.nodeB = nodeB;
    }

    public int getCost() {
        return cost;
    }

    public int getNodeA() {
        return nodeA;
    }

    public int getNodeB() {
        return nodeB;
    }

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

public class Main {

    private static int vertexCount; // 노드, 정점
    private static int edgeCount; // 간선의 개수 = Union 연산의 횟수
    private static int[] parents; // 부모 테이블
    private static List<Edge> edges = new ArrayList<>();
    private static int answer = 0; // 문제에서 구하고자 하는 답 : MST 를 만드는데 드는 비용

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        vertexCount = sc.nextInt();
        edgeCount = sc.nextInt();
        initParents();
        for (int i = 0; i < edgeCount; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int cost = sc.nextInt();
            edges.add(new Edge(cost, a, b));
        }
        // 간선을 비용순으로 정렬
        Collections.sort(edges);
        // Kruskal Algorithm 수행
        kruskal();
        System.out.println(answer);
    }

    // 부모 테이블을 자기 자신의 노드로 초기화
    private static void initParents() {
        parents = new int[vertexCount + 1];
        for (int i = 1; i <= vertexCount; i++) {
            parents[i] = i;
        }
    }

    // Kruskal Algorithm
    private static void kruskal() {
        // 간선을 하나씩 확인하며
        for (int i = 0; i < edges.size(); i++) {
            int cost = edges.get(i).getCost();
            int nodeA = edges.get(i).getNodeA();
            int nodeB = edges.get(i).getNodeB();
            // 사이클이 발생하지 않는 경우에만 집합에 포함(Union 연산 수행)
            // 즉, nodeA 와 nodeB 에 대한 root 값이 달라야 한다는 의미
            if (findParent(nodeA) != findParent(nodeB)) {
                unionParent(nodeA, nodeB);
                answer += cost; // 최종 비용을 구하기 위한 연산
            }
        }
    }

    // find 연산
    // 특정 원소가 속한 집합을 찾기 : 경로 압축(Path Compression)
    private static int findParent(int vertex) {
        if (vertex == parents[vertex]) return vertex;
        return parents[vertex] = findParent(parents[vertex]);
    }

    // union 연산
    private static void unionParent(int nodeA, int nodeB) {
        nodeA = findParent(nodeA);
        nodeB = findParent(nodeB);
        if (nodeA < nodeB) {
            parents[nodeB] = nodeA;
        } else {
            parents[nodeA] = nodeB;
        }
    }
}

References

• 이것이 코딩 테스트다