[JS] 그래프

1. 인접 리스트

/**
 * @description 출발 노드, 도착 노드, 가중치를 포함한 이차원 배열을 인자로 받습니다.
 * @param {number} n 노드 갯수 
 * @param {[number, number, number][]} edges 
 */
function makeConnection(n, edges) {
  const con = Array.from({ length: n }, () => []);
  edges.forEach(([origin, dest, weight]) => con[origin].push([dest, weight]));

  return con;
}

2. BFS

function bfs(con, source, func) {
  const visit = Array(con.length).fill(false);
  const queue = [source];
  visit[source] = true;

  while (queue.length) {
    const cur = queue.shift();
    func(cur);

    con[cur].forEach(([neighbor]) => {
      if (visit[neighbor]) return;

      visit[neighbor] = true;
      queue.push(neighbor);
    });
  }
}

3. DFS

function dfs(con, source, func) {
  const visit = Array(con.length).fill(false);
  const stack = [source];
  visit[source] = true;

  while (stack.length) {
    const cur = stack.pop();
    func(cur);

    con[cur].forEach(([neighbor]) => {
      if (visit[neighbor]) return;

      visit[neighbor] = true;
      stack.push(neighbor);
    });
  }
}

4. 다익스트라

function dijkstra(con, source) {
  const size = con.length;
  const visit = Array(size).fill(false);
  const dist = Array(size).fill(Infinity);

  dist[source] = 0;

  while (true) {
    let minDist = Infinity;
    let minNode = null;

    for (let node = 0; node < size; node += 1) {
      if (!visit[node] && dist[node] < minDist) {
        minDist = dist[node];
        minNode = node;
      }
    }

    if (minNode === null) break;
    visit[minNode] = true;

    con[minNode].forEach(([neighbor, weight]) => {
      const alt = minDist + weight;
      if (alt < dist[neighbor]) dist[neighbor] = alt;
    });
  }

  return dist;
}

Heap과 함께 다익스트라를 사용했을 경우

Heap 알고리즘 구현 보기

function dijkstraWithHeap(con, source) {
  const size = con.length;
  const dist = Array(size);
  const heap = new Heap((a, b) => a[1] < b[1]);

  heap.add([source, 0]);

  while (heap.size) {
    const [minNode, minDist] = heap.poll();

    if (dist[minNode] !== undefined) continue;
    dist[minNode] = minDist;

    con[minNode].forEach(([neighbor, weight]) => {
      if (dist[neighbor] !== undefined) return;
      const alt = minDist + weight;
      heap.add([neighbor, alt]);
    });
  }

  return dist;
}

5. 벨만 포드

function bellmanFord(con, source) {
  const size = con.length;
  const dist = Array(size).fill(Infinity);
  dist[source] = 0;

  for (let i = 0; i < size; i += 1) {
    for (let node = 0; node < size; node += 1) {
      if (!Number.isFinite(dist[node])) continue;

      con[node].forEach(([neighbor, weight]) => {
        const alt = dist[node] + weight;
        if (alt < dist[neighbor]) dist[neighbor] = alt;
      });
    }
  }

  for (let node = 0; node < size; node += 1) {
    con[node].forEach(([neighbor, weight]) => {
      if (dist[neighbor] > dist[cur] + weight) return null;
    });
  }

  return dist;
}

6. 플로이드

function floyd(con) {
  const size = con.length;
  const dist = Array.from({ length: size }, () => Array(size).fill(Infinity));

  for (let node = 0; node < size; node += 1) {
    dist[node][node] = 0;
    con[node].forEach(([neighbor, weight]) => {
      dist[node][neighbor] = weight;
    });
  }

  for (let mid = 0; mid < size; mid += 1) {
    for (let origin = 0; origin < size; origin += 1) {
      if (origin === mid) continue;

      for (let dest = 0; dest < size; dest += 1) {
        const alt = dist[origin][mid] + dist[mid][dest];
        if (alt < dist[origin][dest]) dist[origin][dest] = alt;
      }
    }
  }

  return dist;
}

7. 위상 정렬

function topologicalSort(con) {
  const size = con.length;
  const visit = Array(size).fill(false);
  const stack = [];

  const topologicalSortUtil = (node) => {
    visit[node] = true;
    con[node].forEach(([neighbor]) => {
      if (!visit[neighbor]) topologicalSortUtil(neighbor);
    });

    stack.push(node);
  };

  for (let node = 0; node < size; node += 1) {
    if (!visit[node]) topologicalSortUtil(node);
  }

  return stack.reverse();
}

선행을 반드시 완료해야하는 위상 정렬

function topologicalSort(con) {
  const size = con.length;
  const indegree = Array(size).fill(0);
  const stack = [];
  const res = [];

  for (let i = 0; i < size; i += 1) {
    con[i].forEach(([node]) => {
      indegree[node] += 1;
    });
  }

  indegree.forEach((cnt, node) => {
    if (cnt === 0) stack.push(node);
  });

  while (stack.length) {
    const node = stack.pop();
    res.push(node);

    con[node].forEach((neighbor) => {
      indegree[neighbor] -= 1;
      if (indegree[neighbor] === 0) stack.push(neighbor);
    });
  }

  return res;
}