위상정렬
위상정렬(Topological Sorting)이란?
방향그래프의 노드들을 간선의 방향에 거스르지 않도록 나열하는 것을 말한다.
위상정렬은 왜 쓰는가?
위상 정렬을 사용하면 크게 3가지 이점이 있다.
1. 의존성이 작업 스케줄링
-> 두 노드 사이에 단방향의 간선이 있다는 건
두 작업 사이에 하나의 작업이 끝나야 다른 작업을 시작할 수 있다는 걸로
비유할 수 있다. 이를 이용해 의존성이 있는 두 작업을 스케줄링 할 수 있다.
2. 사이클 유무 확인
-> 사이클이 있을 때 위상정렬을 사용할 수 없다는 건
위상정렬을 해봤을 때 제대로 된 결과가 나오지 않으면 사이클이 있다는 의미가 된다.
이를 통해서 사이클이 생기는지 안 생기는지 위상정렬로 확인할 수 있다.
3. 최단/최장 경로를 계산
-> 위상정렬로 각 노드를 위상정렬 순서로 처리하면서
다이나믹 프로그래밍(DP)를 적용해서 최단거리, 최장거리를 구할 수 있다.
위상정렬 기초 개념
진입차수: 노드로 들어오는 간선의 개수
진출차수: 노드에서 다른 노드로 나가는 간선의 개수
비순환 유향 그래프(DAG): 순환이 없으면서 방향이 있는 그래프
Directed Acyclic Graph
위상정렬을 쓸 수 있는 조건
비순환 유향 그래프(DAG)여야 한다.
비순환 유향 그래프인 경우 진입차수가 0인 그래프가 반드시 1개 이상
존재한다는 걸 보장하기 때문이다.
왜 보장하는 걸까?
우선 3개의 노드에서 사이클이 생긴다면 각 노드는 서로 맞물려서
진입차수가 각각 1이 된다.
즉 사이클이 있다면 사이클 속 모든 노드들은 진입차수가 최소 1 이상이 된다.
하지만 DAG인 경우 모든 노드에서 사이클이 생기지 않으므로
최소 1개 이상의 노드가 진입차수가 0이 되는 것이다.
위상정렬 알고리즘 흐름
- 진입차수 0인 노드를 찾는다.
- 진입차수 0인 노드와 연결된 간선을 지운다.
- 모든 노드가 지워질 때까지 1~2를 반복한다.
위상정렬 알고리즘
위상정렬은 구현하는 방법은 대표적으로 2가지가 있다.
1. Kahn Algorithm (!=Kuhn Algorithm)
2. DFS
위상정렬 예제문제
위상 정렬 예제문제가 궁금하다면 이 글을 읽어보길 바란다.
