[알고리즘] 위상 정렬(Toplogiclal Sort)

순서가 정해져 있는 일련의 알고리즘을 수행해야 할 때 사용되는 알고리즘이다. 

 

'사이클이 없는 방향 그래프의 모든 노드를 순서대로 나열하는 것' 이다.

대표적으로 선수학습 과목 등의 예시가 있다.

 

진입차수와 진출차수

진입차수(indegree): 특정 노드로 들어오는 간선의 개수(노드로 오기 전의 조건)

진출차수(outdegree): 특정 노드에서 나가는 간선의 개수

 

위상 정렬 알고리즘

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌 때까지 다음의 과정 반복:

    큐에서 원소를 꺼내서 그 노드가 향하는 노드의 진입차수를 1 낮추기(그 간선 방문처리)

    진입차수가 0이 된 노드를 큐에 넣기

 

 

위상 정렬 알고리즘의 예시

1. 진입차수가 0인 노드부터 큐에 넣고 시작한다.

 

큐에서 요소를 하나 꺼낸다.

꺼내진 요소 1이 의존하고 있는 노드의 진출차수를 하나씩 낮추고, 진입차수가 0이라면 방문처리하고 큐에 넣는다.

2, 3의 진입차수가 0이 되었으므로 큐에 넣는다.

 

 

 

요소 2를 꺼내서 노드 2가 향하는 노드 4의 진입차수를 낮추고, 노드 4의 진입차수가 0이 되었으므로 방문처리하고 큐에 넣는다.

 

노드 3을 빼서 노드 3이 향하는 노드 5의 진입차수를 1 낮추고, 진입차수가 0이된 노드 5를 큐에 넣는다.

 

노드 4를 꺼내서 6의 진출차수를 1 낮춘다. 6의 진출차수가 0이 아니므로 넘어간다.

 

노드 5를 꺼내서 노드 6의 진입차수를 1 낮춘다. 노드 6의 진입차수가 0이 되었으므로 6을 큐에 넣는다.

노드 6을 큐에서 빼서, 노드 7과 8의 진입차수를 1 낮춘다.

노드 7은 진입차수가 0이 되었으므로 큐에 넣는다.

노드 8은 넘어간다.

노드 7을 빼서 노드 8의 진입차수를 1 낮춘다. 노드 8의 진입차수가 0이 되었으므로 노드 8도 큐에 넣어준다.

 

노드 8을 빼도 할 수 있는게 없다. 큐를 마친다.