기술면접 알고리즘 [Graph] : 위상정렬 (Topological Sort)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

위상정렬 (Topological Sort)

위상정렬은 유향 그래프 (DAG, Directed Acyclic Graph) 에서 선후관계를 고려한 정렬 방식이다. 즉, A -> B 의 관계가 있다고 했을때, 위상정렬을 하면 반드시 A 가 B 보다 먼저 출력된다.

위상정렬을 하기 위해서는 Incoming Edge 의 값이 0 인 녀석들부터 순서대로 추출하여 출력하면 된다. 특정 Vertex 를 추출하면 해당 Vertex 가 가리키는 Vertex 의 Incoming Edge 가 줄어는데, 만약 0 이 된 경우 해당 Vertex 를 stack 이나 queue 에 저장하여 위의 작업을 반복하면 된다.

시간복잡도는 E(각 정점에 대한 Incoming Edge 계산) + V(각 정점을 순회하며 출력) 만큼의 비용이 든다.

따라서 O(E+ V) 의 시간 복잡도를 가진다.

#include <iostream>
#include <map>
#include <stack>
#include <vector>

class Graph {

int V;
std::map<int, std::vector<int>> edge;

public:

    void addEdge(int i, int j) {
        edge[i].push_back(j);
    }

    void topologicalSort() {

        // Calculate Incoming Edges
        int income[V] = {0};

        for (auto e : edge) {
            for (auto end : e.second)
                ++income[end];
        }

        std::stack<int> s;
        for (int i = 0; i < V; ++i) {
            if (income[i] == 0)
                s.push(i);
        }

        int cur;
        while (!s.empty()) {
            cur = s.top();
            s.pop();
            std::cout << cur << " ";
            for (int end : edge[cur]) {
                if (--income[end] == 0) {
                    s.push(end);
                }
            }
        }
        std::cout << std::endl;
    }

    Graph(int v) : V(v) {}
};


// Driver Code
int main()
{
    // Create a graph given in the above diagram
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
 
    std::cout << "Following is a Topological Sort of the given "
            "graph \n";
 
    // Function Call
    g.topologicalSort();
 
    return 0;
}