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

깊이우선탐색과 너비우선탐색은 그래프 데이터를 탐색하는 강력한 두 가지 알고리즘이다. 이 두 방식의 초점은 정점(vertex 또는 node)에 있다. 모든 정점을 순회하거나 정점 사이의 최단 거리를 찾아내는 것이다.

 

반면 최소신장트리는 정점을 이어주는 '간선'을 위한 알고리즘이라 할 수 있다. 

 

MST는 아래의 경우 주로 사용된다.

1. 네트워크 설계 (최소 비용으로 모든 지점 연결)
2. 도로 건설 (최소 비용으로 모든 도시 연결)
3. 전기 회로 설계
4. 파이프라인 설계

네트워크 비용 계산 및 최적화:

통신망을 배치할 때마다 얼마나 비용이 들어갈 수 있는지 계산할 수 있다. 이는 최소신장트리가 간선 가중치의 합이 최소인 트리를 구성할 수 있기 때문이다.

 

효율적 전력망:

A에서 B까지 전기를 보내야 할 때 가장 빠르고 저렴한 공급 경로를 알 수 있다. 이는 최소신장트리가 순환구조 없이 최단경로를 찾을 수 있기 때문이다.

 

네트워크 확장:

최소신장트리는 네트워크를 위해 새로운 간선이나 정점이 추가되더라도 트리를 확장하거나 수정하여 최소신장트리를 계속해서 유지할 수 있다.

 

최소진장트리 구현에는 프림(prim) 알고리즘과 크루스칼(kruskal)알고리즘이 주로 사용된다.

 

 

1. 프림(prim) 알고리즘

 

특징:

• 최소 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘이다.
• 탐욕(Greedy) 알고리즘의 대표적인 예시이다.
• 시간복잡도는 O(V²)이며, 우선순위 큐를 사용하면 O(E logV)로 개선이 가능하다.

핵심 로직:

1. 임의의 시작 정점을 선택한다.
2. 현재 트리와 연결된 간선들 중 가장 가중치가 작은 간선을 선택한다.
3. 선택한 간선으로 연결된 정점을 트리에 추가한다.
4. 모든 정점이 연결될 때까지 2-3단계를 반복한다.

function primMST(graph) {
    // MST 구성에 필요한 배열들 초기화
    const parent = [];    // 각 정점의 부모 노드를 저장할 배열
    const key = [];      // 각 정점까지의 최소 가중치를 저장할 배열
    const visited = [];  // 정점의 방문 여부를 저장할 배열
    const { length } = graph;  // === graph.length: 그래프의 정점 개수
    
    // 모든 정점에 대한 초기화
    for(let i = 0; i < length; i++) {
        // Infinity: 자바스크립트 내장 전역변수로, 어떤 수보다도 큰 무한대를 표현
        key[i] = Infinity;  // 초기에는 모든 정점까지의 거리를 무한대로 설정
        visited[i] = false; // 모든 정점을 미방문 상태로 초기화
    }

    // 시작 정점(0번) 초기화
    key[0] = 0;      // 시작 정점의 가중치를 0으로 설정
    parent[0] = -1;  // 시작 정점의 부모는 없음을 표시

    // MST 구성 (정점 개수 - 1번 반복)
    for (let count = 0; count < length - 1; count++) {
        // 방문하지 않은 정점 중 key값이 최소인 정점 선택
        let u = minKey(key, visited);
        visited[u] = true;  // 선택된 정점을 방문 처리

        // 선택된 정점의 모든 인접 정점 검사
        for(let v = 0; v < length; v++) {
            // 조건: 간선이 존재하고(graph[u][v]), 미방문 정점이며(visited[v] === false),
            // 새로운 경로의 가중치가 기존보다 작은 경우(graph[u][v] < key[v])
            if(graph[u][v] && visited[v] === false && graph[u][v] < key[v]) {
                parent[v] = u;          // 새로운 부모 정점 저장
                key[v] = graph[u][v];   // 최소 가중치 갱신
            }
        }
    }
    
    return parent;  // 최소 신장 트리의 부모 정보 반환
}

