알고리즘 : 위상 정렬

위상 정렬

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

위와 같이 나열하는 것을 위상 정렬이라고 한다.

 

위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다.

진입차수 (Indegree)

특정한 노드로 들어오는 간선의 개수

 

진출차수 (Outdegree)

특정한 노드에서 나가는 간선의 개수

 

 

동작 과정

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다

 

 

예시

진입차수가 0인 노드가 존재하기 위해서는 사이클이 없는 그래프가 필요하다

 

[초기단계] 진압차수가 0인 모든 노드를 큐에 넣는다.

 

[1] 큐에서 노드 1을 꺼낸 뒤에 노드 1에서 나가는 간선을 제거한다. 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.

 

[2] 큐에서 노드 2를 꺼낸 뒤에 노드 2에서 나가는 간선을 제거한다. 여기서 노드 2가 아니라 노드 5부터 꺼내도 된다.

 

이러한 과정을 반복하면 위상 정렬을 수행한 결과를 알 수 있다.

한 번 큐에 삽입된 노드는 다시 들어가지 않으며 각 노드의 인접 간선을 모두 확인하기 때문에 연산 횟수는 V+E가 된다. 즉 시간복잡도는 O(V+E)가 된다.

 

위상 정렬은 DAG(DIrect Acyclic Graph)인 순환하지 않는 방향 그래프에서만 가능하다. 위상 정렬에는 여러가지 답이 존재할 수 있으며 (큐에 새롭게 들어가는 값이 2개 이상인 경우) 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다.

 

import java.util.*;

public class Main {

    // 노드의 개수(V)와 간선의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    // 모든 노드에 대한 진입차수는 0으로 초기화
    public static int[] indegree = new int[100001];
    // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // 위상 정렬 함수
    public static void topologySort() {
        ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
        Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용

        // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= v; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 원소 꺼내기
            int now = q.poll();
            result.add(now);
            // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for (int i = 0; i < graph.get(now).size(); i++) {
                indegree[graph.get(now).get(i)] -= 1;
                // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                if (indegree[graph.get(now).get(i)] == 0) {
                    q.offer(graph.get(now).get(i));
                }
            }
        }

        // 위상 정렬을 수행한 결과 출력
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 방향 그래프의 모든 간선 정보를 입력 받기
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b); // 정점 A에서 B로 이동 가능
            // 진입 차수를 1 증가
            indegree[b] += 1;
        }

        topologySort();
    }
}

 

자바로 구현한 위상 정렬 알고리즘이다. 앞서 말했듯이 시간복잡도는 O(V+E)가 된다.