모든 사진 자료에 관한 출처는 아래 알튜비튜 - 튜터링에 있음을 밝힙니다.
https://github.com/Altu-Bitu/Notice

그래프 용어 복습

• Indegree(진입차수) : 방향 그래프에서 해당 정점으로 들어오는 간선의 수
• Outdegree(진출 차수) : 방향 그래프에서 해당 정점에서 나가는 간선의 수

위상정렬

• 그래프의 선후 관계를 지키며 모든 정점을 일렬로 나열하는 알고리즘
• 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 작업의 순서를 결정함.
• 위상 정렬의 결과는 여러가지가 가능
• 사이클이 없는 방향 그래프 (DAG)에서 사용
• 일상 생활에서는 보통 스케쥴을 짤 때 많이 쓰임

Q. 만약 사이클이 존재한다면?

• 진입차수가 0인 정점이 존재하지 않음
• 다른 연결된 정점이 있다 해도, 사이클 내의 정점은 진입차수가 0이 절대 될 수 없음.
• 따라서 위상정렬 불가능!

과정

1. 진입차수가 0인 정점을 찾아서 나열
2. 1에서 찾은 정점과 그 정점으로부터 나오는 간선을 그래프에서 삭제
3. 1-2 과정을 반복
4. 그래프가 모두 삭제되면 종료

구현

• 각 정점마다 Indegree를 저장할 배열을 만듦.
• 진입차수가 0인 정점이 여러개 일수 있으므로, 이를 저장해 둘 큐(queue) 필요

1. 진입차수가 0인 정점을 찾아서 컨테이너에 저장(큐에 푸시)
2. 1에서 찾은 정점과 연결된 정점의 진입차수를 1씩 감소
3. 1-2 과정을 반복
4. 모든 정점이 선택되었다면 종료

...중략

위상 정렬과 DFS

• DAG(사이클이 없는 그래프)에서 DFS를 실행하면서 한 정점의 탐색이 끝났을때를 저장하면, 이 순서의 역순이 위상 정렬한 결과와 같음.
• DFS가 끝났다는 것은 더 이상 깊게 파고들 정점이 없다는 것을 의미하기 때문
• 스택을 이용하여 DFS가 끝나고 리턴시 현재 정점을 삽입해줌(DFS를 다시 시작하기 전까지)
• 증명은 수학적 귀류법을 사용

void dfs(int node){
if(visited[node]) //이미 방문한 정점이라면
return;

visited[node]=true; //방문 체크

for(int i=0; i< graph[node].size();i++)
dfs(graph[node][i]);

st.push(node); //더이상 탐색할 정점이 없다면 현재 정점 삽입

코드

//위상정렬
vector<int> topologicalSort(int n, vector<int>& indegree, vector<vector<int>>& graph) {
    vector<int> result;
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (!indegree[i]) //진입차수가 0이라면
            q.push(i); // 큐에 푸시
    }

    // 큐에 존재하는 정점들을 하나씩 꺼내어 연결을 끊으면서 진입차수가 0인 된 점들을 큐에 푸시함

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        result.push_back(node); //현재 정점 순서에 삽입
        for (int i = 0; i < graph[node].size(); i++) {
            int next_node = graph[node][i]; // node와 연결된 정점들 
            indegree[next_node]--; //연결된 정점의 진입차수를 1씩 감소
            if (!indegree[next_node]) //연결된 정점의 진입차수가 0이 되었다면
                q.push(next_node);
        }
    }
    return result;
}

✨마무리

• 일상 속에서 일의 순서를 정해야할 때 사용하는 위상 정렬
• 그래프의 선후 관계가 주어졌을 때, 모든 정점을 차례로 나열함.
• 선후 관계가 존재하는 정점들만 지키면 되기 때문에, 여러가지 결과가 나올 수 있음.
• 사이클이 존재하면 위상 정렬을 할 수 없음
• 진입차수를 저장한 배열과, 진입차수가 0인 정점을 관리할 큐를 사용하여 구현
• DFS를 활용해서도 구현 가능