위상 정렬

algorithm class

suhwanc 2020. 2. 12. 16:05

위상 정렬은 사이클이 없는 단방향 그래프에서 그래프의 간선 u, v 가 있을 때,

정점의 순서를 찾는 알고리즘입니다.

위상 정렬을 구현할 때는 bfs를 사용합니다.

예를 들어

이런식으로 구성된 그래프가 있다고 합시다.

여기서 중요한건 위상 정렬을 사용하기 위해선 반드시 모든 간선이 한 방향을 향하고 있어야 한다는 점입니다.

이 그래프가 주어졌을 때 가장 먼저 해야하는 일은 각 노드의 차수를 계산해야 합니다.

차수를 계산하는 방법은 일반적인 그래프와 살짝다른데,

일반적으로는 트리의 높이가 그 노드의 차수였다면

여기서는 연결되어있는 부모의 수가 그 노드의 차수가 됩니다.

차수를 기록했으면 이제 부모가 존재하지 않는 노드들을 큐에 넣어줍니다.

큐를 만들어줬다면 이제 차례대로 bfs를 사용합니다.

이 때 가장 중요한건 주황색으로 칠해진 부분의 차수를 -1씩 해주면서 차수를 줄여나가야 합니다.

6은 아직 5가 pop되지 않았기 때문에 큐에 넣지 않습니다.

이후 과정을 생략한 결과는 : 4 5 3 2 6 1 8 7

이러한 결과는 차수가 0인 노드들을 큐에 넣는 순서에 따라 달라질 수 있습니다.

예시 문제 : 백준 2252번 줄 세우기