Quick Flow
선행 작업이 모두 끝난 정점, 즉 진입 차수가 0인 정점부터 꺼냅니다. 결과 수가 정점 수보다 적으면 남은 정점들이 사이클을 이루므로 유효한 순서가 없습니다.
A -> C
B -> C
C -> D
가능한 순서: A, B, C, D 또는 B, A, C, D- 방향 그래프의 선후 관계: 위상 정렬
- 순서가 하나인지 검사: 처리 중 진입 차수 0 정점 수 확인
- 모든 가능한 순서: 백트래킹 추가
구조
위상 정렬은 “먼저 해야 하는 작업” 관계가 있는 방향 그래프에서 가능한 순서를 찾습니다. 진입 차수는 어떤 정점으로 들어오는 간선 수입니다. 진입 차수가 0이면 더 기다릴 선행 작업이 없으므로 처리할 수 있습니다.
static List<int>? TopologicalOrder(IReadOnlyList<int>[] graph)
{
var indegree = new int[graph.Length];
foreach (IReadOnlyList<int> edges in graph)
{
foreach (int next in edges) indegree[next]++;
}
var queue = new Queue<int>();
for (int vertex = 0; vertex < graph.Length; vertex++)
{
if (indegree[vertex] == 0) queue.Enqueue(vertex);
}
var order = new List<int>();
while (queue.TryDequeue(out int current))
{
order.Add(current);
foreach (int next in graph[current])
{
indegree[next]--;
if (indegree[next] == 0) queue.Enqueue(next);
}
}
return order.Count == graph.Length ? order : null;
}처리가 끝났는데 order.Count < graph.Length이면 사이클 때문에 모든 정점을 처리할 수 없다는 뜻입니다. 각 정점과 간선을 한 번씩 다루므로 시간과 공간은 O(V + E)입니다.
언제 쓰나
| 문제 신호 | 판단 |
|---|---|
| 작업 순서, 선수 과목 | 위상 정렬 |
| 빌드 순서, 의존성 | 위상 정렬 |
| 방향 그래프에 사이클 여부 확인 | 위상 정렬 결과 개수 |
| 모든 순서 경우의 수 | 백트래킹 추가 필요 |
| 최단 경로 문제 | 다른 그래프 알고리즘 검토 |
위상 정렬 결과는 하나가 아닐 수 있습니다. 진입 차수가 0인 정점이 여러 개이면 어떤 것을 먼저 꺼내느냐에 따라 다른 유효 순서가 나옵니다. 가장 번호가 작은 유효 순서처럼 정책이 필요한 경우에는 Queue<T> 대신 PriorityQueue<TElement, TPriority>를 써서 번호를 priority로 넣습니다. 이 경우 시간은 O((V + E) log V)가 됩니다.
주의할 점
위상 정렬은 DAG에서만 가능합니다. 사이클이 있으면 선후 관계를 모두 만족하는 순서가 존재하지 않습니다.
또 간선 방향을 반대로 저장하면 완전히 다른 의미가 됩니다. “A를 하기 전에 B가 필요하다”를 B -> A로 둘지, A -> B로 둘지 입력 해석을 먼저 고정하세요.
참고 링크
1 sources