L13 - Topological Sorting

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

Topological Sorting

 

위상정렬이란 작업들의 선후 관계를 방향 그래프로 표현할 때 선후 관계를 어기지 않도록 정점을 정렬하는 것임

 

=> 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 앞에 위치하도록 정렬

 

대상이 directed graph로 cycle이 없어야함!

= DAG

 

Kahn's Algorithm

 

진입 간선, 진출 간선

 

아이디어는 진입 간선이 없는 정점을 앞에 두는 것임

 

왼쪽 4개, 오른쪽 4개 순으로 진행되는 그림

 

 

순서를 살펴보면

 

1. 진입 간선이 없는 정점을 골라 리스트에 넣음

2. 고른 정점을 제거하고, 연결된 간선도 제거함

모든 정점이 제거될 때까지 위 과정을 반복

 

Implementation Details

 

pseudo code를 살펴보면

 

 

• 각 정점의 진출 간선을 O(1) 만에 확인하기 위해 그래프를 인접리스트로 구현
  
  
• S에 값을 빠르게 넣고 빼려면 List나 Queue등으로 구현
  
  => 정점 순서가 중요하지 않기에
  
  
• 정점 v에 진입 간선이 없음을 O(1)만에 확인하려면 모든 정점 v마다 진입 간선 수를 d[v]에 기록
  
  
• 간선을 직접 지울 필요 없음
  
  => d[v]를 통해 진입 간선 수를 알 수 있으므로

 

 

인접 리스트의 경우 각각의 노드에 대해 어떤 노드로 향하는지를 기록해둠

 

 

Complexity Analysis

 

굉장히 직관적으로 복잡도를 파악할 수 있음

 

pseudo code를 바탕으로

 

 

 

adj를 통해 각 노드의 진입 간선 갯수를 세주는 부분은 간선 수 만큼인 O(|E|)

 

각 노드가 진입 간선이 없는지 판별하고 S에 추가하는 부분은 노드 수 만큼인 O(|V|)

 

while을 통해 S가 0이될 때 까지 즉, 노드 갯수인 |V| 만큼 반복하며

for문을 통해 adj로 연결된 노드의 간선을 다 끊어버리므로 (d[v]를 -1 함) 간선 갯수인 |E| 만큼이 실행됨

 

즉, O(|V| + |E|)

 

총 합치면 O(|V| + |E|) 가 됨

(for문이 각 간선을 한 번만 처리하므로 즉, while문이 돌 때마다 모든 간선을 여러 번 반복하지 않기에 |V| x |E| 가 아니고 |V| + |E|임)

=> 모든 정점과 간선을 한 번씩 방문

 

 

DFS 기반 알고리즘

 

J에서 시작하고 위의 자식을 먼저 방문하는 DFS 예시

 

깊이 우선 탐색(DFS)의 특징을 응용하여 위상정렬 하는 것임

 

=> out-degree가 없는 정점을 먼저 제거하는 방식

 

Kahn's Algorithm과 반대로, DFS를 후처리(post-order visit) 방식으로 순회하면

방문한 순서가 위상정렬의 역순이 된다는 점을 이용

 

1, 2

3, 4

 

 

 

순서는 이러한데

 

1. 방문 순서를 저장할 Stack 생성

 

2. 방문되지 않은 정점을 선택하여 DFS 수행, 방문 순서를 Stack에 저장

 

모든 정점을 방문할 때 까지 2번 과정을 반복하면 됨

 

(Stack에서 값을 꺼내는 순서가 위상정렬 순서가 됨)

 

Complexity Analysis

 

pseudo code를 살펴보면

 

 

 

DFS의 시간복잡도와 동일함

=> DFS는 모든 정점과 간선을 한 번씩 방문하므로 O(|V| + |E|)