Topological Sorting(위상 정렬)의 개념, 구현 방법

DAG (Directed Acyclic Graph)

사이클이 없는 방향 그래프

ex) 작업들의 우선순위, 학과 선수과목, 라면 끓이기

Topological Sorting(위상 정렬)

DAG에서 모든 정점을 순서대로 정렬

정렬 기준: 모든 간선(Vi, Vj)에 대해 Vi가 Vj보다 앞에 위치

 

위상정렬 동작예제

 

위상 정렬 구현

1) 진입 간선이 0인 노드부터 순서대로 탐색하는 방법

 

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

int n, m; // n: 노드, n: 정점
int s, e; // s: 시작지점 e: 끝지점
vector<vector<int>> adjArray;
vector<int> inDeg; // 진입간선의 수
queue<int> q; // 진입간선이 0인 노드를 저장하는 큐
vector<int> A; // 결과값 저장

void AddEdge(int start, int end) {
	adjArray[start].push_back(end); // 방향 그래프이므로 한쪽 방향으로만
}

void topologicalSort1() {
	for (int i = 1; i <= n; i++) {
		if (inDeg[i] == 0)
			q.push(i);
	}
	for (int i = 1; i <= n; i++) {
		int u = q.front();
		q.pop();
		A.push_back(u);
		for (int j = 0; j < adjArray[u].size(); j++) {
			int v = adjArray[u][j];
			inDeg[v]--;
			if (inDeg[v] == 0)
				q.push(v);
		}
	}
}


int main() {
	cin >> n >> m; // 노드, 엣지 개수 입력
	adjArray.resize(n + 1); // 노드 개수만큼 배열 크기 지정
	inDeg.resize(n + 1, 0); // 진입간선의 수 크기 지정

	for (int i = 0; i < m; i++) {
		cin >> s >> e;
		AddEdge(s, e);
		inDeg[e]++;
	}
	topologicalSort1();

	for (int i = 0; i < A.size(); i++)
		cout << A[i] << " ";
}

 

 

2) DFS를 사용하여 반대로 탐색하는 방법

 

1. DFS의 시작은 아무 노드에서나 가능하다. e를 선택하였다.

 

 

2. e가 갈 수 있는 곳은 c와 f가 있다. 그중 먼저 f로 이동한다.

 

 

3. f가 더 이상 갈 수 있는 곳이 없으므로 f는 마지막 노드이다. 따라서 f를 스택에 넣어준 후 다시 e로 돌아간다.

 

 

스택

 

4. e에서는 c로 갈 수 있다. c로 이동한다.

 

 

5. c에서는 더이상 갈 수 있는 곳이 없으므로 c는 마지막 노드이다. 따라서 c를 스택에 넣어준 후 다시 e로 돌아간다.

 

 

스택

 

6. 이제 e에서도 더이상 갈 수 있는 곳이 없으므로 스택에 넣어준다.

 

 

스택

 

7. 방문 안 한 곳 중 아무 곳이나 선택하여 다시 DFS를 진행한다. a를 선택하였다.

 

 

 

8. a가 갈 수 있는 곳은 b와 d가 있다. 먼저 b로 이동한다.

 

 

9. b에서는 더이상 이동할 수 없으므로 스택에 넣어준 후 다시 a로 돌아간다.

 

 

스택

 

10. a에서 d로 갈 수 있으므로 d로 이동한다.

 

 

11. d에서 이동할 수 있는 곳이 없으므로 스택에 넣어준 후 다시 a로 돌아간다.

 

 

 

스택

 

12. 이제 a도 더이상 갈 수 있는 곳이 없으므로 스택에 넣어준다.

 

 

스택

 

13. 아직 방문 안 한 곳인 g에서 다시 DFS를 시작한다. 하지만 g에서 갈 수 있는 곳이 없으므로 바로 스택에 넣어준다.

 

 

스택

 

14. 모든 노드를 방문하고 스택에 넣어주었으므로 마무리가 된 것이다.

 

 

15. 노드의 값을 저장한 스택에서 하나씩 pop을 하면 순서대로 위상 정렬이 된다.

 

g -> a -> d -> b -> e -> c -> f

 

 

 

topologicalSort2(G) {
    for each v∈V
    visited[v] ← NO;
    for each v∈V // 정점의 순서는 무관
    if (visited[v] = NO) then DFS-TS(v);
}
DFS-TS(G,v) {
    visited[v] ← YES;
    for each x∈L(v) // L(v): v의 인접 리스트
    if (visited[x] = NO) then DFS-TS(x);
    
    연결 리스트 R의 맨 앞에 정점 v를 삽입한다;
}