위상정렬 (Topological Sort)

위상정렬이란 ❓

위상정렬(Topological Sort)이란 싸이클이 없는 방향그래프(Directed Acyclic Graph, DAG)에서 정점들을 선형순서로 나열한 것을 의미한다. 아래 그림과 같이 정점에 대해 순서를 부여하는 것을 위상정렬이라고 하며, 주어진 그래프에 따라 여러 개의 위상정렬이 존재할 수 있다. 일반적으로, 작업들 사이에 의존관계가 존재할 때 수행 가능한 작업 순서를 도시고하하는데 위상정렬을 사용한다.

단, 위상정렬의 결과는 그래프의 각 간선 (u,v)에 대해 u가 v보다 반드시 앞서 나열되어야 한다.

구현 방법

큐를 이용한 방법 (순방향)

순방향 방법은 진입차수가 0인 정점 v로부터 시작하여 v를 출력하고 v를 그래프에서 제거하는 과정을 반복하는 방법이다.

1. 진입차수가 0인 정점을 큐에 넣는다.
2. 꺼낸 정점에 연결된 간선들을 모두 제거한다.
3. 간선 제거후 진입차수가 0인 정점들을 큐에 넣는다.
4. 큐가 모두 빌때까지 2-3번을 반복한다.

모든 정점을 방문하기전에 큐가빈다면 싸이클이 존재하는 것이다. 즉, 진입차수가 0인 노드가 존재하지 않는다는 것이다.

public class 위상정렬 {

    private static List<Integer>[] adj;
    private static int[] inDegree;
    private static int size;
    private static int[] result;

    public static void topologicalSort() {
        Queue<Integer> q = new LinkedList<>();

        // 진입차수가 0인 노드를 큐에 넣는다
        for (int i = 1; i < inDegree.length; i++) {
            if(inDegree[i] == 0) q.offer(i);
        }

        // 모든 정점을 방문해야하는 필요충분조건이 있음
        for (int i = 0; i < size; i++) {
            // 만약 큐가 비어있다면 싸이클 존재
            if(q.isEmpty()) return;
            int curr = q.poll();

            result[i] = curr;
            
            // 뽑은 정점과 연결된 간선을 모두 제거한다.
            for(int next : adj[i]) {
                // 진입차수가 0인 정점을 큐에 넣는다.
                if(--inDegree[next] == 0) q.offer(next);
            }
        }
    }

    public static void main(String[] args) {
        size = 7;

        adj = new List[size];
        result = new int[size];
        inDegree = new int[size+1];

        for (int i = 0; i < size; i++) {
            adj[i] = new ArrayList<>();
        }

        adj[1].add(2);
        inDegree[2]++;

        adj[2].add(3);
        inDegree[3]++;

        adj[3].add(4);
        inDegree[4]++;

        adj[4].add(6);
        inDegree[6]++;

        adj[5].add(6);
        inDegree[6]++;

        adj[6].add(7);
        inDegree[7]++;

        topologicalSort();
    }
}

스택을 이용한 방법(역방향)

큐를 이용한 방법과 반대로 진출차수가 0인 정점을 이용해서 정렬하는 방식이다.

1. DFS를 이용해서 모든 점을 방문한다.
2. 모든 점의 방문이 끝난 시점에 리스트에 추가한다.

    public static void dfs(int curr) {
        visited[curr] = true;
        
        for(int next : adj[curr]) if(!visited[next]) dfs(next);
        
        sequence.add(curr);
    }
    
     public static void main(String[] args) {
        size = 7;

        visited = new boolean[size];
        adj = new List[size];
        sequence = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            adj[i] = new ArrayList<>();
        }

        adj[1].add(2);
        inDegree[2]++;

        adj[2].add(3);
        inDegree[3]++;

        adj[3].add(4);
        inDegree[4]++;

        adj[4].add(6);
        inDegree[6]++;

        adj[5].add(6);
        inDegree[6]++;

        adj[6].add(7);
        inDegree[7]++;

        for (int i = 0; i < size; i++)  if(!visited[i]) dfs(i);
        
    }

시간복잡도

위상정렬은 BFS또는 DFS와 동일한 O(V + E) 시간복잡도를 가진다.