위상 정렬

위상 정렬

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.

위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없습니다.

 

위상 정렬 핵심 이론

1. 진입 차수는 자기 자신을 가리키는 에지의 개수이다. ArrayList로 그래프를 표현했다. 진입 차수 배열을 ArrayList로 표현한다. 만약 1에서 2, 3을 가리키면 D [2], D [3]을 각각 1만큼 증가시킨다.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 그 후 인접리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.
3. 진입 차수가 0인 노드 1을 선택하여 2, 3의 진입 차수를 1씩 빼 D[2], D [3]을 0으로 만든다. 계속해서 모든 노드가 정렬될 때까지 반복한다. 여기서 진입 차수가 0인 노드를 위상 정렬 배열에 넣는다.

위상 정렬 수행 과정

1. 진입 차수가 0인 노드를 큐에 저장
2. 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.
4. 큐가 빌 때까지 1 ~ 3을 반복한다.

시간 복잡도(노드 수: V, 에지 수: E)

O(V + E)

 

코드로 표현

ArrayList<ArrayList<Integer>> A = new ArrayList<>();  // 인접 리스트 
for(int i = 0; i <= n; i++) {
	A.add(new ArrayList<>());
}
int[] indegree = new int[n + 1]; // 진입 차수 배열
for(int i = 0; i < m; i++) {
	int s = sc.nextInt();
    int e = sc.nextInt();
    A.get(s).add(e);
    indegree[e]++;         // 진입 차수 배열 데이터 저장하기
}
Queue<Integer> que = new LinkedList<>();  // 위상 정렬 수행하기
for(int i = 1; i <= n; i++) { 
	if(indegree[i] == 0) {
    	que.offer(i);
    }
}
while(!que.isEmpty()) {
	int now = que.poll();
    for(int next : A.get(now)) {
    	indegree[next]--;
        if(indegree[next] == 0) {
        	que.offer(next);
        }
    }
}