위상정렬

 위상 정렬이란 순서가 있는, 즉 방향이 있는 작업을 차례로 진행해야 할 때

 

순서를 결정해주기 위해 사용하는 알고리즘이다.

 

사이클이 없는 방향 그래프(DAG)의 모든 노드를

 

주어진 방향성에 어긋나지 않게 순서를 나열하는 것이 바로 위상정렬이다.

 

 

위상 정렬을 배우기 위해서는 우선 DAG(Directed Acyclic Graph)의 개념과

 

특정 노드로 들어오고 나가는 차수에 대한 개념을 알고 있어야 한다. 

 

DAG는 말 그대로 방향을 가지지만 사이클을 가지지 않는 그래프를 의미하고,

 

진입, 진출 차수는 해당 노드로 향하는 간선과, 해당 노드에서 나아가는 간선의 개수라고 생각하면 된다.

 

여기서 중요한 것은 진입 차수이다.

 

진입 차수가 존재한다는 것은, 해당 노드로 이동하기 위해서는 사전에 거쳐야 할 노드가 있다는 것이다.

 

 

 

그렇다면 위상정렬을 활용하는 방법을 알아보자.

 

우선 위상 정렬은 큐와 스택으로 풀 수 있다.

 

 

Queue

 

큐로 푸는 방법은 다음과 같다.

 

1. 진입 차수가 0인 모든 노드를 큐에 삽입한다.

 

2. 큐가 비어있을 때까지 다음을 반복적으로 수행한다.

 - 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 

    (연결된 노드의 진입 차수를 감소시킨다.)

 - 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다.

 

논리는 간단하다.

 

진입 차수가 없는, 즉 가장 먼저 수행할 수 있는 노드를 먼저 모두 큐에 삽입하고

 

큐가 빌 때 까지 노드를 뽑아 해당 노드에서 진출하는 간선을 제거한다.

 

이 때 해당 간선과 연결된 노드의 진입 차수르 감소시킨다.

 

그 후 진입 차수가 0이된 노드를 큐에 삽입시키는 것이다.

 

 

 

Stack

 

스택으로 풀기 위해서는 깊이 우선 탐색 방법을 활용한다.

 

1. 큐와 같이, 진입 차수가 0인 모든 노드를 활용하는 것은 같다.

 

다만 스택으로 풀 때는 이 모든 노드에서 DFS 탐색을 수행한다.

 

2. DFS

 - 해당 노드를 방문 표시한다.(Visited 배열)

 - 인접하면서 방문하지 않은 노드가 있다면 DFS 재귀 호출한다.

 - 함수에서 리턴하기 전에 Stack에 현재 노드를 저장한다.

 

3. Stack이 공백 상태가 될 때까지 pop 한다.

 

 

위 결과 스택에서 꺼내지는 순서의 역순으로 나열하면 위상 정렬을 수행한 결과가 된다.

 

 

 

위상 정렬은

 

모든 정점을 방문하기 전에 큐가 공백 상태가 되면 사이클이 존재하는 것이다.

 

또한 위상 정렬을 활용하기 위해서는 DAG여야 한다.

 

도출되는 순서는 여러가지일 수 있고, 시간 복잡도는 O(V+E)이다.

 

 

라고 이해했다.