위상 정렬(Topological sort)

위상정렬이란?

위상정렬은 작업의 순서를 정해주는 알고리즘입니다. 어떤 일을 진행시키기 위해 순서가 정해져 있는 경우에 사용할 수 있습니다. 예를들어, 선수과목을 생각해보면 이해하기 쉬운것 같습니다.

 

순서가 있다는 말은 그 관계에서 방향성이 있다는 것 입니다. 위상정렬은 DAG(Directed Acyclic Graph)로써 사이클이 발생하지 않는 방향 그래프의 성질을 가지고 있습니다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없습니다.

 

구현 방법

queue를 이용한 구현 방법이 일반적이라고 합니다.

 

Queue를 이용한 구현

1. in degree가 0인 노드를 queue에 삽입

2. queue에 있는 관련 노드의 간선 삭제

3. in degree 업데이트 (1~3 반복)

4. 종료 후 모든 노드 탐색했는디 check

 

Time Complexity

인접 리스트 : O(V+E)

인접 행렬 : O(V^2)

 

Stack를 이용한 구현

모든 정점을 순회하며 방문하지 않은 정점에 대해서 재귀순환

1. 연결된 edge를 인접리스트에 추가한다.

2. 모든 정점을 기점으로 순회하지 않는 edge를 순회

3. visited를 표시하면서 다음 노드로 재귀

4. 모든 노드를 방문하고 list(방문순서 기록) 에 현재 노드 추가

Time Complexity

인접 리스트 : O(V+E)

인접 행렬 : O(V^2)

관련문제

Course Schedule

 

1. Queue

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses, vector<int>());
        vector<int> degree(numCourses, 0);
        for(auto& v : prerequisites)
        {
            adj[v[1]].push_back(v[0]);
            degree[v[0]]++;
        }
        
        queue<int> q;
        for(int i = 0; i < numCourses; i++)
        {
            if(degree[i] == 0) q.push(i);
        }
        
        vector<int> visited;
        while(!q.empty())
        {
            int e = q.front(); q.pop();
            for(auto& ad : adj[e])
            {
                if(--degree[ad] == 0) q.push(ad);
            }
            visited.push_back(e);
        }
        
        return visited.size() == numCourses;
    }
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses, vector<int>());
        vector<int> degree(numCourses, 0), visited;
        for(auto& v : prerequisites)
        {
            adj[v[1]].push_back(v[0]);
            degree[v[0]]++;
        }
        
        for(int i = 0; i < numCourses; i++)
        {
            if(degree[i] == 0) visited.push_back(i);
        }
        
        for(int i = 0; i < visited.size(); i++)
        {
            for(auto& ad : adj[visited[i]])
            {
                if(--degree[ad] == 0) visited.push_back(ad);
            }
        }
        
        return visited.size() == numCourses;
    }
};

2. Stack

class Solution {
private:
    bool dfs(vector<vector<int>>& adj, vector<int>& takenOrder, vector<int>& visited, set<int>& cycle, int key)
    {
        if(cycle.count(key) > 0) return false;
        if(visited[key]) return true;
        
        cycle.insert(key);
        
        for(int i = 0 ; i < adj[key].size(); i++)
        {
            if(!dfs(adj, takenOrder, visited, cycle, adj[key][i])) return false;
        }
        
        cycle.erase(key);
        visited[key] = true;
        takenOrder.push_back(key);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> takenOrder;
        
        for(auto& v : prerequisites)
            adj[v[0]].push_back(v[1]);
        
        vector<int>visited(numCourses, false);
        set<int> cycle;
        for(int i = 0; i < numCourses; i++)
        {
            if(!dfs(adj, takenOrder, visited, cycle, i)) return {};
        }
        
        return takenOrder;
        
    }
};