Topological Sort(위상 정렬)

위상정렬(Topological Sort)이란?

위상 정렬에서 한 정점에서 나가는 간선을 지나기 위해서는 ==그 정점으로 들어오는 모든 간선을 지나야 한다==고 했다.

따라서, 위상 정렬은 다음과 같이 동작한다.

① 최초 그래프에서 진입 차수가 0인 정점들을 모두 큐(Queue)에 넣는다.

② 큐에서 한 정점을 꺼낸다.

③ 그 정점과 연결된 모든 정점에 대해 진입 차수를 1 뺀다.

④ 이 때 그 정점의 진입 차수가 0이 됐다면, 그 정점을 큐에 넣는다. (즉, 진입 차수가 0인 정점만 큐에 들어갈 수 있다.)

⑤ ② ~ ④를 큐가 빌 때까지 반복한다.

![[%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA2023-08-31%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE_1.23.21.png]]

주의사항

1. 그래프 내에 사이클이 존재하면 위상정렬을 적용할 수 없다.
2. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 것이다.

코드

void topological_sort() {
    queue<int> que;
    //최초 그래프에서 진입 차수가 0인 정점을 삽입
    for (int i = 1; i <= 7; i++)
        if (indegree[i] == 0) que.push(i);
 
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
 
        printf("%d ", cur);
 
        //큐에서 꺼낸 정점과 연결된 모든 정점에 대해
        for (int i = 0; i < adj[cur].size(); i++) {
            int nextnode = adj[cur][i];
            //그 노드의 진입차수를 1 감소
            indegree[nextnode]--;
 
            //만약 그 노드의 진입차수가 0이 되었다면, 조건을 모두 만족했으므로 나아갈 수 있음
            //따라서 큐에 삽입한다.
            if (indegree[nextnode] == 0) que.push(nextnode);
        }
    }
}

위상정렬을 응용한 문제

위상정렬은 어떠한 Task들 간의 먼저 이행되어야 하는 순서가 존재할 때, 이를 올바른 순서로 진행하기 위ㅏ해 사용된다.

따라서 알고리즘 문제에 응용될때, 선행 관계 등이 제시될 경우 위상정렬 문제로 접근할 수 있다.

참고

https://4legs-study.tistory.com/89?category=886581