핵심 정리
| 조건 | 내용 |
|---|---|
| 대상 | 방향 비순환 그래프, DAG |
| 의미 | 선행 조건을 지키는 처리 순서 |
| 대표 구현 | 진입 차수 + 큐 |
| 사이클 감지 | 결과 개수가 정점 수보다 작음 |
text
A -> C
B -> C
C -> D
가능한 순서: A, B, C, D 또는 B, A, C, D구조
위상 정렬은 “먼저 해야 하는 작업” 관계가 있는 방향 그래프에서 가능한 순서를 찾습니다. 진입 차수는 어떤 정점으로 들어오는 간선 수입니다. 진입 차수가 0이면 더 기다릴 선행 작업이 없으므로 처리할 수 있습니다.
csharp
var q = new Queue<int>();
for (int i = 0; i < n; i++)
{
if (indegree[i] == 0) q.Enqueue(i);
}
var order = new List<int>();
while (q.Count > 0)
{
int current = q.Dequeue();
order.Add(current);
foreach (int next in graph[current])
{
indegree[next]--;
if (indegree[next] == 0) q.Enqueue(next);
}
}처리가 끝났는데 order.Count < n이면 사이클 때문에 모든 정점을 처리할 수 없다는 뜻입니다.
언제 쓰나
| 문제 신호 | 판단 |
|---|---|
| 작업 순서, 선수 과목 | 위상 정렬 |
| 빌드 순서, 의존성 | 위상 정렬 |
| 방향 그래프에 사이클 여부 확인 | 위상 정렬 결과 개수 |
| 모든 순서 경우의 수 | 백트래킹 추가 필요 |
| 최단 경로 문제 | 다른 그래프 알고리즘 검토 |
위상 정렬 결과는 하나가 아닐 수 있습니다. 진입 차수가 0인 정점이 여러 개이면 어떤 것을 먼저 꺼내느냐에 따라 다른 유효 순서가 나옵니다.
주의할 점
위상 정렬은 DAG에서만 가능합니다. 사이클이 있으면 선후 관계를 모두 만족하는 순서가 존재하지 않습니다.
또 간선 방향을 반대로 저장하면 완전히 다른 의미가 됩니다. “A를 하기 전에 B가 필요하다”를 B -> A로 둘지, A -> B로 둘지 입력 해석을 먼저 고정하세요.
참고 링크
1 sources