📌 About

위상정렬 알고리즘이란 선후관계가 정의된 그래프 구조에서 정렬을 하기위한 알고리즘이다.

📌 Algorithm

Step 1. 필요한 자료구조 생성

Step 1-1. 각각의 node를 가리키는 개수를 저장하는 리스트 생성

Step 1-2. 각각의 node가 가리키는 node를 저장하는 Map 생성

List<Integer> degrees = new ArrayList<>();
Map<Integer, List<Integer>> nextNodes = new HashMap<>();

Step 2. Edge 정보를 추가

public void addEdge(int from, int to) {
    degrees.set(to, degrees.get(to) + 1);
    nextNodes.get(from).add(to);
}

Step 3. 정렬

public List<Integer> sort() {
    List<Integer> sorted = new ArrayList<>();

    Queue<Integer> readies = IntStream.range(0, SIZE).boxed()
            .filter(nno -> degrees.get(nno) == 0)
            .collect(Collectors.toCollection(LinkedList::new));
    while (!readies.isEmpty()) {
        for (int nno : nextNodes.get(readies.peek()))
            if (degrees.set(nno, degrees.get(nno) - 1) == 1) readies.offer(nno);
        sorted.add(readies.poll());
    }

    return sorted;
}

📌 Java Code

public class Topological {

    private final int SIZE;
    private final List<Integer> degrees = new ArrayList<>();
    private final Map<Integer, List<Integer>> nextNodes = new HashMap<>();

    public Topological(int size) {
        this.SIZE = size;
        for (int nno = 0; nno < size; nno++) {
            degrees.add(nno, 0);
            nextNodes.put(nno, new ArrayList<>());
        }
    }

    public void addEdge(int from, int to) {
        degrees.set(to, degrees.get(to) + 1);
        nextNodes.get(from).add(to);
    }

    public List<Integer> sort() {
        List<Integer> sorted = new ArrayList<>();
        Queue<Integer> readies = IntStream.range(0, SIZE).boxed()
                .filter(nno -> degrees.get(nno) == 0)
                .collect(Collectors.toCollection(LinkedList::new));
        while (!readies.isEmpty()) {
            for (int nno : nextNodes.get(readies.peek()))
                if (degrees.set(nno, degrees.get(nno) - 1) == 1) readies.offer(nno);
            sorted.add(readies.poll());
        }
        return sorted;
    }
}

📌 Example

다음과 같은 그래프가 있다고 하자.

진입 차수와 진출 연결 노드는 다음과 같이 정리할 수 있다.

N은 node의 번호 D는 진입차수 T는 가리키는 node의 번호들이다.

Node 탐색은 D = 0인 것만 탐색한다.

현재 node 1, 7번이 D = 0이기 때문에 두 node를 탐색 queue에 넣는다.