3. Topological Sort

목차

1. 개념
2. Topological Sort 구현 (순방향)
3. Topological Sort 구현 (역방향)

1. 개념

Topological Sort 위상정렬

• 방향 그래프에서 vertex를 edge 방향에 맞게 순서대로 나열하는 알고리즘
• 만약 edge u->v가 존재한다면, Topological sort 결과는 항상 u가 반드시 v보다 앞에 있어야 한다.

ex)

• Topological Sort는 DAG(Directed Acyclic Graph, 사이클이 없는 방향 그래프)에서만 가능하다.
  ex) 1->2->3, 3->1 이므로 u->v가 존재하지만, 항상 u가 v보다 앞에 있지 않다. (DAG가 아닌 그래프는 Topological Sort가 불가능한 반례)

2. Topological Sort 구현 (순방향)

• indegree(진입차수) 해당 vertex로 들어온 edge의 개수
  ex) vertex '0'의 진입차수=0 / vertex '2'의 진입차수=2

• 핵심 구현 내용 : indegree(진입차수)가 0인 vertex를 하나씩 제거할 때마다 indegree를 다시 계산하여 indegree가 0인 vertex를 다시 찾기

	[구현]
	1. indegree가 0인 vertex 찾기
    2. 0인 vertex를 stack에 push(넣기)
    3. 0인 vertex를 pop(제거)하면서 indegree 다시 계산
    4. 위 과정을 반복하면서 stack에 없을 때까지 반복

2-1. indegree가 0인 ver

package TopologicalSort;

import java.util.*;

// 순방향
public class TopologicalSort1 {
	int N;							//vertex 개수
	List<Integer>[] adjList;		//graph
	int[] count;					//indegree(진입 차수)
	Stack<Integer> stack;			//indegree가 0인 vertex 임시 저장
	List<Integer> sequence;			//결과 저장
	boolean[] visited;				//vertex 방문여부
	
    ...
	...
    
	// 진입차수 계산 -> 0인 vertex를 sequence에 넣기 -> 추가한 vertex 제거 -> 반복
	public List<Integer> tsort() {
		// indegree 계산하기 (skip; main에서 직접 count)
		// indegree가 0인 vertex를 stack에 넣기
		for(int i=0; i<N; i++) {
			if(count[i]==0) stack.push(i);
		}

		// sequence에서 indegree가 0인 vertex를 모두 제거할 때까지 반복
		while(!stack.isEmpty()) {			
			int ver = stack.pop();
			sequence.add(ver);
			
			// 그래프에서 add한 edge 제거하기
			for(int e: adjList[ver]) {
				count[e]--;
				
				// indegree가 0인 vertex를 전부 sequence(sort)하기 전까지 계속 반복
				if(count[e]==0) {stack.push(e);}
			}
		}
		
		
		return sequence;
	}

}