Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

자바스크립트로 구현하는 크루스칼(Kruskal) 최소 신장 트리 알고리즘

크루스칼 알고리즘이란?

크루스칼(Kruskal) 알고리즘은 가중치 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 대표적인 그리디(Greedy) 알고리즘입니다. 네트워크 설계, 도로 포설, 통신 케이블 배치처럼 모든 지점을 연결하면서 비용을 최소화해야 하는 문제에 널리 활용됩니다.

알고리즘의 동작 순서는 다음과 같습니다.

  1. 그래프의 모든 간선(edge)을 하나의 집합으로 만듭니다.
  2. 집합이 비어 있지 않고, 모든 정점이 아직 커버되지 않은 동안 다음을 반복합니다.
    • 집합에서 가중치가 가장 작은 간선을 꺼냅니다.
    • 해당 간선이 사이클을 형성하는지, 아니면 단순히 두 개의 트리를 연결하는지 확인합니다. 사이클을 형성하면 이 간선은 버리고, 그렇지 않으면 트리에 추가합니다.
  3. 위 과정이 모두 끝나면 최소 신장 트리가 완성됩니다.

필요한 보조 자료구조

크루스칼 알고리즘을 실제로 구현하려면 두 가지 자료구조가 추가로 필요합니다.

1. 우선순위 큐(Priority Queue)

간선들을 가중치 기준으로 정렬된 상태로 유지하고, 매 반복마다 필요한 간선(최소 가중치 간선)을 효율적으로 꺼내기 위해 사용합니다.

2. 서로소 집합(Disjoint Set, Union-Find)

서로소 집합 자료구조는 유니온-파인드(Union-Find) 또는 머지-파인드 셋(Merge–Find Set)이라고도 불리며, 서로 겹치지 않는(non-overlapping) 여러 부분집합으로 분할된 원소들을 추적하는 자료구조입니다. 새 노드를 트리에 추가할 때마다 두 정점이 이미 연결되어 있는지 확인합니다. 이미 연결되어 있다면 사이클이 존재하는 것이므로 간선을 무시하고, 연결되어 있지 않다면 union 연산으로 간선의 양쪽 정점을 같은 부분집합에 합칩니다.

UnionFind(서로소 집합) 클래스 구현

먼저 유니온-파인드 자료구조를 구현해 보겠습니다.

class UnionFind {
    constructor(elements) {
        // 분리된 컴포넌트(연결 요소)의 개수
        this.count = elements.length;

        // 연결된 컴포넌트를 추적
        this.parent = {};

        // 모든 원소가 자기 자신을 부모로 가지도록 초기화
        elements.forEach(e => (this.parent[e] = e));
    }

    union(a, b) {
        let rootA = this.find(a);
        let rootB = this.find(b);

        // 루트가 같다면 이미 연결되어 있는 상태
        if (rootA === rootB) return;

        // 항상 더 작은 루트를 가진 원소를 부모로 만든다
        if (rootA < rootB) {
            if (this.parent[b] != b) this.union(this.parent[b], a);
            this.parent[b] = this.parent[a];
        } else {
            if (this.parent[a] != a) this.union(this.parent[a], b);
            this.parent[a] = this.parent[b];
        }
    }

    // 노드의 최종 부모(루트)를 반환
    find(a) {
        while (this.parent[a] !== a) {
            a = this.parent[a];
        }
        return a;
    }

    // 두 노드의 연결 여부 확인
    connected(a, b) {
        return this.find(a) === this.find(b);
    }
}

다음과 같이 테스트할 수 있습니다.

let uf = new UnionFind(["A", "B", "C", "D", "E"]);
uf.union("A", "B"); uf.union("A", "C");
uf.union("C", "D");

console.log(uf.connected("B", "E"));
console.log(uf.connected("B", "D"));

실행 결과

false
true

B와 E는 서로 다른 집합에 속해 있어 false, B와 D는 A-C-D를 통해 연결되어 있어 true가 출력됩니다.

크루스칼 알고리즘 구현

이제 앞서 만든 자료구조를 활용해 크루스칼 알고리즘을 구현해 보겠습니다.

kruskalsMST() {
    // MST를 담을 그래프 초기화
    const MST = new Graph();
    this.nodes.forEach(node => MST.addNode(node));
    if (this.nodes.length === 0) {
        return MST;
    }

    // 우선순위 큐 생성
    edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);

    // 모든 간선을 큐에 추가
    for (let node in this.edges) {
        this.edges[node].forEach(edge => {
            edgeQueue.enqueue([node, edge.node], edge.weight);
        });
    }

    let uf = new UnionFind(this.nodes);

    // 모든 노드를 탐색하거나 큐가 빌 때까지 반복
    while (!edgeQueue.isEmpty()) {
        // 구조 분해 할당으로 간선 데이터 가져오기
        let nextEdge = edgeQueue.dequeue();
        let nodes = nextEdge.data;
        let weight = nextEdge.priority;

        if (!uf.connected(nodes[0], nodes[1])) {
            MST.addEdge(nodes[0], nodes[1], weight);
            uf.union(nodes[0], nodes[1]);
        }
    }
    return MST;
}

실제 그래프를 만들어 테스트해 보겠습니다.

let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");

g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("C", "D", 3);
g.addEdge("D", "E", 8);
g.addEdge("E", "F", 10);
g.addEdge("B", "G", 9);
g.addEdge("E", "G", 50);

g.kruskalsMST().display();

실행 결과

A->B, D
B->A, G
C->D
D->C, A, E
E->D, F
F->E
G->B

출력 결과를 보면 가중치가 100인 A-C 간선과 50인 E-G 간선이 제외된 것을 확인할 수 있습니다. 이 간선들은 사이클을 형성하기 때문에 MST에 포함되지 않으며, 그 결과 전체 가중치의 합이 최소가 되는 신장 트리가 만들어집니다.

시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 간선을 가중치 순으로 정렬·추출하는 과정이 지배적이므로 O(E log E)입니다(E는 간선의 수). 유니온-파인드 연산은 경로 압축(path compression)과 랭크(rank) 기법을 함께 사용하면 거의 상수 시간에 처리할 수 있어, 전체 성능에 큰 영향을 주지 않습니다.