[알고리즘] kahn (위상정렬)

부분적인 순서관계만 있는 상황에서 
주어진 조건들을 만족시키도록 정렬하는 방법을 위상정렬이라고 한다.
(그래프의 방향성에 거스르지 않도록 순서대로 배열(정렬)하는 방법을 찾는 알고리즘)
 
"부분적인 순서관계" == 방향 그래프 내 간선으로 표현
"주어진 조건들을 만족시키도록 정렬" == kahn 알고리즘(위상정렬 알고리즘)으로 해결
 

---

[ 위상정렬의 전제조건 ]

 
1) 방향 그래프

2) 사이클이 없다

 

이 두 조건을 만족해야한다.

DAG(Directed Acyclic Graph) 라고 하는데 이것에 대한 반례는 두 가지가 있다.
 
[1. 그냥 대놓고 사이클인 경우]

이 경우는 진입차수가 0인 노드가 하나도 없으므로 맨 초기 queue.empty()에서 바로 걸러진다.

즉, 알고리즘의 시작은 진입차수가 0인 시작점을 기준으로 돌아가므로 이런 경우에는 시작 자체를 할 수 가 없다.
 
[2. 사이클인걸 모르는데 알고리즘 돌리다 보니 사이클임을 알게되는 경우]

 
이 경우에는 맨 처음에는 알고리즘을 돌릴 수 있다.
A의 진입차수가 0이므로 초기에 queue가 차있기 때문이다(A 한개 들어가 있는거임). 

하지만 A노드와 A의 간선을 제거한 이후에는 cycle graph 이기 때문에 위상정렬이 불가능하다.
이런 경우가 돌리다가 걸러지는 경우이다.

---

[ kahn algorithm ]

int inDegree[SIZE];

void solve() {

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

 
위상정렬 문제를 푸는데 사용되는 그래프 개념이 진입차수(inDegree)이다.
알고리즘을 수행하면서 특정노드와 해당 노드의 간선들을 제거하는 작업이 동반되는데 
이때 간선을 제거하는 작업을 해당 노드와 이어진 노드들의 진입차수-1로 해결하기 때문이다.
(그래서 돌리기 전에 간선을 그래프에 반영하면서 indegree 배열을 선언하고 업데이트해줘야한다)

1. 진입차수가 0인 노드를 queue에 넣기
2. N개의 정점에 대해 다음 과정을 반복
	1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다(연결된 노드의 진입차수 - 1)
	2. 업데이트된 진입차수가 0이면 queue에 넣어준다

 
맨 위에 나온 gif에서 cannot make vertex N blue yet은 해당 진입차수 -1을 했는데 아직 0이 안되서 그런 것이다.
즉, 다른 노드의 진입간선을 가지고 있다는 뜻(아직 0이 아니니)이므로 queue에 추가할 수 없는 것이다.

 

---

[왜 N번 반복하면 충분한가?]

void solve()
{
    queue<int> q;

    // 진입차수 0인거 넣어주기
    for (int i = 1; i <= N; i++)
    {
        if(inDegree[i]==0) q.push(i);
    }

    int cur, next;
    for (int i = 0; i < N; i++)
    {
    	// 돌리는 과정에서 큐가 비어있다는 것은 사이클이 존재한다는 것
        if(q.empty()){
            cout << "cycle!";
            return;
        }

        cur = q.front();
        q.pop();

        for (int k = 0; k < graph[cur].size(); k++){
            next = graph[cur][k];

            inDegree[next]--;
            if(inDegree[next]==0){
                q.push(next);
            }
        }
    }

    return;
}

 

DAG에서는 모든 노드를 한번씩 방문하며 정렬해야하기 때문이다.

이때 N번의 반복을 통해 모든 노드를 방문하는 것이 보장되는데, 만약 사이클이 존재한다면 queue가 비어버려서 모든 노드를 방문하지 못하고 중간에 종료되기 때문이다.

 

1. 위상정렬은 모든 노드를 한 번씩 방문하면서 정렬하는 과정이다.
2. 매번 q.front()에서 노드를 꺼내고, 해당 노드와 연결된 간선을 제거하면서 진입 차수를 감소시킨다.
3. 이런 과정으로 총 N개의 노드를 방문해야 하므로, N번만 반복하면 모든 노드를 방문할 수 있다.
4. 하지만 만약 그래프에 사이클이 있다면, 일부 노드는 진입 차수가 0이 되지 않으므로 queue에 들어가지 못하고, queue.empty()가 되어 "cycle!"을 출력한 후 종료된다.

즉, 정상적인 DAG라면 N번의 반복을 돌면서 모든 노드를 방문할 수 있지만,

사이클이 있으면 queue가 비는 상황이 발생하면서 조기에 종료될 수 있는 것이다!

 

---

[while(!q.empty())를 사용한 코드]

void solve() {
	queue<int> q;

	// 진입차수 0인거는 queue에 넣어주기
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	int count = 0;  // 방문한 노드 개수

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		cout << cur << " ";
		count++;  // 방문한 노드 개수 증가

		// cur노드의 간선을 모두 삭제
		for (int end : graph[cur]) {
			inDegree[end]--;
			if (inDegree[end] == 0) q.push(end);
		}
	}

	// 만약 count가 N보다 작다면, 사이클 존재
	if (count < N) {
		cout << "cycle!";
	}
}

 

---

// 필요한 자료구조
int inDegree[SIZE];
vector<vector<int>> graph(SIZE);

void solve() {
    queue<int> q;
}

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

#define SIZE 1001

using namespace std;


int N;
int inDegree[SIZE];
vector<vector<int>> graph(SIZE);

void solve()
{
    queue<int> q;

    // 진입차수 0인거는 queue에 넣어주기
    for (int i = 1; i <= N; i++)
    {
        if (inDegree[i] == 0) q.push(i);
    }

    // 모든 노드를 한 번씩만 방문하므로 N번 돌리기
    for (int i = 0; i < N; i++)
    {
        // 그 전에 queue가 비었다는 것은 사이클이 존재한다는 것
        if (q.empty())
        {
            cout << "cycle!";
            return;
        }

        int cur = q.front();
        q.pop();

        cout << cur << " ";

        // cur노드의 간선을 모두 삭제
        // cur 노드가 가리키는 노드들의 진입차수 -1
        for (int k = 0; k < graph[cur].size(); k++)
        {
            int end = graph[cur][k];
            inDegree[end]--;
            if (inDegree[end] == 0) q.push(end);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int M;
    cin >> N >> M;

    int start, end;
    for (int i = 0; i < M; i++)
    {
        cin >> start >> end;
        graph[start].push_back(end);
        inDegree[end]++;
    }

    solve();

    return 0;
}