[알고리즘] C++로 이해하는 위상정렬

참고 : https://www.geeksforgeeks.org/topological-sorting/?ref=gcse_outind

---

☑️ C++로 이해하는 위상정렬

위상정렬(Topological Sort)은 방향 그래프에서 정점들을 선형으로 정렬하는 알고리즘이다. 풀어서 설명하면 그래프에서 순서가 있는 노드들을 순서대로 나열하는 행동을 한다. 우리가 출근을 하는 과정을 살펴보자.

1. 아침에 기상한다.
2. 씻는다.
3. 옷을 입는다.
4. 아침 식사를 한다.
5. 필요한 물건을 다 챙겼는지 확인한다.
6. 집 밖으로 나선다.

이런 과정들을 거쳐서 우리는 회사에 출근할 수 있다. 아침에 기상하는 것을 시작으로 집 밖으로 나서는 과정은 모두 순서대로 이루어진다. 아침에 기상하지 않고 식사를 하거나 집 밖으로 나설 수 없다.

 

위상정렬 알고리즘은 이처럼 명확한 순서가 있는 노드들을 정리해주는 개념을 의미한다. 순서가 있어야 하기 때문에 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서만 사용 가능하다.

 

☑️ 진입차수(In-degree)와 진출차수(Out-degree)

위상정렬을 이해하기 위해서는 진입차수와 진출차수 개념에 대한 이해가 필요하다.

진입차수(In-dregree) : 다른 노드에서 특정 노드으로 들어오는 간선의 수
진출차수(Out-degree) : 특정 노드에서 다른 노드로 나가는 간선의 수

위상정렬을 구현하는 알고리즘들은 진입차수와 진출차수를 사용해서 동작하기 때문에 이에 대한 개념은 반드시 필요하다.

 

☑️ 위상정렬의 응용 분야

위상정렬의 핵심은 '선행 작업이 먼저 완료되어야 한다'는 점이기 때문에 반복되는 작업이 없고 선행 작업 관계를 나타내기 위해서 사용할 수 있다.

1. 작업 스케줄링 : 작업 간에 선행 조건이 있다면 작업 순서를 결정하기 위해서 사용할 수 있다.
2. 패키지 의존성 관리 : 한 패키지를 설치하기 위해 다른 패키지가 필요하다면 이를 확인하는 용도로 사용할 수 있다.
3. 게임 퀘스트 진행 순서 : 게임 퀘스트 간의 의존성을 나타내고 진행 순서를 결정할 때 사용할 수 있다.
4. 데이터 처리 파이프라인 : 데이터 처리를 위해서 다른 데이터가 필요한 지 식별할 때 사용할 수 있다.

 

☑️ 위상정렬 구현하기

1️⃣ BFS 기반의 Kahn 알고리즘

📌 의사코드

1. 모든 정점의 진입차수를 계산한다.
2. 진입차수가 0인 모든 정점을 Queue에 넣는다.
3. 큐가 비어질 때 까지 아래의 순서대로 작업을 진행한다.
	3-1. 큐에서 정점을 꺼내서 Result List에 추가한다.
    3-2. 해당 정점의 진입차수를 1 감소시킨다.
    3-3. 위 작업을 통해 진입차수가 0인 정점을 Queue에 추가한다.

 

📌 C++ 코드

// Including necessary header file
#include <bits/stdc++.h>
using namespace std;

// We mainly take input graph as a set of edges. This function is
// mainly a utility function to convert the edges to an adjacency
// list
vector<vector<int>> constructadj(int V,vector<vector<int>> &edges){
    
    // Graph represented as an adjacency list
    vector<vector<int> > adj(V);

    // Constructing adjacency list
    for (auto i : edges) {
        adj[i[0]].push_back(i[1]);
    }
    
    return adj;
}

// Function to return list containing vertices in
// Topological order.
vector<int> topologicalSort(int V, vector<vector<int> >& edges)
{
    vector<vector<int>> adj = constructadj(V,edges);
    
    // Vector to store indegree of each vertex
    vector<int> indegree(V);
    for (int i = 0; i < V; i++) {
        for (auto it : adj[i]) {
            indegree[it]++;
        }
    }
    // Queue to store vertices with indegree 0
    queue<int> q;
    for (int i = 0; i < V; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    vector<int> result;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        result.push_back(node);
        
        // Decrease indegree of adjacent vertices as the
        // current node is in topological order
        for (auto it : adj[node]) {
            indegree[it]--;

            // If indegree becomes 0, push it to the queue
            if (indegree[it] == 0)
                q.push(it);
        }
    }

    // Check for cycle
    if (result.size() != V) {
        cout << "Graph contains cycle!" << endl;
        return {};
    }

    return result;
}

int main()
{

    // Number of nodes
    int V = 6;

    // Edges
    vector<vector<int> > edges
        = {{0, 1}, {1, 2}, {2, 3},
           {4, 5}, {5, 1}, {5, 2}};

    vector<int> result = topologicalSort(V, edges);

    // Displaying result
    for (auto i : result) {
        cout << i << " ";
    }

    return 0;
}

 

2️⃣ DFS 기반의 Kahn 알고리즘

📌 의사코드

1. 모든 정점에 대해서 DFS를 수행한다.
2. DFS에서 방문이 끝난 정점을 Stack에 추가한다.
3. Stack을 뒤집는다. (위상정렬 한 결과가 나온다.)

 

📌 C++ 코드

#include <bits/stdc++.h>
using namespace std;

// Function to perform DFS and topological sorting
void topologicalSortUtil(int v, vector<vector<int>> &adj, vector<bool> &visited, stack<int> &st)
{

    // Mark the current node as visited
    visited[v] = true;

    // Recur for all adjacent vertices
    for (int i : adj[v])
    {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, st);
    }

    // Push current vertex to stack which stores the result
    st.push(v);
}

vector<vector<int>> constructadj(int V, vector<vector<int>> &edges)
{

    vector<vector<int>> adj(V);
    for (auto it : edges)
    {
        adj[it[0]].push_back(it[1]);
    }

    return adj;
}

// Function to perform Topological Sort
vector<int> topologicalSort(int V, vector<vector<int>> &edges)
{

    // Stack to store the result
    stack<int> st;

    vector<bool> visited(V, false);
    vector<vector<int>> adj = constructadj(V, edges);
    // Call the recursive helper function to store
    // Topological Sort starting from all vertices one by
    // one
    for (int i = 0; i < V; i++)
    {
        if (!visited[i])
            topologicalSortUtil(i, adj, visited, st);
    }

    vector<int> ans;

    // Append contents of stack
    while (!st.empty())
    {
        ans.push_back(st.top());
        st.pop();
    }

    return ans;
}

int main()
{

    // Graph represented as an adjacency list
    int v = 6;
    vector<vector<int>> edges = {{2, 3}, {3, 1}, {4, 0}, {4, 1}, {5, 0}, {5, 2}};

    vector<int> ans = topologicalSort(v, edges);

    for (auto node : ans)
    {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}