💡 Algorithm
위상정렬(Topology Sort)
date
May 4, 2023
slug
topology-sort
author
status
Public
category
💡 Algorithm
tags
그래프
summary
순서가 정해져있는 작업을 차례로 수행해야 할 때! BFS & DFS 둘 다 구현 가능
type
Post
thumbnail
위상정렬 Topology Sort
순서가 정해져있는 작업을 차례로 수행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘
모든 간선 E(u,v)에 대하여 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 됨
- 여러 개의 답이 존재할 수 있음
- DAG(Directed Acyclic Graph) : 사이클이 발생하지 않는 방향 그래프에만 적용 가능
→ 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음
구현 알고리즘 2가지
- BFS : In-degree, Queue
- DFS : Recursive, Backtracking
구현 1. BFS : In-degree, Queue
Algorithm
- 진입차수가 0인 정점을 큐에 삽입
- 큐에서 정점을 꺼내 해당 정점과 연결된 모든 간선을 제거
- 큐에서 정점을 꺼낼 때 따로 기록해둘것(이 순서가 정렬의 결과)
- 해당 간선의 끝에 있는 정점들의 차수 1씩 차감
- 간선 제거 후 진입차수가 0이 된 정점을 큐에 삽입
- 큐가 빌 때까지 2~3번 과정을 반복
- 이때, 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다는 뜻
- 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과
Data Structure
- List<T> : 정렬 결과를 저장할 리스트/배열
- visited[v] : 해당 정점의 방문 여부 저장
- in_degree[v] : 해당 정점으로 들어오는 간선의 총 개수
- Queue<> queue : BFS 수행을 위한 큐
해당 예시의 경우, 순서대로
in_degree : 0, 1, 2, 2, 1
Time Complexity
BFS 알고리즘을 사용하므로 기본적으로 O(V+E)
- 인접 리스트 사용 시 O(V+E)
- 인접 행렬 사용 시 O(V*V)
Simulation!!!
1. 진입차수가 0인 정점을 큐에 삽입
in_degree[0] = 0, 결과 T is empty
큐에 정점0 insert
2. 큐에서 정점을 꺼내 해당 정점과 연결된 모든 간선을 제거
정점0을 큐에서 꺼내어 결과 T에 append
정점0과 연결된 모든 간선 제거
- 정점1과 정점3의 차수가 1씩 내려감
3. 간선 제거 후 진입차수가 0이 된 정점을 큐에 삽입
차수가 0이 된 정점1을 큐에 삽입
4. 큐가 빌 때까지 2~3번 과정을 반복
큐가 빌 때까지 == 모든 정점의 차수가 0이고 모든 정점을 방문했을 때
static int[] in_degree; // 진입차수(=진입간선수) static boolean[] visited; static Queue<> queue; static Queue<> result; // 진입차수 초기화가 끝났다는 가정하에 for(Vertex v) { if(in_degree[v] == 0) { // 진입차수가 0인 정점들 모두 queue.add(v); // 큐에 삽입 } } while(!queue.isEmpty()) { // 큐가 빌 때까지 순회 Vertex v = queue.poll(); // 큐에서 하나 빼기 result.append(v); // 정렬 결과에 append for(Edge e : v) { // 정점 v에서 시작하는 모든 간선에 대해 if(visited[e.end] == false) { // 아직 방문하지 않은 간선이라면 in_degree[e.end]--; // 차수 빼기 if(in_degree[e.end] == 0) { // 차수가 0이 된다면 queue.add(e.end); // 큐에 삽입 } } } }
구현 2. DFS : Recursive & Backtracking
Algotirhm
- 모든 정점을 순회하며 방문하지 않은 정점에 대하여 DFS 수행
- DFS 수행 방식
- 하나의 정점에서 시작
- 방문표시를 하며 간선을 따라 다음 정점으로 DFS 방문
- 더 이상 방문할 간선이 없으면 스택에 정점을 추가하고, 백트래킹을 통해 이전 정점으로 이동하며 방문하지 않은 간선이 있는지 확인
- 방문 가능한 간선이 있다면 다시 간선을 따라 다음 정점으로 이동
- 모든 정점의 방문이 끝났다면 스택을 거꾸로 출력
DataStructure
- Stack<> : 더이상 갈 수 없는 정점 저장, 정렬 결과가 역순으로 저장되어있음
- visited[v] : 정점 v에 방문했는지 여부 저장
Time Complexity
DFS 시간복잡도 : O(V+E)
Simulation!!
1. 하나의 정점에서 시작하여 DFS 수행(방문표시하며)
2. 더이상 갈 수 없다면 Stack 에 추가
- F에서 더이상 갈 수 없기 때문에 Stack : F ← 추가
3. 백트래킹을 통해 이전 정점으로 이동하여 다시 1~2반복
- D에서 더이상 갈 수 없기 때문에 Stack : F D ← 추가
- B에서 더이상 갈 수 없기 때문에 Stack : F D B ← 추가
- A에서 다시 DFS(A→C→E) 간 후, E에서 더이상 갈 수 없으므로 Stack : F D B E ← 추가
4. 결과 : F D B E C A
static boolean[] visited; static Stack<> stack; dfs(Vertex v) { // 정점 v 방문 visited[v] = true; // 정점 v 방문처리 for(Edge e : v) { // v에서 시작하는 모든 간선에 대해 if(visited[e.end] == false) { // 간선 도착 정점을 아직 방문한 적 없다면 dfs(e.end); // 해당 도착 정점으로 dfs 재귀호출 } } // 모든 간선에 대해 dfs 호출이 끝난 후(더이상 갈 곳이 없다면) stack.append(v); // 현재 정점 append }
