[Algorithm] - Topology Sort(위상정렬)

위상정렬(Topology Sort) 란 ?

위상(Topology)이란, 노드들을 물리적으로 연결해 놓은것을 의미한다.

위상 정렬이라는것은, 위 처럼 노드들을 연결해놓은 그래프를 방향을 거스르지 않도록 나열하는 것이다.

아래 그림을 참고하자.

위상정렬을 가장 잘 설명해줄수 있는 예로 대학교의 선수과목 구조를 예로 들 수 있다.

만약, 특정 과목을 듣기위해 필요한 선수 과목이 있다면, 그 선수과목부터 수강해야 한다.

이때 위상정렬을 사용하면 올바른 강의 순서를 찾아 낼 수 있다.

 

그래프의 구조에 따라 여러개의 정렬이 나타날 수도 있다.

 

위상정렬을 사용하기 위해선 시작노드를 특정하기 위해 DAG(Directed Acyclic Graph)여야만 한다.

DAG는 사이클이 존재하지 않고, 하나의 방향만을 가지는 그래프이다.

 

위상정렬은 주로 업무의 일정이 일어나야 할 순서에 따라 배치하기위한 것 용도로 사용된다.

구현

위상 정렬의 구현은 큐(BFS)와 스택(DFS) 각각을 이용한 방식이 있다.

주로 큐를 많이 사용한다. 우선 큐를 이용한 위상정렬을 구현해보도록 하겠다.

indegree(진입차수)를 추적하기 위한 배열이 하나 필요하다.

 

구현 방식은 간단하다.

1. 진입 차수(해당 노드로 들어오는 방향인 간선의 개수) 가 0인 정점을 출력후 큐에 삽입.

2. 노드에서 나가는 간선을 모두 제거

3. 큐가 empty가 될때까지 반복

 

전체적인 흐름은 아래를 확인하면 되겠다.

한 장씩 그림을 보면서 설명하도록 하겠다.

1. 우선 진입차수가 0인 노드들을 넣어준다.

위 예제에선 1번 노드밖에 없으니 1번 노드를 큐에 넣는다.

현재까지의 큐는 [1]이다.

2. 큐에서 1번 노드를 꺼내고, 1번 노드와 연결된 노드들(2번,4번)의 간선을 제거한다.

진입차수가 0인 노드가 있는지 확인한다.

4번 노드의 진입차수가 0인것을 확인하고 큐에 넣는다.

현재 큐는 [4]이다.

3. 위와 동일하게 4번 노드와 연결된 간선(2번,5번,6번)들을 모두 제거한다.

진입차수가 0인 노드를 확인한다.

확인해봤을때, 진입차수가 0인 노드가 2개가 존재한다(2번,5번)

2번과 5번을 모두 큐에 넣는다.

현재 큐는 [2,5]이다.

4. 먼저 큐에 넣은 2번을 꺼내서 연결된 간선(3번)을 모두 제거한다.

3번 노드의 진입차수가 0인것을 확인하고 큐에 넣는다.

현재까지의 큐는 [5,3]이다.

5. 큐에서 5번 노드를 꺼내어 연결된 간선(6번)을 모두 제거한다.

6번 노드의 진입차수가 0인것을 확인하고 큐에 넣는다.

현재까지 큐는 [3,6]이다.

6. 큐의 맨앞에 있는 3번 노드를 꺼내서 확인한다.

연결된 노드가 없으므로 넘어간다.

현재까지 큐는 [6]이다.

큐의 맨앞에 있는 6번 노드를 꺼내서 확인한다.

6번 노드와 연결된 노드가 없으므로 넘어간다.

큐가 비었으므로 종료한다.

 

위와 같이 위상정렬을 구현 할 수 있다.

위의 로직을 그대로 코드로 작성하면 아래와 같다.

 

Queue를 이용한 구현 (BFS)

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

#define INPUTMAX 10

int input;
vector<int> edgeInfo[INPUTMAX],inDegree(INPUTMAX,0);

bool topologySort()
{
	queue<int> q;
    
    for(int i = 1; i <= input; i++)
    {
    	if(inDegree[i] == 0)
            q.push(i);
    }

	while(q.empty() == false)
    {
    	int front = q.front();
        q.pop();
        cout << front << " ";
        for(int i = 0; i < edgeInfo[front].size(); i++)
        {
            int edge = edgeInfo[front][i];
            if(--inDegree[edge] == 0)
                q.push(edge);
        }
    }
}


int main()
{
    input = 6;
    edgeInfo[1].push_back(4);
    inDegree[4]++;
    edgeInfo[1].push_back(2);
    inDegree[2]++;
    
    edgeInfo[2].push_back(3);
    inDegree[3]++;
    
    edgeInfo[4].push_back(2);
    inDegree[2]++;
    edgeInfo[4].push_back(5);
    inDegree[5]++;
    edgeInfo[4].push_back(6);
    inDegree[6]++;
    
    edgeInfo[5].push_back(6);
    inDegree[6]++;
    
    topologySort();
}

Stack을 이용한 위상정렬 구현 (DFS)

DFS로 쭉 순회해주면 위상정렬을 찾을수 있다.

queue를 사용한 위상정렬에서처럼 inDegree를 증가시켜주지 않아도 된다.

쭉 순회하면서 자식 노드가 없는 단말 노드에서부터 올라오기 때문에 신경써주지 않아도 된다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

#define INPUTMAX 10

int input;
stack<int> st;
vector<int> isVisited(INPUTMAX,0);
vector<int> edgeInfo[INPUTMAX];

void dfs(int curr)
{
    isVisited[curr] = true;
    for(int& iter : edgeInfo[curr])
    {
        if(isVisited[iter] == false)
        {
            dfs(iter);
        }
    }
    st.push(curr);
}

void topologySort_dfs()
{    
    for(int i = 1; i <= input; i++)
    {
        if(isVisited[i] == false)
        {
            dfs(i);
        }
    }
}

int main()
{
    input = 6;
    edgeInfo[1].push_back(4);
    edgeInfo[1].push_back(2);
    
    edgeInfo[2].push_back(3);
    
    edgeInfo[4].push_back(2);
    edgeInfo[4].push_back(5);
    edgeInfo[4].push_back(6);
    
    edgeInfo[5].push_back(6);

    topologySort_dfs();

    while(!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
}