TIL_2023.07.25

위상 정렬은 각 노드에 연결된 간선을
진입 간선과 진출 간선으로 나누어서
진입 간선이 0인 노드 부터 차례대로 진행하는 정렬이다.

수업 커리큘럼(사칙연산 -> 방정식)과 같이 진행 순서가 중요한 상황에서 쓰일 수 있다.

//[노드개수, 간선개수]
const [n, e] = [7, 8];
//연결노드 [시작노드, 연결될 노드]
const edges = [
  [1, 2],
  [1, 5],
  [2, 3],
  [2, 6],
  [3, 4],
  [4, 7],
  [5, 6],
  [6, 4],
];
let a = [];

//진입 간선을 나타내는 배열 생성 및 할당)
const indegree = Array.from({ length: n + 1 }, () => 0);
edges.forEach((edge) => {
  const [_, v] = edge;
  indegree[v]++;
});

//큐 생성(indegree를 돌면서 값이 0을 만나면 큐에 담아줌/최초시작)
//배열 생성 때 0부터 시작하긴 했으나 실제 노드는 1부터 시작합니다.
const queue = [];
for (let v = 1; v <= n; v++) {
  if (indegree[v] === 0) queue.push(v);
}

//큐의 맨 앞 노드를 제거한 후 a배열에 담아줌(순서기록 위함)
//큐가 빌 때까지 반복해서 실행
while (queue.length !== 0) {
  const now = queue.shift();
  a.push(now);
    for (const edge of edges) {
    //이번에 확인한 노드에 연결 되어있던 간선에 해당하는 진입 간선 개수를 하나 감소 시킴
    if (edge[0] === now) {
      indegree[edge[1]]--;
      //감소 된 진입 간선의 개수가 0일 경우 큐에 다시 담아주고 로직 반복
      if (indegree[edge[1]] === 0)   queue.push(edge[1]);
    }
  }
}

참고 블로그
https://nohack.tistory.com/137