[바미] Graph algorithm - 최소 신장 트리(Minimum Spanning Tree, MST) 구현하기

최소 신장 트리?

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치 그래프에서 모든 노드를 포함하면서, 간선의 가중치 합이 최소인 트리를 의미하는데요. 이를 구하는 알고리즘으로는 Prim's Algorithm과 Kruskal's Algorithm이 있습니다.

 

Prim's Algorithm

Prim's Algorithm은 시작 정점에서부터 출발하여 신장 트리 집합을 확장해 나가는 방법입니다.

 

Kruskal's Algorithm

Kruskal's Algorithm은 간선들을 가중치 순으로 정렬한 후에 사이클을 형성하지 않는 선에서 차례대로 선택하는 방법입니다.

 

이제 Prim's Algorithm과 Kruskal's Algorithm을 구현해 볼까요?

 

Prim's Algorithm 구현

// 인접 리스트로 구현된 그래프를 입력 받습니다.
function primMST(graph) {
  const vertices = Object.keys(graph);
  const visited = {};
  const distance = {};

  // 시작 정점을 임의로 선택합니다.
  const startVertex = vertices[0];
  visited[startVertex] = true;
  distance[startVertex] = 0;

  // distance 배열을 모두 Infinity로 초기화합니다.
  for (let i = 1; i < vertices.length; i++) {
    const vertex = vertices[i];
    distance[vertex] = Infinity;
  }

  // MST에 포함되지 않은 정점들을 처리합니다.
  for (let i = 1; i < vertices.length; i++) {
    const adjacentVertices = graph[startVertex];
    for (let j = 0; j < adjacentVertices.length; j++) {
      const vertex = adjacentVertices[j][0];
      const weight = adjacentVertices[j][1];
      if (!visited[vertex] && weight < distance[vertex]) {
        distance[vertex] = weight;
      }
    }

    // distance 배열에서 최소 값을 찾습니다.
    let minVertex = null;
    let minValue = Infinity;
    for (let k = 1; k < vertices.length; k++) {
      const vertex = vertices[k];
      if (!visited[vertex] && distance[vertex] < minValue) {
        minVertex = vertex;
        minValue = distance[vertex];
      }
    }

    // MST에 해당 정점을 추가합니다.
    visited[minVertex] = true;
    startVertex = minVertex;
  }

  // MST에 포함된 간선들을 출력합니다.
  for (let i = 1; i < vertices.length; i++) {
    const vertex = vertices[i];
    const parent = distance[vertex];
    console.log(`${parent} - ${vertex}`);
  }
}

코드 설명

인접 리스트로 구현된 그래프를 입력으로 받아 주는데 우선, 시작 정점을 임의로 선택하고, visited 배열과 distance 배열을 초기화

해줘요.

 

그리고 MST에 포함되지 않은 정점들을 처리하는 반복문을 실행하게 되는데 이 때, 현재 정점과 인접한 정점들을 탐색하면서,

distance 배열의 값을 갱신하게 돼요. 그 다음 distance 배열에서 최소 값을 찾아서 MST에 해당 정점을 추가해준 뒤

마지막으로, MST에 포함된 간선들을 출력합니다. 출력할 때는 parent-vertex 형태로 출력되도록 구현하였는데

여기서 parent는 간선의 가중치를 의미해요.

 

 

Kruskal's Algorithm 구현

// 간선 리스트로 구현된 그래프를 입력 받습니다.
function kruskalMST(graph) {
  const edges = graph;
  edges.sort((a, b) => a[2] - b[2]);

  const parent = {};
  const rank = {};

  // 모든 정점의 부모를 자기 자신으로 초기화합니다.
  for (let i = 0; i < edges.length; i++) {
    const vertex1 = edges[i][0];
    const vertex2 = edges[i][1];
    parent[vertex1] = vertex1;
    parent[vertex2] = vertex2;
    rank[vertex1] = 0;
    rank[vertex2] = 0;
  }

  const mst = [];

  // 간선을 하나씩 처리합니다.
  for (let i = 0; i < edges.length; i++) {
    const vertex1 = edges[i][0];
    const vertex2 = edges[i][1];
    const root1 = find(vertex1);
    const root2 = find(vertex2);

    // 두 정점이 서로 다른 집합에 속해 있으면 MST에 추가합니다.
    if (root1 !== root2) {
      mst.push([vertex1, vertex2]);
      union(root1, root2);
    }
  }

  // MST에 포함된 간선들을 출력합니다.
  for (let i = 0; i < mst.length; i++) {
    const vertex1 = mst[i][0];
    const vertex2 = mst[i][1];
    console.log(`${vertex1} - ${vertex2}`);
  }

  function find(vertex) {
    if (parent[vertex] !== vertex) {
      parent[vertex] = find(parent[vertex]);
    }
    return parent[vertex];
  }

  function union(root1, root2) {
    if (rank[root1] > rank[root2]) {
      parent[root2] = root1;
    } else if (rank[root1] < rank[root2]) {
      parent[root1] = root2;
    } else {
      parent[root2] = root1;
      rank[root1]++;
    }
  }
}

