1. 위상정렬 알고리즘
•
순서가 정해져있는 작업 을 순서대로 수행해야 할 때 그 순서를 정해주기 위해 사용하는 알고리즘
•
위상정렬은 DAG(Directed Acyclic Graph) == 사이클이 발생하지 않는 방향 그래프에만 적용 가능하다.
•
위상정렬 알고리즘은 ① 현재 그래프가 위상 정렬이 가능한지 ② 위상 정렬이 가능하다면 그 결과가 무엇인지 총 2가지에 대한 해결책을 준다.
2. 위상정렬 알고리즘의 동작방식
1.
진입차수(degree)가 0인 정점을 선택한다.
•
진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.
•
초기에 간선의 수가 0인 모든 정점을 큐에 삽입
2.
선택된 정점과 여기에 부속된 모든 간선을 삭제
•
선택된 정점을 큐에서 삭제
•
선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
3.
1 ,2의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료
Note. 만약 모든 원소를 반복하기 전에 큐가 비게 된다면 사이클이 존재하는 것이고, 모든 원솔르 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과가 된다.
3. 위상정렬 알고리즘 관련 예시
•
큐를 이용한 위상 정렬
◦
줄 세우기- 백준2252번
•
우선순위 큐를 이용한 위상 정렬
◦
문제집- 백준1766번
4. 위상정렬 알고리즘 동작 도식
5. 위상정렬 알고리즘 시간 복잡도
•
모든 정점과 간선에 대해서 작업
◦
노드 수: V
◦
간선 수: E
◦
시간 복잡도: O(V + E)
6. 위상정렬 알고리즘 구현 (BOJ 1766)
arr = [[] for _ in range(n + 1)]
degree = [0] * (n+1)
heap = []
result = []
for _ in range(m):
p1, p2 = map(int, input().split())
arr[p1].append(p2) # p1 다음에 p2를 풀어야함
degree[p2] += 1
for i in range(1, n+1):
if degree[i] == 0:
heapq.heappush(heap, i)
while heap:
cur = heapq.heappop(heap)
result.append(cur)
for i in arr[cur]:
degree[i] -= 1
if degree[i] == 0:
heapq.heappush(heap, i)
Python
복사
