Notice
Recent Posts
천천히 빛나는
알고리즘 : 위상 정렬 본문
위상 정렬
사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
위와 같이 나열하는 것을 위상 정렬이라고 한다.
위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다.
진입차수 (Indegree)
특정한 노드로 들어오는 간선의 개수
진출차수 (Outdegree)
특정한 노드에서 나가는 간선의 개수
동작 과정
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다
예시
진입차수가 0인 노드가 존재하기 위해서는 사이클이 없는 그래프가 필요하다
[초기단계] 진압차수가 0인 모든 노드를 큐에 넣는다.
[1] 큐에서 노드 1을 꺼낸 뒤에 노드 1에서 나가는 간선을 제거한다. 새롭게 진입차수가 0이 된 노드들을 큐에 삽입한다.
[2] 큐에서 노드 2를 꺼낸 뒤에 노드 2에서 나가는 간선을 제거한다. 여기서 노드 2가 아니라 노드 5부터 꺼내도 된다.
이러한 과정을 반복하면 위상 정렬을 수행한 결과를 알 수 있다.
한 번 큐에 삽입된 노드는 다시 들어가지 않으며 각 노드의 인접 간선을 모두 확인하기 때문에 연산 횟수는 V+E가 된다. 즉 시간복잡도는 O(V+E)가 된다.
위상 정렬은 DAG(DIrect Acyclic Graph)인 순환하지 않는 방향 그래프에서만 가능하다. 위상 정렬에는 여러가지 답이 존재할 수 있으며 (큐에 새롭게 들어가는 값이 2개 이상인 경우) 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다.
import java.util.*;
public class Main {
// 노드의 개수(V)와 간선의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
public static int v, e;
// 모든 노드에 대한 진입차수는 0으로 초기화
public static int[] indegree = new int[100001];
// 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// 위상 정렬 함수
public static void topologySort() {
ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
Queue<Integer> q = new LinkedList<>(); // 큐 라이브러리 사용
// 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for (int i = 1; i <= v; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
// 큐가 빌 때까지 반복
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));
}
}
}
// 위상 정렬을 수행한 결과 출력
for (int i = 0; i < result.size(); i++) {
System.out.print(result.get(i) + " ");
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= v; i++) {
graph.add(new ArrayList<Integer>());
}
// 방향 그래프의 모든 간선 정보를 입력 받기
for (int i = 0; i < e; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b); // 정점 A에서 B로 이동 가능
// 진입 차수를 1 증가
indegree[b] += 1;
}
topologySort();
}
}
자바로 구현한 위상 정렬 알고리즘이다. 앞서 말했듯이 시간복잡도는 O(V+E)가 된다.
'STUDY > ALGORITHM' 카테고리의 다른 글
알고리즘 : LCS (최장 공통 부분수열) (0) | 2024.04.25 |
---|---|
알고리즘 : 최단 경로 알고리즘 (3) - 기초 문제 풀이 (미완성!!!) (0) | 2024.02.23 |
알고리즘 : 최단 경로 알고리즘 (2) - 플로이드 워셜 알고리즘 (0) | 2024.02.23 |
알고리즘 : 최단 경로 알고리즘 (1) - 다익스트라(Dijkstra) 알고리즘 (Java로 구현) (0) | 2024.02.23 |
알고리즘 : 다이나믹 프로그래밍 (Dynamic Programming) (2) - 기초 문제 풀이 (C++로 구현) (0) | 2023.10.20 |