해당 포스팅은 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책을 기반으로 포스팅 하였습니다. ✍️✍️
그래프 알고리즘
그래프 알고리즘은 매우 다양한데, 코딩 테스트에서 출제 비중이 낮은 편이지만 제대로 알아야 하는 알고리즘이다.
그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 이루어져있는 자료구조이다. 따라서 서로 다른 객체가 연결되어 있다는 내용이 있으면, 그래프 알고리즘을 떠올려야 한다.
또한 트리 자료구조는 다양한 알고리즘에서 사용되므로 기억해두어야 한다.
다익스트라 최단 경로 알고리즘에서 사용되는 우선순위 큐를 구현할 때, 최소힙을 이용할 수 있는데, 이때 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다.
- 그래프 VS 트리 자료구조
| 그래프 | 트리 | |
|---|---|---|
| 방향성 | 방향 그래프 혹은 무방향 그래프 | 방향 그래프 |
| 순환성 | 순환 및 비순환 | 비순환 |
| 루트 노드 존재 여부 | 루트 노드가 없음 | 루트 노드가 존재 |
| 노드간 관계성 | 부모와 자식 관계 없음 | 부모와 자식 관계 |
| 모델의 종류 | 네트워크 모델 | 계층 모델 |
그래프를 표현하는 방식으로는 인접 행렬과 인접 리스트가 있다.
- 인접 행렬: 2차원 배열을 사용하여 그래프의 연결 관계를 표현
- 인접 리스트: 리스트를 사용하여 그래프의 연결 관계를 표현
노드의 개수가 V, 간선의 개수가 E인 그래프가 있다고 하자.
이때 인접 행렬을 이용하는 방식은 간선 정보를 저장하기 위해 O(V2)만큼의 메모리 공간을 사용한다. 반면, 인접 리스트를 이용할 때는 간선의 개수만큼인 O(E)만큼만 메모리 공간을 사용한다.
또한 인접 행렬은 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용을 O(1)의 시간으로 즉시 알 수 있다는 장점이 있지만, 인접 리스트를 이용할 때에는 O(V) 만큼의 시간이 소요된다.
다익스트라 최단 경로 알고리즘은 인접 리스트를 이용하고, 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식이다.
이때 주의해야 할 점은 어떤 문제를 만나든 메모리와 시간을 염두하고 알고리즘을 선택하여 구현해야 한다는 점이다.
예를 들어 최단 경로를 찾아야 하는 문제에서 노드의 개수가 적은 경우에는 플로이드 워셜 알고리즘을 이용하고, 노드와 간선의 개수가 모두 많으면 다익스트라 알고리즘을 이용하면 유리하다.
이제 다른 그래프 알고리즘들에 대해 알아보자.
서로소 집합
수학에서의 서로소 집합은 공통원소가 없는 두 집합을 의미한다.
서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 이 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다.
union(합집합) 연산은 하나의 집합으로 합치는 연산이다. find(찾기) 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다.
서로소 집합 자료구조는 합집합과 찾기 연산으로 구성된다. 따라서 union-find(합집합 찾기) 자료구조라고 불리기도 한다.
두 집합이 서로소 관계인지 확인하기 위해서는 각 집합이 어떤 원소를 공통으로 가지고 있는지를 확인하면 되기 때문이다.
서로소 집합 자료구조
서로소 집합 자료구조는 트리 자료구조를 이용하여 구현한다.
서로소 집합 계산 알고리즘은 다음과 같다.
-
union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다.
1-1. A와 B의 루트 노드 A', B' 를 각각 찾는다.
1-2. A'를 B'의 부모 노드로 설정한다. (즉, B'가 A'를 가리키도록 한다.)
-
모든 union 연산을 처리할 때까지 1번 과정을 반복한다.
실제 구현시에 더 작은 원소가 부모 노드가 되도록 구현하는 경우가 많으므로, 여기서도 그러한 방식으로 구현하였다.
이 알고리즘을 그림을 통해 더 직관적으로 이해해보자.
전체 집합이 {1, 2, 3, 4, 5, 6}으로 총 6개의 원소로 구성되어 있을 때, 다음과 같은 4개의 union 연산이 있다고 하자.
각 union 연산은 두 원소가 같은 집합이라는 의미를 가지고 있다.
-
step 0
초기 단계에서는 가장 먼저 노드의 개수 크기의 부모 테이블을 초기화한다.
이때 모든 원소가 자기 자신을 부모로 가지도록 설정한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 | 1 | 2 | 3 | 4 | 5 | 6 |
-
step 1
첫번째 union 연산을 확인하여, 1과 4를 합친다. 이때, 더 작은 원소가 부모가 되도록 설정한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 | 1 | 2 | 3 | 1 | 5 | 6 |
-
step 2
두번째 union 연산을 확인하여, 2와 3을 합친다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 | 1 | 2 | 2 | 1 | 5 | 6 |
-
step 3
세번째 union 연산을 확인하여, 2와 4을 합친다. 이때, 노드 2와 노드 4의 루트 노드인 1에서 더 작은 원소인 1이 노드 2의 부모가 되도록 설정한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 | 1 | 1 | 2 | 1 | 5 | 6 |
-
step 4
마지막 union 연산을 확인하여, 5와 6을 합친다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 부모 | 1 | 2 | 3 | 1 | 5 | 5 |
부모 테이블을 계속해서 확인하며, 이를 갱신해야 한다.
서로소 집합 알고리즘으로 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다.
결과적으로 최종 루트가 같은 것끼리 묶으면 다음과 같이 나누어진다.
이렇게 나뉘게 된 묶음끼리 서로소 집합이 되는 것이다.
기본적인 서로소 집합 알고리즘의 소스코드는 다음과 같다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
return find_parent(parent, parent[x])
return x
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1):
print(find_parent(parent, i), end=' ')
print()
# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v+1):
print(parent[i], end=' ')# 입력 예시
6 4
1 4
2 3
2 4
5 6# 출력 예시
각 원소가 속한 집합: 1 1 1 1 5 5
부모 테이블: 1 1 2 1 5 5이렇게 구현을 하는 경우, find 함수가 최악의 경우 모든 노드를 확인하여 시간 복잡도가 O(V)가 된다.
따라서 경로 압축 기법을 적용하면 시간 복잡도를 개선시킬 수 있다. 이를 구현하기 위해서는 기존의 find 함수를 다음과 같이 변경하면 된다.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]이렇게 수정하면, 각 노드에 대하여 find 함수를 호출한 후, 해당 노드의 루트 노드가 바로 부모 노드가 된다.
따라서 경로 압축 방법을 이용할 경우의 서로소 집합 알고리즘의 시간복잡도를 알아보자.
노드가 V개이고, 최대 V-1개의 union 연산과 M개의 find 연산이 가능할 때, 경로 압축 방법을 적용한 시간 복잡도는 O(V+M(1+log2-M/VV))라고 알려져 있다.
보다 더 시간 복잡도를 줄일 수 있는 방법들도 있지만, 코딩 테스트를 위해서는 이 정도로 충분하다고 한다. 그러므로 경로 압축을 이용한 서로소 집합 알고리즘의 코드는 꼭 기억하도록 하자.
이 서로소 집합 알고리즘을 사용하여 방향이 없는 그래프에서 사이클 존재 여부를 판별할 수 있다.
서로 다른 두 노드의 루트 노드를 확인하여 이들이 같으면 사이클이 발생했다고 보면 된다.
이에 대한 소스코드는 다음과 같다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
cycle = False
# union 연산을 각각 수행
for i in range(e):
a, b = map(int, input().split())
# 사이클이 발생한 경우 종료
if find_parent(parent, a) == find_parent(parent, b):
cycle = True
break
# 사이클이 발생하지 않았으면 합집합 수행
else:
union_parent(parent, a, b)
# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v+1):
print(find_parent(parent, i), end=' ')
if cycle:
print("사이클이 발생했습니다.")
else:
print("사이클이 발생하지 않았습니다.")# 입력 예시
3 3
1 2
1 3
2 3# 출력 예시
사이클이 발생했습니다.신장 트리
하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이라, 이러한 조건이 붙은 그래프를 신장 트리라고 하는 것이다.
오른쪽 그림이 왼쪽 그래프에서 가능한 신장 트리 중 하나이다.
왼쪽 그림은 "모든 노드가 서로 연결"이 되지 않았으므로 신장 트리가 아니다.
오른쪽 그림은 "사이클이 존재"하므로 신장 트리가 아니다.
크루스칼 알고리즘
최소한의 비용으로 신장 트리를 찾아야 할 때 사용하는 알고리즘을 "최소 신장 트리 알고리즘" 이라고 한다. 이 최소 신장 트리 알고리즘 중 대표적인 것으로는 크루스칼 알고리즘이 있다.
그리디 알고리즘으로 분류되는 크루스칼 알고리즘은 모든 간선에 대하여 정렬을 한 후, 가장 거리가 짧은 간선부터 집합에 포함시키는 방식으로 진행된다. 이때 사이클을 발생시킬 수 있는 간선의 경우, 집합에 포함시키지 않는다.
최소 신장 트리는 일종의 트리 자료구조이므로, 신장 트리에 포함되는 간선의 개수가 '노드의 개수-1'과 같다는 특징이 있다.
*트리 자료구조는 노드가 N개일 때, 항상 간선의 개수가 N-1개 이다.
구체적인 크루스칼 알고리즘은 다음과 같다.
-
간선 데이터를 비용에 따라 오름차순으로 정렬한다.
-
간선을 하나씩 확인하며, 현재의 간선이 사이클을 발생시키는지 확인한다.
2-1. 사이클이 발생하지 않으면, 최소 신장 트리에 포함시킨다.
2-2. 사이클이 발생하면, 최소 신장 트리에 포함시키지 않는다.
-
모든 간선에 대하여 2번의 과정을 반복한다.
다음 그래프의 최소 신장 트리를 구해보자.
| 간선 | (1, 2) | (1, 5) | (2, 3) | (2, 6) | (3, 4) | (4, 6) | (4, 7) | (5, 6) | (6, 7) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 29 | 75 | 35 | 34 | 7 | 23 | 13 | 53 | 25 |
-
step 0
모든 간선 정보를 빼내어 정렬을 수행한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
-
step 1
가장 짧은 간선을 선택한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 |
-
step 2 ~ 3
가장 짧은 간선을 선택한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 |
-
step 4
가장 짧은 간선을 선택한다. 이때, (6, 7)은 이미 step 2와 step 3에서 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 | step 4 |
-
step 5 ~ 6
가장 짧은 간선을 선택한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 | step 4 | step 5 | step 6 |
-
step 7
가장 짧은 간선을 선택한다. 이때, (2, 3)은 이미 둘 다 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 | step 4 | step 5 | step 6 | step 7 |
-
step 8
가장 짧은 간선을 선택한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 | step 4 | step 5 | step 6 | step 7 | step 8 |
-
step 9
가장 짧은 간선을 선택한다. 이때, (1, 5)은 이미 둘 다 포함된 노드들이므로, 이를 신장 트리에 포함하면 사이클이 존재하게 된다. 따라서 신장 트리에 포함하지 않게 처리한다.
| 간선 | (3, 4) | (4, 7) | (4, 6) | (6, 7) | (1, 2) | (2, 6) | (2, 3) | (5, 6) | (1, 5) |
|---|---|---|---|---|---|---|---|---|---|
| 비용 | 7 | 13 | 23 | 25 | 29 | 34 | 35 | 53 | 75 |
| 순서 | step 1 | step 2 | step 3 | step 4 | step 5 | step 6 | step 7 | step 8 | step 9 |
결과적으로 다음과 같은 최소 신장 트리를 찾을 수 있다.
이때, 간선들의 비용을 모두 더하면, 159로 최소 신장 트리를 만드는데 필요한 총비용이 된다.
크루스칼 알고리즘의 소스코드는 다음과 같다.
# 특정 원소가 속한 집합 찾기
def find_parent(parent, x):
# 루트 노드가 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
# 두 원소가 속한 집합 합치기
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
# 부모 테이블에서 부모를 자기 자신으로 초기화
for i in range(1, v+1):
parent[i] = i
# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위하여 튜플의 첫 원소를 비용으로 설정
edges.append((cost, a, b))
# 간선을 비용순으로 정렬
edges.sort()
# 간선을 하나씩 확인
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우, 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)# 입력 예시
7 9
1 2 29
1 5 75
2 3 35
2 6 34
3 4 7
4 6 23
4 7 13
5 6 53
6 7 25# 출력 예시
159크루스칼 알고리즘은 간선의 개수가 E 일 때, O(ElogE)의 시간 복잡도를 가진다. 크루스칼 알고리즘의 가장 오래 걸리는 부분은 간선 비용의 정렬 부분이며, 이 정렬의 시간 복잡도가 O(ElogE)이기 때문이다.
크루스칼 알고리즘에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘보다 작으므로 무시할 수 있다.
위상 정렬
위상 정렬은 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다.
이론적으로는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서를 나열하는 것이다.
그래프 상에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다.
위상 정렬을 알아보기 전에, 진입차수에 대해 알아야 한다.
진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다.
예를 들어, 컴퓨터공학과의 커리큘럼에는 선수과목이 정해져 있다고 하자. 총 3개의 과목으로 '알고리즘', '자료구조', '고급 알고리즘'이 있을 때, 각 과목을 노드로 표현하고, 선수관계를 간선으로 표현하면 다음과 같다.
'알고리즘'의 선수과목으로는 '자료구조'가 있으며, '고급 알고리즘'의 선수과목으로는 '자료구조'와 '알고리즘'이 있는 것을 확인할 수 있다.
구체적인 위상 정렬 알고리즘은 다음과 같다.
-
진입차수가 0인 노드를 큐에 넣는다.
-
큐가 빌 때까지 다음의 과정을 반복한다.
2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
즉, 큐가 빌 때까지 큐에서 원소를 계속 꺼내서 처리하는 과정을 반복한다.
이때 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다. 큐에서 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다.
사이클이 존재하는 경우에는 사이클에 포함되어 있는 원소들이 큐에 들어가지 못하기 때문이다.
그러나, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는 경우를 고려하는 경우가 많으므로, 여기서 또한 사이클이 발생하지 않는다고 가정하여 살펴볼 것이다.
다음 그래프의 위상 정렬을 구해보자.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 1 | 1 | 2 | 1 | 2 | 1 |
| 큐 | 노드 1 |
|---|
-
step 0
진입차수가 0인 노드를 큐에 넣는다. 현재 노드 1의 진입차수만 0 이므로, 큐에 노드 1만 삽입한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 1 | 1 | 2 | 1 | 2 | 1 |
| 큐 | 노드 1 |
|---|
-
step 1
큐에 들어있는 노드 1을 꺼내어, 노드 1과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 된 노드 2와 노드 5를 큐에 삽입한다. (처리된 노드와 간선은 점선으로 표시하였다.)
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 1 | 2 | 0 | 2 | 1 |
| 큐 | 노드 2, 노드 5 |
|---|
-
step 2
큐에 들어있는 노드 2을 꺼내어, 노드 2과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 된 노드 3을 큐에 삽입한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 2 | 0 | 1 | 1 |
| 큐 | 노드 5, 노드 3 |
|---|
-
step 3
큐에 들어있는 노드 5을 꺼내어, 노드 5과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 된 노드 6을 큐에 삽입한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 2 | 0 | 0 | 1 |
| 큐 | 노드 3, 노드 6 |
|---|
-
step 4
큐에 들어있는 노드 3을 꺼내어, 노드 3과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 되는 노드가 없으므로, 그냥 넘어간다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 큐 | 노드 6 |
|---|
-
step 5
큐에 들어있는 노드 6을 꺼내어, 노드 6과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 된 노드 4를 큐에 삽입한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 큐 | 노드 4 |
|---|
-
step 6
큐에 들어있는 노드 4를 꺼내어, 노드 4와 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 된 노드 7를 큐에 삽입한다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 큐 | 노드 7 |
|---|
-
step 7
큐에 들어있는 노드 7을 꺼내어, 노드 7과 연결되어 있는 간선들을 제거한다.
새롭게 진입차수가 0이 되는 노드가 없으므로, 그냥 넘어간다.
| 노드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 진입차수 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 큐 |
|---|
위 과정을 수행하는 동안, 큐에서 빠져나간 노드를 순서대로 출력한 것이 위상 정렬을 수행한 결과가 된다.
위상 정렬은 한 단계에서 새롭게 들어가는 원소가 2개 이상인 경우, 여러 가지의 답이 존재하게 된다.
위 예시의 경우에는 1 - 2 - 5 - 3 - 6 - 4 - 7 이외에 1 - 5 - 2 - 3 - 6 - 4 - 7 또한 답이 될 수 있다.
위상 정렬 알고리즘의 소스코드는 다음과 같다.
from collections import deque
# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v+1)
# 각 노드에 연결된 간선 정보를 담기위한 연결 리스트 초기화
graph =[[] for i in range(v+1)]
# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
a, b = map(int, input().split())
graph[a].append(b) # 정점 A에서 B로 이동 가능
# 진입차수를 1 증가
indegree[b] += 1
# 위상 정렬 함수
def topology_sort():
result = []
q = deque() # 큐 기능을 사용하기위한 deque 라이브러리 사용
# 진입차수가 0인 노드를 큐에 삽입
for i in range(1, v+1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft()
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상 정렬 수행 결과 출력
for i in result:
print(i, end=' ')
topology_sort()# 입력 예시
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4# 출력 예시
1 2 5 3 6 4 7위상 정렬의 시간 복잡도는 O(V+E)이다.
위상 정렬은 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선들을 차례대로 제거해야 한다. 따라서, 모든 노드와 간선을 전부 확인하므로 O(V+E)의 시간이 소요되는 것이다.
