[javascript] 최소 신장 트리 알고리즘

18 Dec 2023

javascript

Kruskal 알고리즘은 그래프의 모든 정점을 독립된 트리로 만든 후, 가장 작은 가중치의 간선을 선택하여 트리를 연결합니다. 이때 사이클을 형성하는 간선은 제외합니다. 이 과정을 거쳐 모든 정점을 연결하며 가중치의 합이 최소인 트리를 찾습니다.

function kruskal(graph) {
  // 그래프에서 간선을 가중치로 정렬
  let edges = graph.edges.sort((a, b) => a.weight - b.weight);
  let mst = []; // 최소 신장 트리를 저장할 배열

  // 간선을 선택하여 사이클을 형성하지 않으면 mst에 추가
  for (let edge of edges) {
    if (!formsCycle(mst, edge)) {
      mst.push(edge);
    }
  }

  return mst;
}

function formsCycle(tree, edge) {
  // 사이클 형성 여부를 확인하는 로직
}

Prim 알고리즘

Prim 알고리즘은 시작 정점을 기준으로 해당 정점과 연결된 간선 중에서 최소 가중치를 선택하여 트리를 확장하는 방식으로 최소 신장 트리를 찾습니다.

function prim(graph) {
  let mst = []; // 최소 신장 트리를 저장할 배열
  let visited = new Set(); // 방문한 정점을 저장할 Set

  // 임의의 시작 정점을 선택
  let startVertex = graph.vertices[0];
  visited.add(startVertex);

  while (visited.size < graph.vertices.length) {
    let minEdge = findMinEdge(graph, visited);
    mst.push(minEdge);
    visited.add(minEdge.endVertex);
  }

  return mst;
}

function findMinEdge(graph, visited) {
  // 최소 가중치 간선을 찾는 로직
}

이렇게 Kruskal 알고리즘과 Prim 알고리즘을 사용하여 최소 신장 트리를 찾을 수 있습니다.

자세한 내용은 아래 참고 자료를 확인해주세요.

목차

Kruskal 알고리즘

Prim 알고리즘

참고 자료