Topological Sort(위상 정렬)

🧠 Topological Sort(위상 정렬):

**방향성이 있는 그래프(Directed Acyclic Graph, DAG)**에서 선행 작업이 반드시 먼저 수행되어야 하는 작업 흐름을 결정하는 알고리즘이다.

즉, 작업의 순서를 찾아내는 과정!

 

⚙️ 1️⃣ 핵심 개념

1. Directed Acyclic Graph(DAG)
   • 방향성이 있는 비순환 그래프
   • **순환(Cycle)**이 있으면 위상 정렬 불가

📍 **그래프(Graph)**란? 정점(Vertex, Node): 데이터 포인트 간선(Edge): 정점 간 관계 종류: 방향 그래프(Directed Graph): 방향 화살표 존재 → A → B 무방향 그래프(Undirected Graph): 방향 화살표 없음 → A — B

🛠️ DAG 특징 방향(Directed): **방향성이 있는 간선(Edge)**로 관계 표시 비순환(Acyclic): 사이클이 없는 구조 사이클: 출발점 → 중간 → 출발점으로 다시 돌아오는 경로

DAG 예제    1 → 2 → 3        ↑ ↓        4 ➡️ 방향성: 1 → 2 → 3 일방향 흐름 ➡️ 순환 없음: 어느 노드에서도 출발해도 되돌아오지 않음 → DAG 맞음! ✅

DAG가 아닌 경우    1 → 2 → 3        ↑   ↓        5 ← 4 2 → 3 → 4 → 5 → 2: 사이클 존재 🚨 DAG 아님!

1. 진입 차수(In-degree)
   • 해당 노드로 들어오는 간선의 개수
   • 진입 차수가 0인 노드를 먼저 처리

⚙️  진입 차수(In-degree) 📍 비유로 이해하기: 노드(Node) = 작업(Task) 간선(Edge) = 의존 관계(Dependency) 예: A → B: B를 처리하려면 A가 선행되어야 함 B의 In-degree = 1 (A로부터 오는 하나의 화살표)

A → B → C    ↑    ↓    D → E

📖 진입 차수의 핵심 역할 **위상 정렬(Topological Sort)**에서 진입 차수가 0인 노드를 탐색 시작 진입 차수가 줄어드는 과정을 통해 의존 관계 해소

 

🌐 실제 활용 예시

컴파일러: 코드의 의존 관계를 기반으로 빌드 순서 결정 프로젝트 관리: **작업(Task)**의 선후 관계 정의 (Jira, MS Project) 데이터베이스: 테이블 생성 순서 결정(Foreign Key 의존성)

 

📍 위상정렬 분석

1 → 2 → 3        ↑ ↓        4

 

🔍  핵심 개념: 진입 차수(In-degree)

위상 정렬 알고리즘은 **진입 차수(In-degree)**를 기반으로 동작.

• 진입 차수(In-degree): 노드로 들어오는 간선의 수
• 위상 정렬 시작점: 진입 차수 0인 노드부터 시작

노드	In-degree	이유
1	0	들어오는 간선 없음
2	2	1 → 2 & 4 → 2
3	1	2 → 3
4	0	들어오는 간선 없음

 

⚙️ 정렬 과정

🟢 STEP 1: 초기 큐 생성 In-degree 0: 1, 4 Queue: 1, 4 결과 리스트: []

🟢 STEP 2: 1 꺼내기 Queue: 4 결과 리스트: [1] 동작: 1 → 2로 연결 → 노드 2의 In-degree 감소 In-degree(2): 2 → 1

🟢 STEP 3: 4 꺼내기 Queue: 2 결과 리스트: [1, 4] 동작: 4 → 2로 연결 → 노드 2의 In-degree 감소 In-degree(2): 1 → 0 → 큐에 2 추가

🟢 STEP 4: 2 꺼내기 Queue: 3 결과 리스트: [1, 4, 2] 동작: 2 → 3으로 연결 → 노드 3의 In-degree 감소 In-degree(3): 1 → 0 → 큐에 3 추가

🟢 STEP 5: 3 꺼내기 Queue: empty 결과 리스트: [1, 4, 2, 3]