DAG(Directed Acyclic Graph) = 사이클이 없는 방향 그래프.

DAG에서 선형 순서를 정렬.

예를 들면, 대학생 졸업 요건을 갖추기 위해 각 과목이 있고 선수 과목이 있다.
선수 과목을 들어야 다음 과목을 들을 수 있다.
이러한 선수 관계를 위상 정렬하면 들어야할 과목 순서를 정할 수 있다.

이론

정리 - 방향 그래프가 비순환이면, dfs는 역행 간선을 만들지 않고 그 역도 성립한다.

소스 코드

vector<int> ts; // 위상 정렬을 역순으로 저장하기 위한 변수

void dfs(int u){
    dfs_num[u] = VISITED;
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if (dfs_num[v] == UNVISITED)
            dfs(v);
    }
    ts.push_back(u); // 기존 dfs에서 이 부분만 추가하면 됨. 방문이 끝나면서 하나씩 담음
}

칸 알고리즘

BFS를 응용함.
DFS기반 알고리즘으로 풀지 못할 경우도 있다.
그럴때 사용하면 된다.

소스 코드

// 진입 차수가 0인 정점들을 우선순위 큐에 삽입
while(!q.empty()){
    int u = q.dequeue();
    ts.push_back(u);    // 정점 u를 위상 정렬 목록에 추가
    
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        in_edge[v]--;   // 정점 u에 모든 진출 간선을 제거
        if (in_edge[v] == 0) // 제거 하면서 u에 연결된 정점 v가 진입 차수가 0이 되면,
            q.enqueue(v);
    }
}