Topological Sort란? Kahn's Algorithm으로 DAG 정렬 쉽게 이해하기

🧠 DAG란?

DAG(Directed Acyclic Graph)는 사이클이 존재하지 않는 방향 그래프입니다. 이 구조는 이벤트 간의 선후 관계를 파악해야 하는 문제에서 매우 유용하게 사용됩니다.

예를 들어, 과목 수강 순서를 정하는 문제에서 필수 선이수 과목이 있다면 그 관계를 DAG로 표현할 수 있습니다.

대표 문제: LeetCode - Course Schedule II

 

 

✅ 비순환 그래프

DAG 를 만족하는 비순환 그래프

 

 

❌ 순환 그래프

DAG를 위반하는 순환 그래프 - 사이클이 존재한다

 

위상 정렬(Topological Sort)이란?

정의: DAG(Directed Acyclic Graph)의 노드를 선형(linear) 순서로 나열하는 정렬 방식입니다.

정렬된 결과는 모든 간선 (a → b)에 대해 a가 b보다 앞서도록 보장합니다.

따라서, 그래프에 사이클이 있다면 위상 정렬은 수행될 수 없습니다.
이를 판단하기 위해 일반적으로 DFS 또는 BFS(Kahn’s Algorithm) 를 사용합니다.

 

 

🛠️ 구현 방법 (BFS - Kahn's Algorithm)

 

• 필수 구성 요소:
  1. in-degree 배열: 각 노드에 들어오는 간선 수 저장
  2. 그래프 인접 리스트: 각 노드가 가리키는 노드 리스트
  3. Queue: in-degree가 0인 노드를 처리
  4. 결과 리스트: 위상 정렬된 노드 저장
• 전체 과정:
  1. 모든 노드의 in-degree 계산
  2. in-degree가 0인 노드들을 Queue에 삽입
  3. Queue에서 노드를 하나씩 꺼내고:
     • 결과 리스트에 추가
     • 해당 노드에서 이어지는 간선 제거 (in-degree 감소)
     • in-degree가 0이 된 노드를 Queue에 추가
  4. 모든 노드를 처리했을 때 결과 리스트의 크기가 전체 노드 수와 같다면 성공적인 위상 정렬, 아니라면 사이클 존재

아래는 예시 코드입니다.

class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Create adjacency list for graph representation
        List<Integer>[] courseSet = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses]; // Track the in-degrees (number of incoming edges)

        // Build the graph
        for (int i = 0; i < prerequisites.length; i++) {
            int course = prerequisites[i][0];
            int prereq = prerequisites[i][1];

            if (courseSet[prereq] == null) {
                courseSet[prereq] = new ArrayList<>();
            }

            // Add an edge from prereq to course (correct direction)
            courseSet[prereq].add(course);
            inDegree[course]++; // Increment the in-degree of the course
        }
        
        Queue<Integer> queue = new LinkedList<>(); //Look for starting node
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        int[] result = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            Integer courseNum = queue.poll(); //start
            result[index++] = courseNum; //append result

            //Now, get the next course
            if (courseSet[courseNum] != null) {
                List<Integer> nextCourses = courseSet[courseNum];
                for (Integer nextCourse : nextCourses) {
                    inDegree[nextCourse]--; //reduce indegree count if visited
                    if (inDegree[nextCourse] == 0) {
                        queue.add(nextCourse);
                    }
                }
            }
        }

        // Check if topological sort was possible, if incremented index is same as provided numCourses
        return index == numCourses ? result : new int[0];
    }
}

 

⏱️ 시간 복잡도 분석

• 시간 복잡도: O(V + E)
  • V: 노드 수 (numCourses)
  • E: 간선 수 (prerequisites.length)
• 공간 복잡도: O(V + E)
  • 인접 리스트 및 in-degree 배열 저장 공간

✅ 마무리 요약

• DAG는 사이클이 없는 방향 그래프이며, 선후 관계가 필요한 문제에 적합합니다.
• 위상 정렬은 DAG의 정점을 선형으로 나열하는 기법입니다
• Kahn’s Algorithm은 BFS 기반의 위상 정렬로, 사이클 탐지에도 사용 가능합니다