위상 정렬…

위상 분열기에 대해는 잘 들어보았다만

위상 정렬은 잘 못 들어봤다

그래서 준비한…

친해지길 바래~

- 위상 정렬 편

오늘은 위상정렬의 대표적인 두 가지 방식,

진입 차수 방식과 DFS 방식을 알아볼거다

진입 차수 방식

- 부제 : Khan’s Algorithm

개념

 🔷 핵심

• 진입 차수 : 노드로 들어오는 간선의 개수

• 진입 차수가 없다는 것
  = 바로 시작 가능 하다는 것

• 노드를 제거해가면서 연결된 노드들의 진입 차수 감소

동작순서

1. 각 노드의 진입 차수를 계산한다

                ↓

2. 진입 차수가 0인 노드를 큐에 넣는다

                ↓

3. 큐에서 하나 꺼내서 정렬 결과에 추가

                ↓       

4. 해당 노드가 가리키는 노드들의 진입 차수를 1씩 줄인다

                ↓

5. 새로 진입 차수가 0이 된 노드를 다시 큐에 넣는다

                ↓

6. 큐가 빌 때까지 3~5 반복

예시

그래프:

A → C  
B → C  
C → D

초기 진입 차수: |A|B|C|D| |——|—|—|—| | 0 | 0 | 2 | 1 |

정렬 흐름:

1. A, B 진입차수 0 → 큐에 추가

2. A 꺼내고 → C 진입차수 1로 감소

3. B 꺼내고 → C 진입차수 0 → 큐에 추가

4. C 꺼내고 → D 진입차수 0 → 큐에 추가

5. D 꺼냄 → 끝

→ 결과: A, B, C, D or B, A, C, D

특징 요약

| 항목 | 설명 | | —— | ————————– | | 사이클 감지 | ⭕ 모든 노드를 처리하지 못하면 사이클 존재 | | 구현 | 큐 + 진입 차수 배열 | | 사용 용도 | 현실적 작업 스케줄링, 순서 결정 | | 장점 | 사이클 감지 쉽고, 실행 흐름 직관적 | | 단점 | 진입 차수 배열과 큐 관리가 필요 | ___

DFS 기반 방식

- 부제 : “깊이” 우선 탐색

개념

 🔷 핵심 개념

• DFS 탐색 종료 후 노드를 결과 스택에 넣음 ㅇㅅㅇ

• 후행 작업이 먼저 끝나고 선행이 마지막에 끝남

• 결과 스택을 뒤집을 시 위상 정렬 순서가 되버림;;

동작 순서

1. 방문하지 않은 노드에 대해 DFS 수행

                ↓

2. 자식 노드(연결된 노드) 먼저 DFS

                ↓

3. 모든 자식 DFS 끝나면 현재 노드를 스택에 push

                ↓

4. DFS 종료 후 스택을 뒤집어 출력하면 위상 정렬 결과

예시

그래프:

A → C  
B → C  
C → D

DFS 흐름:

1. A → C → D → 스택: [D, C, A]

2. B → 이미 방문된 C는 건너뜀 → 스택: [D, C, A, B]

3. 역순으로 꺼냄 → B, A, C, D (또는 A, B, C,D)

특징 요약

| 항목 | 설명 | | —— | ————————————– | | 사이클 감지 | ❌ 직접 구현해야 함 (백트래킹 시 방문 중인 노드 재방문 체크) | | 구현 | 재귀 or 명시적 스택 | | 사용 용도 | 작업 종료 순서가 중요한 상황 | | 장점 | 간단하고 코드 짧음 | | 단점 | 사이클 감지 어렵고, 재귀 깊이 위험 있음 | ___