위상 정렬(Topology Sort)의 구현(JAVA)

언제 사용하는가?

 

순서가 정해져있는 작업을 차례로 수행해야 할때 그 순서를 정해주기 위해 사용하는 알고리즘이다.

 

이때 그런 순서가 정해져 있다는건 그래프가 단방향 그래프로 사이클이 없어야 한다.

 

또 그래프에 따라 여러가지의 순서가 나올수 있다.

 

특징

 

1. 현재 그래프가 위상정렬이 가능한지 알 수 있다. (사이클이 발생한다면 위상정렬이 불가능하다.)

2. 위상정렬이 가능하다면 그 정렬된 결과를 알 수 있다.

 

 

어떻게 사용하는가?

 

위상정렬은 다음의 순서로 진행된다.

 

1. 진입차수가 0인 정점을 찾아 큐에 삽입한다.

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.

    2.1 꺼낸 원소를 차례대로 저장한다.

3. 간선을 제거한뒤 진입차수가 0인 정점을 큐에 삽입한다.

4. 큐가 비워질때까지 2,3의 과정을 반복한다.

    4.1 이때 모든 원소를 방문하기전에 큐가 비워진다면, 사이클이 발생한다는 의미

    4.2 모든 원소를 방문하여 큐가 비워진다면 큐에서 꺼낸 순서로 저장한 것이 위상정렬된 결과이다.

 

 

그럼 간단한 그래프의 예시를 들어 위상정렬의 과정을 설명해 보도록 하겠다.

 

먼저 다음과 같은 간선관계를 갖는 그래프가 존재한다고 가정해보도록하겠다.

 

 

 

이제 위에서 나열한 순서대로 진행해보도록 하겠다.

 

먼저 진입차수가 0인 정점을 찾아 큐에 삽입한다.

 

이때 진입차수는 다른 정점에서 현재 정점을 가리키는 간선의 개수라고 생각하면 된다.

 

표로 정리를 하자면 

 

0	1	2	3	4	5
0	1	1	1	2	4

 

 

다음과 같이 정리할수 있겠다. 그럼 표로 정리한 바와 같이 진입차수가 0인 최초의 정점인 0번 정점이

시작정점이 된다.

 

0번 정점을 큐에 넣고 다시 꺼내 연결된 간선을 모두 제거하면 다음과 같다.

 

 

이제 다시 간선을 제거 했으니 진입차수에도 변화가 생긴다.

이를 다시 표로 나타내면 다음과 같다.

 

0	1	2	3	4	5
0	1	0	1	1	3

 

 

그럼 다음으로 진입차수가 0이되는 정점인 2번 정점을 넣고 다시 꺼내 연결된 간선을 제거하면,

 

 

다음과 같다.

그리고 진입차수 역시 다음과 같이 변경될것이다.

 

0	1	2	3	4	5
0	0	0	0	1	2

 

 

다음 진입차수가 0인 정점은 1, 3 두개의 정점이므로 둘다 차례로 큐에 삽입후 다시 꺼낸다.

 

이때 삽입순서에 따라 위상정렬의 순서는 바뀔수 있다.

즉 여러가지 정렬순서가 존재할수 있다는것이다.

 

일단 현재는 1, 3 의 순서로 삽입된다 가정 후 계속 해서 이어나가겠다.

 

다음 정점은 1번 정점이므로 연결된 간선을 제거한 진입차수의 결과는 다음과 같다.

 

 

0	1	2	3	4	5
0	0	0	0	0	2

 

 

또한 4번 정점의 진입차수가 0이 되었으므로 역시 큐에 삽입된다.

다음 정점은 3번 정점이다.

 

 

0	1	2	3	4	5
0	0	0	0	0	1

 

 

이번에는 진입차수가 0이되는 정점이 없으므로 큐에 삽입되는 정점은 없고 바로 다음 정점으로 넘어간다.

 

다음 정점인 4번 정점을 꺼내 간선제거후 진입차수를 업데이트하면 이제 모든 진입차수가 0이되고

5번 정점이 큐에 들어갈것이다.

 

 

0	1	2	3	4	5
0	0	0	0	0	0

 

 

그리고 더이상 방문하지 않은 노드가 없고 다음 정점인 5번 노드를 꺼내게 된다면 이제 큐가 비어있으므로

차례로 큐에서 꺼낸 순서대로 나열한 결과가 곧 위상정렬된 결과이다.

 

>> 0 ➡️ 2 ➡️ 1 ➡️  3 ➡️ 4 ➡️ 5

 

이때 아까 1번 정점과 3번 정점이 동시에 진입차수가 0이 되었던 시점에 3번 정점을 먼저 큐에 삽입했다면

0 ➡️ 2 ➡️ 3 ➡️  1 ➡️ 4 ➡️ 5의 정렬 결과를 얻을수 있겠다.

 

그럼 이제 이를 소스로 구현 해보도록 하겠다.

 

구현

 

먼저 그래프를 저장하기 위한 인접리스트와 진입차수를 저장할 리스트를

하나씩 필드로 선언해주도록 하겠다.

 

public class TopologySort {

    private final List<Integer> inDegrees;
    private final List<List<Integer>> edges;
    
}

 

 

