포드 풀커슨 최대 유량: 잔여 용량과 역방향 간선으로 선택 수정하기

별도 패키지는 필요하지 않습니다. Node.js가 처음이라면 브라우저와 Node.js 시작 안내부터 확인하세요.

algorithm-ford-fulkerson-residual-flow.mjs 파일을 만들고 아래 전체 코드를 저장합니다.

function maxFlow(n, edges, source, sink) {
  if (!Number.isInteger(n) || n < 2 || !Array.isArray(edges)) {
    throw new RangeError('정점 수 2 이상과 간선 배열이 필요합니다.');
  }
  const validVertex = v => Number.isInteger(v) && v >= 0 && v < n;
  if (!validVertex(source) || !validVertex(sink)) throw new RangeError('출발·도착 정점 범위를 확인하세요.');
  if (source === sink) throw new RangeError('출발점과 도착점은 서로 달라야 합니다.');
  const graph = Array.from({length:n}, () => []);
  const residual = [];
  let totalCapacity = 0;
  for (const edge of edges) {
    if (!Array.isArray(edge) || edge.length !== 3) throw new TypeError('간선은 [u,v,capacity]입니다.');
    const [u,v,capacity] = edge;
    if (!validVertex(u) || !validVertex(v)) throw new RangeError('간선 정점 번호가 범위를 벗어났습니다.');
    totalCapacity += capacity;
    if (!Number.isSafeInteger(capacity) || capacity < 0 || !Number.isSafeInteger(totalCapacity)) {
      throw new RangeError('용량과 그 합은 0 이상의 안전한 정수여야 합니다.');
    }
    const index = residual.length;
    residual.push({to:v,remaining:capacity,reverse:index+1});
    residual.push({to:u,remaining:0,reverse:index});
    graph[u].push(index);
    graph[v].push(index+1);
  }
  let value = 0;
  while (true) {
    const seen = Array(n).fill(false);
    const parentEdge = Array(n).fill(-1);
    seen[source] = true;
    function visit(u) {
      if (u === sink) return true;
      for (const index of graph[u]) {
        const edge = residual[index];
        if (edge.remaining <= 0 || seen[edge.to]) continue;
        seen[edge.to] = true;
        parentEdge[edge.to] = index;
        if (visit(edge.to)) return true;
      }
      return false;
    }
    if (!visit(source)) {
      return {
        value,
        flows:edges.map((edge,index) => edge[2]-residual[index*2].remaining),
        sourceSide:Array.from({length:n}, (_,v) => v).filter(v => seen[v])
      };
    }
    let amount = Infinity;
    for (let v = sink; v !== source;) {
      const edge = residual[parentEdge[v]];
      amount = Math.min(amount,edge.remaining);
      v = residual[edge.reverse].to;
    }
    for (let v = sink; v !== source;) {
      const edge = residual[parentEdge[v]];
      edge.remaining -= amount;
      residual[edge.reverse].remaining += amount;
      v = residual[edge.reverse].to;
    }
    value += amount;
  }
}

const edges = [[0,1,1],[1,2,1],[2,3,1],[0,2,1],[1,3,1]];
console.log(JSON.stringify(maxFlow(4,edges,0,3)));
console.log(JSON.stringify(maxFlow(2,[[0,1,2],[0,1,3],[1,0,7]],0,1)));

파일이 있는 폴더의 터미널에서 실행합니다.

node algorithm-ford-fulkerson-residual-flow.mjs

기대 출력

{"value":2,"flows":[1,0,1,1,1],"sourceSide":[0]}
{"value":5,"flows":[2,3,0],"sourceSide":[0]}