function minKey(key, visited) {
    let min = Infinity;
    let minIndex;

    // 방문하지 않은 정점 중 key값이 최소인 정점 찾기
    for(let v = 0; v < key.length; v++) {
        if(visited[v] === false && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }
    return minIndex;  // 최소 key값을 가진 정점의 인덱스 반환
}

// 인접 행렬로 표현된 그래프: 각 원소는 정점 간의 연결 가중치(거리, 비용 등)를 나타냄
const graph = [
    //  0  1  2  3  4   <- 연결될 정점 번호(정점은 총 5개이다)
    [0, 2, 0, 6, 0],    // 0번 정점에서 다른 정점으로 가는 간선의 가중치
    [2, 0, 3, 8, 5],    // 1번 정점에서 다른 정점으로 가는 간선의 가중치
    [0, 3, 0, 0, 7],    // 2번 정점에서 다른 정점으로 가는 간선의 가중치
    [6, 8, 0, 0, 9],    // 3번 정점에서 다른 정점으로 가는 간선의 가중치
    [0, 5, 7, 9, 0]     // 4번 정점에서 다른 정점으로 가는 간선의 가중치
]
// 예시: 1번 정점(vertex, node)은 자기 자신(graph[1][1])과는 0의 가중치를 가지며, 
// 3번 정점과는 8의 가중치를 가진다. 0은 연결되지 않은 정점을 표시. 자기 자신과도 연결돼 있지 않기 때문에 0이다.


console.log(primMST(graph))	// [-1, 0, 1, 0, 1]


/*
[-1, 0, 1, 0, 1]의 의미 => [부모 없음, 0의 자식, 1의 자식, 0의 자식, 1의 자식]


각 인덱스별 의미:
parent[0] = -1  : 0번 정점은 시작점이므로 부모가 없음
parent[1] = 0   : 1번 정점의 부모는 0번 정점
parent[2] = 1   : 2번 정점의 부모는 1번 정점
parent[3] = 0   : 3번 정점의 부모는 0번 정점
parent[4] = 1   : 4번 정점의 부모는 1번 정점

도식화 한다면

	0
     / \
    1   3
   / \
  2   4
  
  
각 연결의 가중치까지 포함하는 경우

	0
     / \
  (2)1  3(6)
   /  \
(3)2   4(5)

 

 

 

2. 크루스칼(Kruskal) 알고리즘

프림 알고리즘과 마찬가지로 최소 신장 트리를 찾는 알고리즘이다.

 

특징:

• Union-Find 자료구조를 사용하여 사이클 여부를 확인한다.
• 시간복잡도는 O(E logE) 또는 O(E logV)이다.
• 프림과 달리 간선을 기준으로 동작한다.

핵심 로직:

1. 모든 간선을 가중치 순으로 정렬한다.
2. 가장 작은 가중치의 간선부터 선택한다.
3. 선택한 간선이 사이클을 만들지 않으면 트리에 추가한다.
4. 모든 정점이 연결될 때까지 2-3단계를 반복한다.

-->

 

 

• 모든 간선을 가중치 순으로 정렬
• 가장 작은 가중치의 간선부터 선택하되, 사이클을 만들지 않는 경우만 선택
• 사이클 검사는 Union-Find 자료구조를 사용해 효율적으로 수행
• (정점 수 - 1)개의 간선을 선택하면 완성

 

/**
 * 크루스칼 알고리즘 구현
 * 최소 신장 트리(MST)를 찾는 알고리즘
 * @param {number[][]} graph - 인접 행렬로 표현된 그래프
 * @returns {number[][]} - MST를 구성하는 간선들의 배열
 */
function kruskalMST(graph) {
    // 각 정점의 부모를 저장하는 배열 (Union-Find를 위해 사용)
    const parent = [];
    // 각 정점이 속한 트리의 높이를 저장하는 배열 (Union 최적화를 위해 사용)
    const rank = [];
    // 최소 신장 트리를 구성하는 간선들을 저장할 배열
    const result = [];
    // 그래프의 모든 간선을 저장할 배열
    let edges = [];

    // 1단계: 그래프의 모든 간선을 edges 배열에 저장
    // 무방향 그래프이므로 행렬의 위쪽 삼각형만 고려 (중복 방지)
    for (let u = 0; u < graph.length; u++) {
        for (let v = u + 1; v < graph.length; v++) {
            if (graph[u][v] !== 0) {
                // [시작정점, 도착정점, 가중치] 형태로 저장
                edges.push([u, v, graph[u][v]]);
            }
        }
    }

    // 2단계: 간선들을 가중치 기준으로 오름차순 정렬
    // 가중치가 작은 간선부터 선택하기 위함
    edges.sort((a, b) => a[2] - b[2]);

    // 3단계: Union-Find 자료구조 초기화
    // 처음에는 각 정점이 자신만을 포함하는 집합의 대표
    for (let node = 0; node < graph.length; node++) {
        parent[node] = node;  // 자기 자신이 부모
        rank[node] = 0;      // 초기 트리 높이는 0
    }

    // 4단계: 최소 신장 트리 구성
    let i = 0;
    // MST는 (정점 수 - 1)개의 간선을 가져야 함
    while (result.length < graph.length - 1 && i < edges.length) {
        // 현재 가장 가중치가 작은 간선 선택
        let [u, v, w] = edges[i++];
        
        // 두 정점의 대표 원소 찾기
        let x = find(parent, u);
        let y = find(parent, v);

        // 두 정점이 서로 다른 집합에 속해 있다면
        // (즉, 사이클을 만들지 않는다면)
        if (x !== y) {
            // 두 집합을 합치고
            union(parent, rank, x, y);
            // 해당 간선을 MST에 추가
            result.push([u, v, w]);
        }
    }
    return result;
}

/**
 * Find 연산: 정점이 속한 집합의 대표 원소를 찾음
 * 경로 압축(Path Compression) 최적화 포함
 */
function find(parent, node) {
    // 자신이 대표가 아니라면
    if (parent[node] !== node) {
        // 대표를 찾아서 바로 연결 (경로 압축)
        parent[node] = find(parent, parent[node]);
    }
    return parent[node];
}

/**
 * Union 연산: 두 집합을 하나로 합침
 * 랭크 기반 합치기(Union by Rank) 최적화 포함
 */
function union(parent, rank, x, y) {
    // 랭크가 더 큰 집합이 작은 집합을 흡수
    if (rank[x] > rank[y]) {
        parent[y] = x;  // y의 대표를 x로 변경
    } else if (rank[x] < rank[y]) {
        parent[x] = y;  // x의 대표를 y로 변경
    } else {
        // 랭크가 같은 경우, 한쪽을 임의로 선택하고 랭크 증가
        parent[y] = x;
        rank[x]++;
    }
}

// 테스트용 그래프
const graph = [
    [0, 2, 0, 6, 0],  // 0번 정점의 간선들
    [2, 0, 3, 8, 5],  // 1번 정점의 간선들
    [0, 3, 0, 0, 7],  // 2번 정점의 간선들
    [6, 8, 0, 0, 9],  // 3번 정점의 간선들
    [0, 5, 7, 9, 0],  // 4번 정점의 간선들
];

console.log(kruskalMST(graph));
// 출력: [[0,1,2], [1,2,3], [1,4,5], [0,3,6]]
// 의미: [정점1, 정점2, 가중치] 형태로 MST를 구성하는 간선들

 

 

 

 

예제

도시를 가로지르는 전선 설치

/**
 * 크루스칼 알고리즘 구현
 * 최소 신장 트리(MST)를 찾는 알고리즘
 * @param {number[][]} graph - 인접 행렬로 표현된 그래프
 * @returns {number[][]} - MST를 구성하는 간선들의 배열
 */
function kruskalMST(graph) {
    // 각 정점의 부모를 저장하는 배열 (Union-Find를 위해 사용)
    const parent = [];
    // 각 정점이 속한 트리의 높이를 저장하는 배열 (Union 최적화를 위해 사용)
    const rank = [];
    // 최소 신장 트리를 구성하는 간선들을 저장할 배열
    const result = [];
    // 그래프의 모든 간선을 저장할 배열
    let edges = [];

    // 1단계: 그래프의 모든 간선을 edges 배열에 저장
    // 무방향 그래프이므로 행렬의 위쪽 삼각형만 고려 (중복 방지)
    for (let u = 0; u < graph.length; u++) {
        for (let v = u + 1; v < graph.length; v++) {
            if (graph[u][v] !== 0) {
                // [시작정점, 도착정점, 가중치] 형태로 저장
                edges.push([u, v, graph[u][v]]);
            }
        }
    }

    // 2단계: 간선들을 가중치 기준으로 오름차순 정렬
    // 가중치가 작은 간선부터 선택하기 위함
    edges.sort((a, b) => a[2] - b[2]);

    // 3단계: Union-Find 자료구조 초기화
    // 처음에는 각 정점이 자신만을 포함하는 집합의 대표
    for (let node = 0; node < graph.length; node++) {
        parent[node] = node;  // 자기 자신이 부모
        rank[node] = 0;      // 초기 트리 높이는 0
    }

    // 4단계: 최소 신장 트리 구성
    let i = 0;
    // MST는 (정점 수 - 1)개의 간선을 가져야 함
    while (result.length < graph.length - 1 && i < edges.length) {
        // 현재 가장 가중치가 작은 간선 선택
        let [u, v, w] = edges[i++];
        
        // 두 정점의 대표 원소 찾기
        let x = find(parent, u);
        let y = find(parent, v);

        // 두 정점이 서로 다른 집합에 속해 있다면
        // (즉, 사이클을 만들지 않는다면)
        if (x !== y) {
            // 두 집합을 합치고
            union(parent, rank, x, y);
            // 해당 간선을 MST에 추가
            result.push([u, v, w]);
        }
    }
    return result;
}

/**
 * Find 연산: 정점이 속한 집합의 대표 원소를 찾음
 * 경로 압축(Path Compression) 최적화 포함
 */
function find(parent, node) {
    // 자신이 대표가 아니라면
    if (parent[node] !== node) {
        // 대표를 찾아서 바로 연결 (경로 압축)
        parent[node] = find(parent, parent[node]);
    }
    return parent[node];
}

/**
 * Union 연산: 두 집합을 하나로 합침
 * 랭크 기반 합치기(Union by Rank) 최적화 포함
 */
function union(parent, rank, x, y) {
    // 랭크가 더 큰 집합이 작은 집합을 흡수
    if (rank[x] > rank[y]) {
        parent[y] = x;  // y의 대표를 x로 변경
    } else if (rank[x] < rank[y]) {
        parent[x] = y;  // x의 대표를 y로 변경
    } else {
        // 랭크가 같은 경우, 한쪽을 임의로 선택하고 랭크 증가
        parent[y] = x;
        rank[x]++;
    }
}

// 테스트용 그래프
const graph = [
    [0, 2, 0, 6, 0],  // 0번 정점의 간선들
    [2, 0, 3, 8, 5],  // 1번 정점의 간선들
    [0, 3, 0, 0, 7],  // 2번 정점의 간선들
    [6, 8, 0, 0, 9],  // 3번 정점의 간선들
    [0, 5, 7, 9, 0],  // 4번 정점의 간선들
];

const cities = ["서울", "부산", "대구", "인천", "광주"]

// console.log(kruskalMST(graph));
// 출력: [[0,1,2], [1,2,3], [1,4,5], [0,3,6]]
// 의미: [정점1, 정점2, 가중치] 형태로 MST를 구성하는 간선들

const result = kruskalMST(graph);
for ( let i = 0; i < result.length; i++) {
    console.log(`${cities[result[i][0]]} 와 ${cities[result[i][1]]} 전선 연결비용: ${result[i][2]}`);
}

/*

서울 와 부산 전선 연결비용: 2
부산 와 대구 전선 연결비용: 3
부산 와 광주 전선 연결비용: 5
서울 와 인천 전선 연결비용: 6
*/