[ TIL ] 위상정렬

📌 About

위상정렬은 선후관계가 정의된 그래프에서 정렬하는 알고리즘이다.

선후관계가 명확해야 하기 때문에 사이클이 있어서는 안된다.

📌 Algorithm

1. 필요한 자료구조 생성
   1-1. 각각의 node를 가리키는 개수(진입차수)를 저장하는 리스트 생성
   1-2. 각각의 node가 가리키는 node를 저장하는 Map 생성

2. Edge 정보를 추가

3. 정렬
   3-1. 진입차수가 0인 node 탐색
   3-2. 탐색한 node가 가리키는 node 들의 진입차수 1 감산 연산

📌 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;
    }
}

More Details