// 예시
const graph = [
  [0, 1, 4],
  [0, 2, 3],
  [1, 2, 1],
  [1, 3, 2],
  [2, 3, 4],
  [3, 4, 2],
  [4, 5, 6],
  [3, 5, 3],
];

console.log("Kruskal's Algorithm:");
kruskalMST(graph);

코드 설명

위에서 간선 리스트로 구현된 그래프를 입력으로 받는데요. 먼저, 간선들을 가중치 순으로 정렬 한 뒤 모든 정점의 부모를 자기 자신으로 초기화하고, rank 배열도 초기화 해주는 작업을 해줘요.

다음으로, 간선을 하나씩 처리하는 반복문을 실행하게 되는데 이 때, '두 정점이 서로 다른 집합에 속해있는가?'에 대한 여부를 판단하기 위해 각 정점의 root(parent)를 찾는 find 함수를 구현하였습니다. 이 함수는 재귀적으로 자신의 부모를 찾아가며, 최종적으로 root를 반환해주죠.

 

 find 함수와 union 함수에 대해 설명해보자면

function find(vertex) {
  if (parent[vertex] !== vertex) {
    parent[vertex] = find(parent[vertex]);
  }
  return parent[vertex];
}

find 함수에서는 경로 압축(Path Compression) 기법을 적용하여, 부모 노드를 찾은 뒤 해당 정점의 parent를 부모 노드로 갱신하였어요. 이를 통해 다음 번에 같은 정점을 처리할 때 빠르게 찾을 수 있었죠.

그리고 두 정점의 root를 찾아서 서로 다른 집합에 속해 있는지 여부를 확인해주는데 만약 두 정점이 같은 집합에 속해 있다면, 이 간선을 추가하면 사이클이 형성되는데요.

 

이 부분에 대해 조금 설명을 덧붙이자면 Kruskal's Algorithm에서 새로운 간선을 추가할 때, 이미 같은 집합에 속한 두 정점을 연결하려고 하면 사이클이 형성된다는 의미인데, 따라서 Kruskal's Algorithm에서는 이미 같은 집합에 속한 두 정점을 연결하는 간선을 선택하지 않으면 사이클이 형성될 가능성을 배제할 수 있죠.

이와 반대로 서로 다른 집합에 속해 있다면, 이 간선을 MST에 추가하고, 두 집합을 합쳐줍니다. 이 때, rank 배열을 사용하여 랭크 기반 합침(Rank-based Union) 기법을 적용합니다.

 

 

function union(root1, root2) {
  if (rank[root1] > rank[root2]) {
    parent[root2] = root1;
  } else if (rank[root1] < rank[root2]) {
    parent[root1] = root2;
  } else {
    parent[root2] = root1;
    rank[root1]++;
  }
}

그리고 union함수에서 사용된 랭크 기반 합침 기법은 두 집합의 랭크(rank)를 비교하여, 랭크가 작은 집합을 랭크가 큰 집합에 합쳐줘요. 이 때, 랭크가 작은 집합의 root를 랭크가 큰 집합의 root의 자식으로 만들어주고, 만약 두 집합의 랭크가 같다면, 한 집합의 root를 다른 집합의 root의 자식으로 만들어주고, 랭크를 1 증가시켜줘요.

마지막으로, MST에 포함된 간선들을 출력하죠.

// MST에 포함된 간선들을 출력합니다.
for (let i = 0; i < mst.length; i++) {
  const vertex1 = mst[i][0];
  const vertex2 = mst[i][1];
  console.log(`${vertex1} - ${vertex2}`);
}

위와 같이 Kruskal's Algorithm을 구현할 수 있어요.