Suhwanc

위상 정렬

위상 정렬은 사이클이 없는 단방향 그래프에서 그래프의 간선 u, v 가 있을 때, 정점의 순서를 찾는 알고리즘입니다. 위상 정렬을 구현할 때는 bfs를 사용합니다. 예를 들어 이런식으로 구성된 그래프가 있다고 합시다. 여기서 중요한건 위상 정렬을 사용하기 위해선 반드시 모든 간선이 한 방향을 향하고 있어야 한다는 점입니다. 이 그래프가 주어졌을 때 가장 먼저 해야하는 일은 각 노드의 차수를 계산해야 합니다. 차수를 계산하는 방법은 일반적인 그래프와 살짝다른데, 일반적으로는 트리의 높이가 그 노드의 차수였다면 여기서는 연결되어있는 부모의 수가 그 노드의 차수가 됩니다. 차수가 0인 노드 : 4, 5, 3 차수가 1인 노드 : 2, 7, 8 차수가 2인 노드 : 6, 1 차수를 기록했으면 이제 부모가 존재하..