[JS] 크루스칼(Kruskal) 알고리즘

1. 가중치 그래프

 가중치 그래프는 간선에 가중치를 할당한 그래프를 말한다. 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 크루스칼(Kruskal) 알고리즘은 비용, 거리, 시간을 최소화하는 신장트리를 만들기 위해 나온 알고리즘이다. 즉, 모든 가중치의 합이 최소 값이 되어야 한다는 것이다. 최소 값이 나오게 하려면, 가중치를 오름차순으로 n-1만큼 더하면 된다. 그런데 앞에서 크루스칼 알고리즘에 대해 설명할 때 신장트리라는 말을 한 적이 있다. 신장 트리란, n 개의 정점을 가진 그래프 G에서 모든 정점이 n-1개의 간선으로 이루어진 트리를 말한다. 

 

[그림 1] 그래프 G와 신장트리

 

 

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

 크루스칼 알고리즘은 두 가지 방법이 있다. 첫 번째 방법은 가중치가 높은 간선을 제거하면서 최소 비용 신장트리를 만드는 것이고, 두 번째 방법은 가중치가 낮은 간선을 삽입하면서 최소 비용 신장트리를 만드는 것이다. 여기서 최소 비용 신장트리란, 가중치의 합이 최소인 신장트리를 말한다. 이번 포스팅에서 나는 두 번째 방법을 이용했고 프로그래밍했다. 따라서 두 번째 방법에 대해서만 설명을 하도록 하겠다.

 

 

 크루스칼 알고리즘을 구현하기 위해서는 다음과 같은 재료가 필요하다.

• 가중 그래프 G

• 간선 리스트

• 싸이클 테이블

  

[그림 2] 크루스칼 알고리즘 준비물

 

 

 간선리스트는 가중치 값을 기준으로 오름차순으로 정렬한다. 순환테이블은 각 정점이 자기 자신을 참조하도록 초기화한다. 그리고 그래프 G의 간선을 모두 없애버린다. 그리고 간선리스트에서 가중치가 작은 값 부터 값을 삽입해나가면 된다.

 

[그림 3] 크루스칼 알고리즘 시작 전

 

 간선 리스트에서 가중치 값이 2인 간선 (E,G)를 선택한다. 정점 E는 인접정점이 한 개도 없으므로 간선을 삽입한다. 그리고 순환테이블에서 정점 G가 E를 참조하도록 한다. 현재 간선의 개수는 1이므로 작업을 계속하도록 한다.

 

[그림 4] 크루스칼 알고리즘 1 단계

 

 간선리스트에서 가중치 값이 3인 간선 (A,B)를 선택한다. 정점 A는 인접 정점이 한 개도 없으므로 간선 (A, B)를 삽입한다. 그리고 순환 테이블에서 B는 A를 참조하도록 값을 바꿔준다. 현재 간선의 총 개수는 2이므로 작업을 계속하도록 한다.

 

[그림 5] 크루스칼 알고리즘 2단계

 

 간선 리스트에서 가중치 값이 4인 간선 (E,F)를 선택한다. 정점 E는 인접정점 G를 가지고 있다. 하지만 정점 F와 간선을 만든다 하더라도 순환 사이클에 전혀 영향을 주지 않는다. 그러므로 간선 (E,F)를 삽입하도록 한다. 또한, 순환 테이블에서 정점 F가 E를 참조하도록 값을 바꿔준다. 현재 그래프의 간선은 총 3개이므로 작업을 계속하도록 한다. 

 

[그림 6] 크루스칼 알고리즘 3단계

 

 간선리스트에서 가중치 값이 4인 간선 (B, D)를 선택한다. 정점 B는 인접정점 A가 있으나 D와 간선을 이룬다고 해서 A - B - D와 같이 순환 경로가 이루어지지 않는다. 따라서 간선 (B, D)를 삽입하도록 한다. 그리고 순환 테이블에서 정점 D는 정점 B를 참조하도록 값을 바꾼다. 이때 정점 B는 A를 참조하고 있으므로, B를 참조하는 정점 D는 A를 참조하게 된다. 현재 간선의 총 개수는 4이므로 작업을 계속 진행한다.

 

[그림 7] 크루스칼 알고리즘 4단계

 

 간선 리스트에서 가중치 값이 6인 간선 (A, D)를 선택한다. A는 인접정점이 B밖에 없다. 하지만 만약 간선 (A, D)를 삽입하게 되면 A - B - D - A와 같은 순환 경로가 만들어진다. 크루스칼 알고리즘은 순환 경로를 형성하는 간선을 삽입할 수 없다. 따라서 간선 (A, D)를 그래프에 삽입하지 않는다. 현재 간선의 총 개수는 4이므로 작업을 계속하도록 한다.

 

[그림 8] 크루스칼 알고리즘 5 단계

 

 

 간선 리스트에서 가중치 값이 8인 간선 (C, F)를 선택한다. C는 인접 정점이 하나도 없다. 간선을 연결하더라도 순환 경로가 만들어지지 않는다. 따라서 간선 (C, F)를 삽입한다. 이 때 순환테이블에서 F는 C를 참조하도록 값을 바꾼다. 현재 그래프의 간선의 총 개수는 5이므로 작업을 계속하도록 한다.

 

