[알고리즘] 그래프 : 위상정렬(Topological Sort)과 Task Graph, Kahn 알고리즘

 

 

작업 간의 순서(의존성)을 체계적으로 관리하기 위해서 위상 정렬(Topological Sort) 이라는 개념이 사용된다.

 

위상 정렬의 간단한 개념은 앞에서 그래프에 대해 설명하면서 언급이 되었긴 하지만, 

 

이번 글에서는 위상 정렬의 기본 개념부터

실제로 구현할 때 자주 사용되는 칸 알고리즘(Kahn’s Algorithm) 과 이를 응용한 Task Graph 구조까지 알아보도록 하겠다. 

 

---

 

1. 그래프의 위상정렬 (Topological Sort) 이란?

방향 그래프(Directed Graph) 에서 모든 간선의 방향을 거스르지 않고 정점(노드)을 나열하는 것

 

즉, u → v 가 있다면 u가 반드시 v보다 먼저 나와야 한다는 것. 

결과적으로, 정점들의 “선형 순서(Linear Ordering)” 를 만드는 과정.

 

 

 

1-1. 위상 정렬의 조건

위상 정렬을 하려면 그 그래프는 반드시 DAG(Directed Acyclic Graph, 비순환 방향 그래프) 이어야 한다.

사이클(Cycle)이 있으면 순서를 정할 수 없음 (예: A→B, B→C, C→A) 

 

왼쪽은 DAG / 오른쪽은 사이클이 있으므로 DAG가 아님

 

 

1-2. 위상 정렬 특징 

결과는 하나로 정해지지 않을 수도 있다.

진입차수(In-degree)가 0인 노드들은 동시에 시작 가능 → 병렬 실행 가능

각 노드들의 진입차수는 다음과 같다.

 

Task1, Task2, Task6은 진입차수가 0으로, 동시에 시작이 가능한 노드들이다. 

=> 병렬 실행 가능하다..! 

 

 

1-2-1. 관련 용어 정리 

여기서, 진입 차수라는 단어가 낯설 수 있다. 관련 용어들은 다음과 같다. 

용어	의미
진입 차수 (In-degree)	노드로 들어오는 간선의 개수
진출 차수 (Out-degree)	노드에서 나가는 간선의 개수
차수 (Degree)	진입 차수 + 진출 차수

 

 

 

2. Task Graph란?

여러 작업(Task) 간의 의존 관계를 그래프로 표현한 구조.

• 작업 간의 의존 관계(Dependency) 를 간선(Edge) 으로 연결한 싸이클 없는 그래프 기반 실행 구조이다.

요소	설명
Node	실행할 작업 단위 ( 함수 객체(std::function) 나 작업 단위(Job) 등..)
Edge	“이 작업이 끝나야 다음 작업 실행 가능”을 나타내는 의존 관계 : 선후 관계(Dependency)
Graph 구조	DAG (사이클 없는 방향 그래프)
실행(Run) 순서	위상 정렬을 통해 순서 결정
병렬 실행	의존이 없는 노드(진입 차수 0)는 동시에 실행 가능

 

즉, Task Graph = “작업 순서를 보장하면서 병렬 실행을 최적화하는 구조”

 

 

2-1. 의존성이란?

“A 작업이 끝나야 B 작업을 할 수 있다”  → 이런 관계를 의존성(Dependency) 이라고 함 

• 즉, "B는 A에 의존한다".  그래프로 표현하면 다음과 같다. 

 A → B

이 화살표(간선, Edge)는 “B를 실행하기 전에 A를 먼저 해야 한다”는 의존 관계를 나타내는 것. 

 

 

2-2. 의존성을 추가한다?

의존성 추가 == 새로운 선후 관계(Edge) 를 그래프에 추가한다.

 

Task6 -> Task2 의존성을 추가한 그래프. BUT, 해당 이미지는 순환(Cycle) 문제가 있는 그래프임을 주의!!

 

" Task6 이 끝난 후, Task2를 실행되게 하고 싶다 "  Task6  → Task2 간선을 추가한 이미지 이다. 

AddDependency(Task6, Task2);

 

주의!!

의존성을 아무렇게나 추가하다 보면 순환(Cycle) 이 생길 수 있음. 

( 나머지는 뒤에서 설명 )

 

 

 

 

 

3. Kahn’s Topological Sort (칸 알고리즘)

진입 차수 0인 노드부터 큐에 넣고, → BFS(너비 우선 탐색) 방식으로 순서대로 처리한다.

알고리즘 순서

1. 진입 차수가 0인 노드를 큐에 삽입
2. 큐에서 하나 꺼내 처리(실행)
3. 그 노드와 연결된 다음 노드들의 진입 차수 -1
4. 차수가 0이 된 노드를 큐에 추가
5. 큐가 빌 때까지 반복 (큐에 남은게 있다면 2번 반복) 

→ 큐에서 꺼낸 순서가 곧 위상 정렬 결과( = 실행 순서)

 

 

 

4. 순환(Cycle) 검사

위에서 언급했듯. 의존성을 추가하면 순환(Cycle)이 생길 수 있음.

Task6 -> Task2 의존성을 추가해서 순환 생김.

 

그래서 의존성 추가할 때마다 순환 검사 해야한다..! 

 

• 칸(Kahn) 알고리즘으로 모든 노드를 처리하지 못하면 순환(Cycle)이 존재한다는 뜻.
  • 칸 위상 정렬 방식을 사용하면 사이클이 있는 부분은 진입 차수가 0이 될 수 없으므로 Task를 처리할 수 없다.
• 즉, 처리된 노드 수 < 전체 노드 수   => 순환 발생 

 

 

4-1. 순환 검사 하는 법

그러면 의존성 추가할 때마다 어떻게 순환검사를 할 수 있을까?

AddDependency(Task6, Task2);

예를들어, 위 처럼 의존성을 추가할 때

• Task2에서 DFS로 거슬러 올라가서 Task6이 연결되어 있는지 찾아본다.
• Task6과 이미 연결되어있다면 => 순환 발생 

 

4-1-1. 탐색 알고리즘 2가지 중에서 DFS 사용하는 이유? 

• DFS: 경로 차제가 있는가 확인
• BFS: 짧은 경로가 무엇인가 확인

BFS도 가능하지만, 순환 존재 여부는 DFS가 더 직관적이다 ( 경로 존재 여부만 확인하면 되니까..! )

 

 

 

 

5. 병렬 처리

진입 차수 0인 노드 = 의존성이 없는 독립 Task → 병렬 실행 가능

 

• 초기에는 Task1, Task2의 진입차수가 0 = 의존성이 없다 = 병렬실행 가능
• 또한 Task3, Task5도 의존이 사라지면 병렬실행이 가능해진다. 

 

 

5-1. 병렬 실행 시스템 구조 (C++ 예시)

TaskGraph
{
   std::vector<TaskNode> nodes; 
   std::queue<int> ready_queue; // 의존이 제거되어 실행 가능한 노드
   std::vecot<std::atomic<int>> // 수정할 원자적 진입 차수 (의존 수)
}

 

스레드 구성은 다음과 같을 수 있다. 

• Main Thread
  • Run() 실행 → 진입 차수 0인 Task를 큐에 넣음
  • 여러 WorkerThread 생성 후 종료까지 대기
• Worker Thread
  • 큐에서 Task를 꺼내 실행
  • 후속 노드의 진입 차수를 줄이고, 0이 되면 큐에 추가
  • 모든 Task 완료 시 종료
  • 큐가 비었으면 대기 (CPU 자원 절약을 위해 Thread Blocking)