다음으로 간선관계를 입력할 메소드를 하나 작성해주도록 하겠다.

정점 a에서 정점 b로 가는 방향의 간선인 경우 정점 b의 진입차수는 1 증가할것이다.

 

    void add(int a, int b) {
        edges.get(a).add(b);
        inDegrees.set(b, inDegrees.get(b) + 1);
    }

 

 

이제 위상 정렬을 구현 해보도록 하겠다.

 

먼저 정렬한 결과를 저장할 리스트를 하나 선언해준다.

이 리스트를 리턴해주면 될것이다.

 

다음으로 진입차수가 0인 정점을 삽입하고 꺼낼 큐를 선언해주도록 하겠다.

 

    List<Integer> topologySort(int n) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
    }

 

 

이제 최소의 시작 정점을 찾아야 하기 때문에 진입차수가 0인 정점을 순회하며 찾는다.

 

    List<Integer> topologySort(int n) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        // 진입차수 0인 노드 삽입
        for(int i = 0; i < n; i++) {
            if(inDegrees.get(i) == 0) {
                queue.add(i);
            }
        }
    }

 

 

그리고 모든 정점을 방문전에 큐가 비어있다면 사이클이 발생한 상황이므로 예외처리해준다.

 

    List<Integer> topologySort(int n) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        // 진입차수 0인 노드 삽입
        for(int i = 0; i < n; i++) {
            if(inDegrees.get(i) == 0) {
                queue.add(i);
            }
        }
        // 모든 노드 방문
        for(int i = 0; i < n; i++) {
            if(queue.isEmpty()) {
                throw new IllegalArgumentException("[ERROR] 사이클 발생");
            }
        }
    }

 

 

이어서 큐에서 원소를 꺼내 결과리스트에 넣어주고 꺼낸 노드와 연결된 간선을 모두 제거후

다음으로 진입차수가 0이되는 정점을 큐에 삽입하는 과정을 반복하게 만들어주면 된다.

 

    List<Integer> topologySort(int n) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        // 진입차수 0인 노드 삽입
        for(int i = 0; i < n; i++) {
            if(inDegrees.get(i) == 0) {
                queue.add(i);
            }
        }
        // 모든 노드 방문
        for(int i = 0; i < n; i++) {
            if(queue.isEmpty()) {
                throw new IllegalArgumentException("[ERROR] 사이클 발생");
            }
            int now = queue.remove();
            result.add(now);
            for(int no : edges.get(now)) {
                inDegrees.set(no, inDegrees.get(no) - 1); // 진입차수 제거
                if(inDegrees.get(no) == 0) {
                    queue.add(no);
                }
            }
        }
        return result;
    }

 

 

이제 위에서 설명한 간선정보를 데이터로 넣어 테스트해보면...

 

        int n = 6;
        List<List<Integer>> edges = new ArrayList<>();
        List<Integer> inDegrees = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
            inDegrees.add(0);
        }

        TopologySort topologySort = new TopologySort(edges, inDegrees);

        topologySort.add(0, 2);
        topologySort.add(0, 4);
        topologySort.add(0, 5);
        topologySort.add(2, 1);
        topologySort.add(1, 4);
        topologySort.add(2, 3);
        topologySort.add(2, 5);
        topologySort.add(3, 5);
        topologySort.add(4, 5);

 

 

다음과 같이 예상한 위상정렬 결과를 얻을수 있다.

 

 

아래는 코드의 전문이다.

 

package algorithm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class TopologySort {

    private final List<Integer> inDegrees;
    private final List<List<Integer>> edges;

    TopologySort(
        final List<List<Integer>> edges, 
        final List<Integer> inDegrees) {
        this.inDegrees = inDegrees;
        this.edges = edges;
    }

    void add(int a, int b) {
        edges.get(a).add(b);
        inDegrees.set(b, inDegrees.get(b) + 1);
    }

    List<Integer> topologySort(int n) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new ArrayDeque<>();
        // 진입차수 0인 노드 삽입
        for(int i = 0; i < n; i++) {
            if(inDegrees.get(i) == 0) {
                queue.add(i);
            }
        }
        // 모든 노드 방문
        for(int i = 0; i < n; i++) {
            if(queue.isEmpty()) {
                throw new IllegalArgumentException("[ERROR] 사이클 발생");
            }
            int now = queue.remove();
            result.add(now);
            for(int no : edges.get(now)) {
                inDegrees.set(no, inDegrees.get(no) - 1); // 진입차수 제거
                if(inDegrees.get(no) == 0) {
                    queue.add(no);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> edges = new ArrayList<>();
        List<Integer> inDegrees = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            edges.add(new ArrayList<>());
            inDegrees.add(0);
        }

        TopologySort topologySort = new TopologySort(edges, inDegrees);

        topologySort.add(0, 2);
        topologySort.add(0, 4);
        topologySort.add(0, 5);
        topologySort.add(2, 1);
        topologySort.add(1, 4);
        topologySort.add(2, 3);
        topologySort.add(2, 5);
        topologySort.add(3, 5);
        topologySort.add(4, 5);

        for(int no : topologySort.topologySort(n)) {
            System.out.print(no + "\t");
        }
    }
}