알고리즘 공부[3] Topological sort(위상정렬) (C++)

안녕하세요. 오늘은 그래프를 활용한 문제에서 등장하는 위상정렬에 대해서 알아보겠습니다.

Contents

DAG(Directed Acyclic graph)

Topological sort란?

위상정렬의 구현방식(1)-indegree

위상정렬의 구현방식(2)-DFS

DAG(Directed Acyclic Graph)

---

우선 위상정렬을 공부하기 전에 DAG에 대해서 알아봅시다. 

Directed Acyclic graph란 말 그대로 간선에 방향이 있고, 싸이클이 없는 그래프를 말합니다.

Directed Graph에서 방향을 가지고 있는 간선들의 sequence에 대해 

시작점과 끝점이 같아지는 sequence가 있다면 싸이클이 있다고 합니다. 

DAG는 이런 싸이클이 없는 유향그래프이죠.

이전의 그래프의 정의와 함께 말씀드렸듯 DAG는 노드간의 의존성을 나타내며, 

작업 간의 순서를 표현하는데 많이 사용됩니다.

아래와 같은 그래프가 바로 DAG이죠.

Topological sort란?

---

Topological sort, 위상정렬이란 DAG에서 의존성에 맞게 그래프의 정점을 정렬하는 것을 말합니다.

다시 말하면 DAG에서 간선의 방향이 모두 한 방향으로 흘러가게 정점들을 정렬하는 것을 말합니다.

간선의 방향이 모두 한 방향으로 흘러가게, 방향성을 거스르는 간선이 없게 정렬을 하기 위해서는 싸이클이 없어야 합니다.

(만약 싸이클이 있다면 방향성을 일정하게 할 수가 없게 되겠죠!)

그래서 DAG가 위상정렬을 하기위한 필요조건이 되는 것이죠.

위의 예시로 본 DAG를 가지고 위상정렬을 하게되면 아래와 같이 됩니다.

위상정렬은 간선의 방향성만 모두 같으면 되므로 정렬 결과는 여러가지가 나올 수 있습니다.

위상정렬의 구현방식(1)-indegree

---

그렇다면 위상정렬을 주어진 DAG를 가지고 어떻게 하면 될까요?

우선 직관적으로 생각하면, DAG에서 자신으로 들어오는 점을 먼저 찾아서 앞에 넣어야 할 것 같습니다.

그 점으로부터 간선을 따라가면 될 것 같다는 느낌이 오실겁니다. (위에서는 (i)번 노드를 먼저 찾는 것이죠.)

이런 직관을 바탕으로 생각을 해보면 다음과 같습니다.

1. 자기 자신으로 들어오는 간선이 없는 정점을 모두 찾아서 저장한다.

2. 1에서 찾는 정점과 그 정점으로 부터 나오는 간선을 그래프에서 삭제한다.

3. 1-2번의 과정을 계속 반복한다.

4. 그래프가 모두 삭제되면 종료한다.

이 때 각 정점으로 들어오는 간선의 수를 indegree라고 합니다.

위와 같은 방식으로 위상정렬을 할 경우 예시를 보여드리겠습니다.

이제 아 위상정렬은 이렇게 하면 되는구나! 라고 생각하셨을 겁니다.

자 그렇다면 코드는 어떻게 작성할까요? indegree를 사용한 방식으로 위상정렬을 할 경우 어떻게 구현하면 될까요?

구현 포인트는 다음과 같습니다.

1) indegree를 업데이트 하면서 indegree가 0인 정점을  찾는다.

2) queue를 사용해서 하나씩 저장후 나중에 출력

구현하는 방식은 많지만 제가 위를 바탕으로 구현한 코드는 아래와 같습니다.

#include<iostream>
#include<vector>
#include<queue>
#define VERTEX_NUM 100
using namespace std;
 
vector< vector<int> > adj(VERTEX_NUM+1, vector<int>());
/* 
주어지는 그래프의 정점의 갯수가 VERTEX_NUM이고
N개의 그래프 정보가 입력으로 주어진다고 가정하고,
u->v일 경우 입력이 "u v"로 N가지가 주어진다고 생각해봅시다.
*/
void topological_sort(queue<int>& answer, vector<int>& indegree) {
    while(answer.size()!=VERTEX_NUM) {
        /* indegree=0인 정점을 찾습니다. */
        for (int i = 1; i < adj.size(); i++) {
            if (indegree[i] == 0) {
                indegree[i] = -1;    //삭제와 같은 역할을 합니다.
                answer.push(i);        //큐에 넣습니다.
                for (auto& v : adj[i]) {
                    //정점과 인접한 정점에 대해 indegree 업데이트
                    indegree[v]--;
                }
            }
        }
    }
}
 
int main() {
    int N;
    vector<int> indegree(VERTEX_NUM + 1, 0);
    queue<int> answer;
    /* N가지의 그래프 정보를 담습니다.
    그래프 정보를 받으면서 할 일은 1) adj를 채우고,
    2) indegree를 업데이트 합니다. */
    while (N--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);        //adj에 인접리스트 담기
        indegree[v]++;              //indegree 업데이트
    }
 
    topological_sort(answer, indegree);
 
    cout << "ANSWER : ";
    while(!answer.empty()){
        cout << answer.front() << " ";
        answer.pop();
    }
    cout << '\n';
}

위상정렬의 구현방식(2)-DFS

---

사실 위상정렬은 더 간단하게 생각하면 DFS로도 정렬된 결과를 구할 수 있습니다.

DFS의 작동방식을 생각해보면 DAG에서 한 정점으로부터 depth를 우선적으로 탐색하게 됩니다.

그렇다면 DFS가 재귀적으로 구현이 되어있을때, 각 재귀적으로 호출된 DFS가 종료되는 시점을 생각해봅시다.

종료되는 시점에서 해당 정점과 연결된 정점들에 대해 모든 depth를 보았을 때 종료를 하게 됩니다. (간선이 없거나 이미 방문한 경우)

그러니 잘 생각해 보면 DFS를 종료할 때 출력을 해주면 topological sort한 결과의 역순으로 출력을 하게 됩니다!

그렇다면 DFS를 구현한 후 종료시에 stack에 담에서 pop해주면 위상정렬된 결과를 얻을 수 있겠죠!

이러한 사실은 귀류법으로 간단하게 증명이 됩니다.

밑에 적어놓은 증명을 읽어 보시면 DFS종료시 출력한 역순이 위상정렬된 결과라는 것에 대해 확신을 가질 수 있을 것입니다.

---

이번 글에서는 위상정렬에 대해 알아보았습니다.

질문이 있으시거나, 잘못된 내용을 발견하시면 댓글 남겨주시면 답변드리겠습니다.