위상 정렬(Topology Sort)

1. 위상 정렬이란?

유향 그래프(방향이 존재하는 그래프)의 노드를 방향에 거스르지 않도록 나열하는 것을 의미한다.

2. 진행 방식

시작하기에 앞서 그래프이 '진입 차수'라는 개념에 대해 알아야한다. 특정 노드에 대하여 간선이 자신에게로 향하는 간선을 진입 간선, 자신으로 부터 간선이 출발하는 간선을 진출 간선이라 한다. 진입 차수는 진입 간선의 개수로, 반대로 진출 차수는 진출 간선의 개수라 보면 되겠다.

진입 차수라는 개념을 통해 위상정렬을 진행할 수 있다. 위상 정렬을 실행할 때 제일 먼저 위치하게 될 노드는 진입 차수가 0인 노드이기 때문이다(진입 차수가 0인 노드가 여러 개라면 임의의 한 노드를 골라서 시작한다).
아래와 같은 그래프를 위상 정렬 해보자. 진입 차수가 0인 노드는 1번과 3번 노드이며 임의로 1번 노드서 부터 정렬을 시작한다 하자.

진행 과정
매 단계마다 그래프의 진입 차수를 기록한다. 진입 차수가 0인 노드가 현재 노드가 되며, 현재 노드 및 현재 노드와 연결된 간선을 같이 지운다. 지웠을 때 진입 차수의 값이 0이라면 다음 차례가 된다(후보가 여러 개라면 임의로 하나 설정). 더 이상 진행할 노드가 없을 때 까지 위 과정을 반복한다.

위상 정렬 시작
진입 차수가 0인 1,3번 중 1번 노드를 현재 노드로 설정한다. 아래 그림과 같이 1번 노드는 2번,4번 노드와 연결되어 있다.

• 현재 노드: 1번
• 연결 노드: 2번,4번
  
  1번 노드를 지우면서 2,4번으로 가는 간선을 같이 지우게 되면 아래와 같이 그래프가 변경되며 2번,4번 노드의 진입 차수가 1개씩 줄어든 것을 확인할 수 있다. 진입 차수가 0인 노드는 3 뿐이므로 3번 노드가 현재 노드가 된다.

---

• 현재 노드: 3번
• 연결 노드: 2번
  
  3번 노드와 해당 간선을 같이 지우면 아래 그림와 같다. 2번의 진입 차수가 0이 되었으므로 다음 노드가 되겠다

---

• 현재 노드: 2번
• 연결 노드: 4번,5번
  
  2번 노드와 연결 간선을 지우자.

---

• 현재 노드: 4번
• 연결 노드: 5번
  

---

• 현재 노드: 5번
• 연결 노드: 없음
  

---

다음으로 향할 간선이 없으므로 종료한다.

3. 코드

vector<int> topologySort(){
    vector<int> answer;
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(degree[i]==0)
            q.push(i);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        answer.push_back(now);
        for(int i=0;i<adj[now].size();i++){
            int next=adj[now][i];
            degree[next]--;
            if(degree[next]==0)
                q.push(next);
        }
    }
    return answer;
}

4. 시간 복잡도

모든 노드와 간선을 순회한다.
O(V+E)

5. 참고 자료

알고리즘 문제해결 전략(종만북)