1. 위상정렬이란?

• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미
• 예시) 선수과목을 고려한 학습순서 설정
  • 세 과목을 듣기 위해선 자료구조->알고리즘->고급알고리즘 순
    

2. 진입 차수와 진출 차수

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수
  

3. 위상 정렬 알고리즘

1) Queue를 이용

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때 까지 다음의 과정을 반복한다.
  1) 큐가 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

4. 위상정렬의 특징

• DAG에 대해서만 수행 가능
• 여러가지 답이 존재 가능
• 모든 원소를 방문 전 큐가 빈다면 사이클이 존재한다고 판단 가능

5. 소스 코드(c++)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int v,e;
int indegree[100001];
vector<int> graph[100001];

void topologySort()
{
	vector<int> result;
    queue<int> q;
    for(int i=0; i<=v; i++)
    {
    	if(indegree[i] == 0)
          q.push();
    }
    while(!q.empty())
    {
    	int current = q.front();
        q.pop();
        result.push_back(current);
        //해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for(int i=0;i<graph[current].size();i++)
        {
        	indegree[graph[current][i]] -=1;
            if(indegree[graph[current][i]] == 0)
            	q.push(graph[current][i]);
        }
    }
    for(int i=0; i<result.size(); i++)
    	cout << result[i]<<' ';
}