위상 정렬 알고리즘 (Topology Sort)

위상 정렬 알고리즘 : 순서가 정해져 있는 작업을 순차적으로 탐색하는 알고리즘

위와 같은 그래프가 주어졌을 때 화살표는 작업의 순서를 나타낸다.

ex) 1이 끝나면 3을 시작할 수 있다.

ex) 2와 3이 끝나면 5를 시작할 수 있다.

<위상정렬 알고리즘>

단순하게 자신으로 들어오는 indegree가 모두 제거되면 자신의 일을 시작하면 된다.

<전체 코드>

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
vector<int> a[10];
int indegree[10];
int n = 7;
 
void topology()
{
    queue <int> q;
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)q.push(i); // 자신 전에 선행되어야 할 일이없다면 큐에 저장
    }
 
    for (int i = 0; i < n; i++)
    {
        if (q.empty())  //n개 모두 탐색하기 전에 탐색이 끝나면 사이클 존재.
        {
            cout << "사이클이 발생하였습니다." << "\n";
            return;
        }
 
        int node = q.front();
        q.pop();
 
        cout << node << " ";
        for (int i = 0; i < a[node].size(); i++)
        {
            int next = a[node][i];
            indegree[next]--;
            if (indegree[next] == 0)q.push(next);
        }
    }
}
 
int main()
{
    a[1].push_back(2);  //노드 1에서 노드 2로가는 길
    indegree[2]++;   //노드 2의 indegree 증가
    a[1].push_back(3);
    indegree[3]++;
    a[1].push_back(4);
    indegree[4]++;
    a[2].push_back(5);
    indegree[5]++;
    a[3].push_back(5);
    indegree[5]++;
    a[3].push_back(6);
    indegree[6]++;
    a[5].push_back(7);
    indegree[7]++;
    a[6].push_back(2);
    indegree[2]++;
 
    cout << " 탐색 순서 : ";
    topology();
 
    return 0;
}