공항 문제에 그래프 알고리즘(Kruskal)의 최소 스패닝 트리를 사용하는 방법.

시간 간격이 있는 여러 공항 연결이 주어지면 가능한 최단 시간에 모든 공항을 통과하는 경로를 찾습니다(동일한 공항으로 돌아가는 것은 제외).

문제는 다음과 같이 번역될 수 있습니다. 무방향 가중 연결 그래프에서 최소 스패닝 트리(MST)를 찾습니다.

A MST is a subgraph consisting of all the nodes in the graph with one exclusive path from a node to every other one (no cycles) and having the minimum sum of all edges weight among all such subgraphs.

7개의 직항 항공편이 있는 5개의 공항과 시간 단위의 예:

5 7
MAD XDT 2
MAD OTP 3
MAD FRA 4
MAD BER 4
XDT OTP 3
OTP FRA 4
FRA BER 2

모든 공항을 통과하는 최단 경로는 11시간이 소요됩니다.

MAD -- XDT ( 2 )
FRA -- BER ( 2 )
MAD -- OTP ( 3 )
MAD -- FRA ( 4 )
time:  11

6개의 직항 항공편이 있는 4개의 공항과 시간 단위의 예:

4 6
ANK BCN 3
ANK COS 2
DTM ANK 6
BCN DTM 7
COS BCN 4
COS DTM 5

따라서 앙카라(ANK)에서 바르셀로나(BCN)까지 비행기로 3시간이 걸립니다.

모든 공항을 통과하는 가장 짧은 경로는 12시간이 걸립니다.

ANK -- COS ( 3 )
COS -- BCN ( 4 )
COS -- DTM ( 5 )
time:  12

Kruskal 알고리즘을 사용하여 그래프 최소 스패닝 트리를 찾을 수 있습니다. 그래프의 노드 수가 V인 경우 각 스패닝 트리는 (V-1) 에지를 갖고 사이클을 포함하지 않아야 합니다.
크루스칼 단계:

Initialize an empty edge set T 
Sort all graph edges by the ascending order of their weight values
Foreach edge in the sorted edge list
    Check whether it will create a cycle with the edges inside T
    If the edge doesn't introduce any cycles, add it into T
    If T has (V-1) edges, exit the loop
return T

Node.js 구현:

'use strict';

let fs = require('fs'),
    readline = require('readline');

class Edge {
    constructor(v1, v2, w = 0) {
        this.v1 = v1;
        this.v2 = v2;
        this.w = w;
    }
}

class Graph {
    constructor(v, e) {
      this.v = v;
      this.e = e;
      this.edges = [];
      this.nodes = [];
    }

    addEdge(edge) {
      this.edges.push(edge);
      if (!this.nodes.includes(edge.v1)) {
        this.nodes.push(edge.v1);
      }
      if (!this.nodes.includes(edge.v2)) {
        this.nodes.push(edge.v2);
      }
    }

    getEdge(pos) {
      return this.edges[pos]
    }

    getEdges() {
      return this.edges
    }

    getNodes() {
      return this.nodes
    }

    // get the root of node
    find(subsets, node) {
      let nodeInfo = subsets.get(node);
      if (nodeInfo.parent != node) {
        nodeInfo.parent = this.find(subsets, nodeInfo.parent)
      }

      return nodeInfo.parent; 
    }

    // unite the x and y subsets based on rank
    union(subsets, x, y) {
        let xroot = this.find(subsets, x);
        let yroot = this.find(subsets, y);

        if (subsets.get(xroot).rank < subsets.get(yroot).rank) {
            subsets.get(xroot).parent = yroot;
        } else if (subsets.get(xroot).rank > subsets.get(yroot).rank) {
          subsets.get(yroot).parent = xroot;
        } else {
          subsets.get(yroot).parent = xroot;
          subsets.get(xroot).rank++;
        }
    } 
}

function kruskal(gNodes, gEdges, gFrom, gTo, gWeight) {
    let i = 0, j = 0, cost = 0;
    let subsets = new Map(),
        result = [];

    let graph = new Graph(gNodes, gEdges);

    while(i < gEdges) {
      graph.addEdge(new Edge(gFrom[i], gTo[i], gWeight[i]));
      i++;
    }

    graph.getEdges().sort((edge1, edge2) => {
      if (edge1.w === edge2.w) {
        return 1;
      }

      return edge1.w < edge2.w ? -1 : 1;
    });

    console.log('sorted edges:' , graph.getEdges());

    graph.getNodes().forEach(node => {
      subsets.set(node, { parent: node, rank: 0 });
    });

    i = 0;
    while(j < gNodes-1) {
      let edge = graph.getEdge(i++);
      let root1 = graph.find(subsets, edge.v1); 
      let root2 = graph.find(subsets, edge.v2);

      // if the nodes doesn't create a cycle then we add the edge to final subgraph
      if (root1 != root2) {
          result[j++] = edge;
          // update the total weight of the subgraph
          cost += edge.w;
          graph.union(subsets, root1, root2);
      }
    }

    i = 0;
    while(i < j) {
      console.log(`${result[i].v1} -- ${result[i].v2} ( ${result[i++].w} )`);
    }
    console.log('time: ', cost);
}

function readFile(fileName) {
  let fileStream = fs.createReadStream(fileName),
      rl,
      data = '', 
      index = 0,
      gNodes = 0, 
      gEdges = 0, 
      gFrom = [],
      gTo = [],
      gWeight = [];

  fileStream.on('error', (err) => {
    console.log('file issue: ', err.message)
  });

  rl = readline.createInterface({
      input: fileStream
  });
  // 'line' event - emitted whenever the input stream receives a new line \n
  rl.on('line', (line) => {
      data = line.split(' ');
      if (index == 0) {
          gNodes = parseInt(data[0], 10);
          gEdges = parseInt(data[1], 10);
      } else if (index <= gEdges) {
          gFrom.push(data[0]);
          gTo.push(data[1]);
          gWeight.push(parseInt(data[2], 10));
      }
      index++;
  });

  rl.on('close', () => {
    if (gNodes && gEdges && gFrom.length && gTo.length && gWeight.length) {
      kruskal(gNodes, gEdges, gFrom, gTo, gWeight);
    } else console.log('invalid data file');
  });
}

readFile('data1.txt');

GitHub에서 코드를 확인하세요.
Girlsincode에서 이와 같은 추가 기사 읽기