DAG와 위상정렬(topological sort)

DAG(Directed Acyclic Graph)

: 사이클이 없는 방향 그래프. DAG에서 에지 <u,v>가 있다면 정점 u는 정점 v를 선행함.

 

 

위상 정렬(topological sort)

: 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 것.  선행관계가 없는 것은 뭐가 먼저 나오든지 상관이 없기 때문에 위상 정렬 결과는 여러 가지가 존재할 수 있음.

 

DAG 예시. 이 그림에서 5의 진입차수는 3.

 

▷ 알고리즘

 

1. 진입차수가 0인 임의의 정점(선행자가 없는 정점)을 큐(혹은 스택)에 삽입

2. 정점 개수만큼 시행하는 반복문 생성

3. 반복문 내부에서는, 큐에서 정점을 하나씩 꺼내어 출력하고 출력한 정점에 붙어있는 에지들을 제거하여 진입차수 재계산

4. 진입차수를 재계산하여 진입차수가 0이 된 것은 큐에 삽입

 

위상정렬이 불가한 경우를 처리해주어야 한다면, 2번을 큐가 빌 때까지 시행하는 반복문으로 수정해줌.

 

 

 

 

 

▷ 프로그램

 

int inDegree[MAX];
vector<int> graph[MAX];

void topologySort() {
	int result[MAX]; // 출력 결과를 저장하는 배열
	queue<int> q;

	for (int i = 1; i <= N; i++) { // 1번부터 N번까지 정점 존재
		if (inDegree[i] == 0) q.push(i);
	}

	for (int i = 1; i <= N; i++) { // 정점 개수만큼 시행
		int next = q.front();
		q.pop();
		result[i] = next; // 출력 결과 저장
		for (int i = 0; i < graph[next].size(); i++) { // 해당 정점에 연결되어 있는 정점에 대하여
			int y = graph[next][i];
			if (--inDegree[y] == 0) { // 진입차수 재계산한 후 0이 되었다면
				q.push(y);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		printf("%d ", result[i]);
	}
}

 

위의 그림에 대해서 시행하면 스택을 사용할 때는 0,1,2,3,5,4 큐를 사용할 때는 0,1,2,3,4,5가 나옴