그래프 알고리즘 - (6) 위상 정렬 Topological sort

이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.

 

1. DAG란?

Definition

 DAG는 directed acyclic graph이다. cycle이 없는 directed graph라는 말이다.

 

 

Property

 DAG는 적어도 하나의 sink와 하나의 source가 있다. sink는 나가는 edge가 없는 vertex, source는 들어오는 edge가 없는 vertex이다.

 cycle이 없다 -> source가 있다, 이며 source가 없다 -> cycle이 있다, 라는 말이 된다.

 

 

 

2. 위상정렬 Topological Sort

Definition

 모든 directed edge (u, v)에 대해 u가 항상 v보다 더 빨리 오게 vertex를 정렬하는 방식이다.

 DAG는 한 쪽 방향의 edge만 존재하도록 vertex를 정렬하는 linearlize가 가능하다. 아래 왼쪽 graph를 topological sort하면 오른쪽과 같이 바뀐다.

 

 

DFS로 구현 : O(|V| + |E|)

 DFS의 특성을 생각해 보았을 때 DFS가 종료되는 시점을 생각해 보자. DFS가 종료되는 시점은 '더 이상 탐색할 수 있는 vertex가 없을 때'... 즉 sink node일 때이다. 그러면 DFS가 종료되었을 때 vertex를 바로바로 vector에 push_back한다면 topological sort의 역순이 될 것이다. 그렇다면 stack에 push하고 모든 DFS가 종료되었을 때 stack에서 pop해온다면 그것이 topological sort한 결과물이 될 것이다.

 다만 DFS로 구현한다면 cycle이 있는지 검사하기가 힘들기 때문에 DFS 구현보다는 queue를 이용한 구현을 외워두는 게 더 좋을 것 같다.

 시간복잡도의 경우 DFS이므로 O(V + E)이다.

void DFS(int cur_node, vector<vector<int>>& edges, vector<bool>& visited, stack<int>&s){
    visited[cur_node] = true;
    
    for(int adjacent : edges[cur_node]){
        if(visited[adjacent] == false) {
            DFS(adjacent, edges, visited, s);    
        }
    }
    // DFS가 끝나면 cur_node를 stack에 push
    s.push(cur_node);
}

// edges[i] : vertex i와 연결된 edge list
void topological_sort(vector<vector<int>>& edges){
    vector<bool> visited(V.size(), false);
    stack<int> tsort_result;

    // 모든 unvisited vertex에 대해 DFS
    for(int i = 0; i < V.size(); i++){
        if(!visited[i]) DFS(i, edges, visited, tsort_result);  
    } 

    // DFS 탐색 끝나면 stack pop
    while(!tsort_result.empty()){
        cout<<tsort_result.top()<<endl;
        tsort_result.pop();
    }
}

 

 

source, sink vertex로 구현 : O(|V| + |E|)

 이 구현 방식은 간단하다.  source를 찾고, sourve vertex와 source와 이어진 모든 edge를 graph에서 삭제한다.

• source를 찾고 모든 source를 queue에 넣는다.
• q의 front()와 해당 vertex와 연결된 모든 edge를 graph에서 삭제한다.
  
  • 이 단계에서 edge를 graph에서 지우고, vertex와 연결된 edge를 구하는 것은 시간낭비이다. 그럴 필요 없고 모든 vertex에 대해 incoming edge 개수를 구하고 갱신할 때 -1 해주면 된다.
• graph가 빌 때 까지 반복한다.
• 만약, 끝나기 전 까지 queue size가 0이라면 cycle이 있는 것이고(source가 없는 경우), queue size가 1보다 크다면 결과가 2개 이상이라는 것이다.

 시간복잡도의 경우 모든 vertex와 edge를 1번씩 방문하므로 O(V+E)이다.

// edges[i] : vertex i와 연결된 edge list
// num_incoming_edge[i] : vertex i로 들어오는 edge 개수
void topological_sort(vector<vector<int>>& edges, vector<int>& num_incoming_edge){
    queue<int> q;
    for(int i = 0; i <= V.size(); i++){ // 모든 vertex에 대해 incoming edge가 0인 것은 q에 push
        if(num_incoming_edge[i] == 0) q.push(i);
    }
    
    bool isCycle = false;
    vector<int> result;
    for(int i = 0; i <= V.size(); i++){
        if(q.empty()){
            isCycle = true;
            break;
        }
        
        int front = q.front(); q.pop();
        result.push_back(front);
        for(int adjacent : edges[front]){
            num_incoming_edge[adjacent]--;
            if(num_incoming_edge[adjacent] == 0) q.push(adjacent);
        }
    }

    if(isCycle){
        cout<<"this graph includes cycle!"<<endl;
        return;
    }
    else{
        for(int i = 0; i<result.size(); i++){
            cout<<result[i]<<endl;
        }
    }
    return;
}