javascript - 크루스칼(Kruskal)

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 그래프에서 최소 비용 신장 트리를 찾기 위한 알고리즘입니다. 주요 아이디어는 간선의 비용을 기준으로 오름차순 정렬한 후, 가장 작은 비용의 간선부터 연결하되 사이클을 형성하지 않도록 주의하는 것입니다.

아래는 크루스칼 알고리즘의 기본 개념을 사용하여, 그래프에서 최소 비용 신장 트리의 총 비용을 구하는 자바스크립트 함수입니다.

class UnionFind {
    constructor(size) {
        this.parent = Array.from({ length: size }, (_, index) => index);
    }

    find(node) {
        if (this.parent[node] === node) {
            return node;
        }
        return this.parent[node] = this.find(this.parent[node]);
    }

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

        if (rootA !== rootB) {
            this.parent[rootB] = rootA;
            return true;
        }
        return false;
    }
}

function kruskal(edges, numVertices) {
    edges.sort((a, b) => a[2] - b[2]);
    const uf = new UnionFind(numVertices);
    let totalCost = 0;

    for (let edge of edges) {
        if (uf.union(edge[0], edge[1])) {
            totalCost += edge[2];
        }
    }

    return totalCost;
}

const edges = [[0, 1, 1], [1, 2, 2], [0, 2, 3], [2, 3, 4]];
const numVertices = 4;

console.log(kruskal(edges, numVertices)); // 7

간선을 비용 기준으로 오름차순 정렬한 후, 간선을 하나씩 검사하면서 연결합니다. 이때, 사이클을 형성하는지 체크하기 위해 UnionFind 자료구조를 사용합니다.

union 메서드가 true를 반환하면 해당 간선은 사이클을 형성하지 않으므로, 최소 비용 신장 트리에 포함시키고 비용을 합산합니다.

console.log의 결과로는 최소 비용 신장 트리의 총 비용인 7이 출력됩니다.