728x90
위상 정렬(Topology Sort)
위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 즉, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것
이다.
사용 예시
- 선수과목을 고려한 학습 순서 설정
- A 과목을 수행하고 B 과목을 수강하는 것을 권장할 때, A, B 를 각각 노드로 표현하고 A -> B 로 가는 방향을 갖는 간선을 그린다.
- 즉, 그래프 상에서
선, 후 관계
가 존재하면 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.
진입 차수(Indegree)
진입 차수(Indegree)란 특정한 노드로 들어오는 간선의 개수를 의미한다. A -> B, B -> C, D -> B
의 관계를 가질 때 B 에 대한 진입 차수는 2이다.
동작 과정
- 진입 차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
Tip
- 모든 원소를 방문하기 전 큐가 빈다면 사이클(cycling)이 존재한다고 볼 수 있다.
- 보통 위상 정렬을 사용하라고 낸 문제들은, 사이클이 발생하지 않는다고 명시하는 경우가 많다.
위상 정렬을 수행한 결과는 큐에서 빠져나간 노드를 순서대로 출력하면 된다. 위 그래프의 결과로는 1-2-5-3-6-4-7
과 1-5-2-3-6-4-7
이 정답이 된다.
구현
public class Main {
private static int vertexCount; // 노드의 개수
private static int edgeCount; // 간선의 개수
private static int[] indegree; // 모든 노드에 대한 진입 차수
private static List<List<Integer>> graph = new ArrayList<>(); // 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
private static List<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과 리스트
public static void main(String[] args) {
input();
topologySort();
output();
}
private static void input() {
Scanner sc = new Scanner(System.in);
vertexCount = sc.nextInt();
edgeCount = sc.nextInt();
indegree = new int[vertexCount + 1];
// 그래프 초기화
for (int i = 0; i <= vertexCount; i++) {
graph.add(new ArrayList<>());
}
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < edgeCount; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b); // A 노드에서 B 로 이동
indegree[b] += 1; // 진입 차수 1증가
}
}
private static void topologySort() {
Queue<Integer> Q = new LinkedList<>();
// step 0. 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= vertexCount; i++) {
if (indegree[i] == 0) {
Q.offer(i);
}
}
// step N. 큐가 빌 때까지 반복
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));
}
}
}
}
private static void output() {
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i) + " ");
}
}
}
위상 정렬의 시간 복잡도는 모든 노드와 간선을 확인한다는 점에서 O(V + E)
이다.
$$O(V + E)$$
References
728x90
'Algorithms > 기본 지식' 카테고리의 다른 글
부분 집합 구하기(DFS) (0) | 2022.01.03 |
---|---|
깊이 우선 탐색(DFS) (0) | 2022.01.03 |
신장 트리와 크루스칼 알고리즘 (0) | 2021.12.13 |
서로소 집합 (0) | 2021.12.12 |
플로이드 워셜 알고리즘 (0) | 2021.12.12 |