C++] 위상정렬 구현 및 설명

위상정렬은 각 노드들의 간선 개수를 구한 후 간선개수가 가장 적은 요소부터 순회하는 알고리즘입니다. 

 

여기서 간선 개수란 각 노드마다 연결된 개수를 의미합니다.

 

간선 개수가 적은 요소들을 순회하기 때문에 한번에 원하는 지점까지 못가게 되는 특징이 있습니다.

 

위상정렬을 이용한 예제들은 주로 '게임 스킬트리, 우선순위에 대한 시간 문제 등...' 다양하게 사용되고 있습니다.

 

아래 그림을 통해 코드를 구현해 보겠습니다.

 

 

 

여기서 만약 A에서 E로 간다고 가정한다면 A는 B나 C를 거치고 D를 거처서 E로 가거나 혹은 D에서 F를 거처 E로 가게 됩니다.

즉, 노드 간선을 기점으로 모든 노드를 순서대로 거처가는걸 알 수 있습니다. 이 간선을 거처가는것이 하나의 조건이 될 수 있습니다.

 

아래는 구현 코드 입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>

int indegree[6] = { 0, };

using namespace std;

enum { A, B, C, D ,E, F };

void AddGraph(vector<int> * v, int x, int y) {
    v[x].push_back(y);
    indegree[y]++;
}

void ShowGraphLine(vector<int> * v) {
    for (int i = 0; i <= F; i++) {
        printf("%c와 연결된 정점 : ", i + 65);
        for_each(v[i].begin(), v[i].end(), [&](auto& s) {
            printf("%c ", s + 65);
            });
        cout << endl;
    }
}

void ShowGraphDFS(vector<int> * v) {
    queue<int> q;

    for (int i = 0; i < F; i++) {
        if (indegree[i] == 0)
            q.push(i);
    }

    while (!q.empty()) {
        int num = q.front();
        q.pop();
        printf("%c ", num + 65);
        for (int i = 0; i < v[num].size(); i++) {
            if (--indegree[v[num][i]] == 0)
                q.push(v[num][i]);

        
        }
    }
}

int main(void) {

    vector<int> g[6];

    AddGraph(g, A, B);
    AddGraph(g, A, C);
    AddGraph(g, B, D);
    AddGraph(g, C, D);
    AddGraph(g, D, E);
    AddGraph(g, D, F);
    AddGraph(g, F, E);

    ShowGraphLine(g);
    ShowGraphDFS(g);

    return 0;
}
​

 

 

 

 

 

 

 

 

 

 

 

 

이 코드는 깊이우선탐색입니다.

 

여기서 queue에 넣었다가 나온 요소들을 출력해주면 탐색한 모든 요소들을 확인할 수 있습니다.

 

또한 코드에선 indegree[] 배열을 직접 갔다가 사용했지만 재사용 하려면 해당 배열을 복사해서 사용하면 됩니다.

 

감사합니다.!!