[그림 9] 크루스칼 알고리즘 6 단계

 

 간선 리스트에서 가중치 값이 9인 간선 (D, E)를 선택한다. 간선 (D, E)를 삽입하면 정점 전체가 연결된 경로가 만들어진다. 하지만 이 경로는 순환 경로가 아니다. 따라서 간선 (D, E)를 그래프에 삽입하도록 한다. 이 때 순환테이블에서는 E가 D를 참조하도록 한다. 그런데 D는 이미 A를 참조하고 있다. 따라서 D를 참조하는 E는 A를 참조하는 것이 되버린다. 그래서 E가 A를 참조하게끔 테이블 값을 바꾼다. 현재 그래프 간선의 총 개수는 6이다. 6은 그래프 정점 개수 7하고 1 차이가 난다. 따라서 크루스칼 알고리즘은 모든 과정을 마치고 종료된다.

 

[그림 10] 크루스칼 알고리즘 마지막 단계

 

 

3. 프로그램 코드

 const GraphNode = function(data, weight=null){
  this.data = data;
  this.link = null;
  this.weight = weight;
}

const weightGraph = function(size){
  this.graph = Array.from({length: size}, (data,i) => new GraphNode(String.fromCharCode(65+i)));
  

  weightGraph.prototype.insertEdge = function(v1, v2, w){
    const graph = this.graph;
    const v1Idx = v1.charCodeAt(0) - 65;
    const v2Idx = v2.charCodeAt(0) - 65;
    let v1Node = graph[v1Idx];
    let v2Node = graph[v2Idx];

    while(v1Node.link !== null)
      v1Node = v1Node.link;
    while(v2Node.link !== null)
      v2Node = v2Node.link;

    v1Node.link = new GraphNode(v2, w);
    v2Node.link = new GraphNode(v1, w);
  }

  weightGraph.prototype.printEdge = function(){
    const graph = this.graph;
    for(let i=0; i<size; i++){
      const vertex = graph[i];
      let node = graph[i];
      let vertexPrint = `${vertex.data}'s Edge:`;
      let edgePrint = '';
      

      while(node.link !== null){
        node = node.link;
        edgePrint += `E(${vertex.data}, ${node.data}, w: ${node.weight}) `;
      }

      console.log(vertexPrint, edgePrint);
    }
  }

  const getEdgeList = (arr, size) => {
    const graph = arr;
    const isWOverlap = [];
    const edgeList = [];

    for(let i=0; i<size; i++){
      let node = graph[i];
      const vertex = node;

      while(node.link !== null){
        const edgeObj = {
          'w': 0,
          'edge': [vertex.data]
        };
        node = node.link;
        edgeObj.w = node.weight;
        if(isWOverlap.indexOf(edgeObj.w) === -1){
            isWOverlap.push(edgeObj.w);
            edgeObj.edge.push(node.data);
            edgeList.push(edgeObj);
        }
      }
      vertex.link = null;
    }
    return edgeList;
  }

  weightGraph.prototype.Kruskal = function(){
    const graph = this.graph;  
    const cyTable = Array.from({length: size}, (e,i) => {
      const cyTableEl = new Object();
      cyTableEl.data = String.fromCharCode(65+i);
      return cyTableEl
    });
    let edgeList = getEdgeList(graph, size);
    const minEdgeList = [];

    edgeList = edgeList.sort((a,b) => a.w - b.w);

    while(minEdgeList.length < size-1){
      const edge = edgeList.shift();
      const v1 = edge.edge[0];
      const v2 = edge.edge[1];
      const v1Idx = v1.charCodeAt(0) - 65;
      const v2Idx = v2.charCodeAt(0) - 65;
      
      if(cyTable[v2Idx].data !== v1){
        cyTable[v2Idx].data = cyTable[v1Idx].data;
        this.insertEdge(v1, v2, edge.w);
        minEdgeList.push(edge);
      }
    }
  }
}


const main = (function(){
  const graph = new weightGraph(7);
  graph.insertEdge('A', 'B', 3);
  graph.insertEdge('A', 'C', 17);
  graph.insertEdge('A', 'D', 6);

  graph.insertEdge('B', 'D', 5);
  graph.insertEdge('B', 'G', 12);

  graph.insertEdge('C', 'E', 10);
  graph.insertEdge('C', 'F', 8);

  graph.insertEdge('D', 'E', 9);

  graph.insertEdge('E', 'F', 4);
  graph.insertEdge('E', 'G', 2);

  graph.insertEdge('F', 'G', 14);

  console.log("Before Kruskal Algorithm");
  graph.printEdge();
  graph.Kruskal();
  console.log("\n\nAfter Kruskal Algorithm");
  graph.printEdge();
}());

 

 

4. 참고 자료

• 자바로 배우는 쉬운 자료구조, 한빛 미디어

• 동빈나 - 19강 크루스칼 알고리즘(Kruskal Algorithm)[실전 알고리즘 강좌(Algorithm Programming Tutorial) #19]