[Algorithm/Python] 위상 정렬(Topology Sort)란?

2023. 4. 6. 15:30·🎯PS/Algorithm

들어가며

본 포스팅에서는 위상 정렬에 대해 소개합니다.


📌 위상 정렬이란?

위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 
 
 
특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다.
1️⃣ 진입차수가 0인 노드를 큐에 담습니다.
2️⃣ 큐가 비어있을 때까지 다음의 과정을 반복합니다.
- 1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다.
- 2 ) 진입차수가 0인 노드를 큐에 담습니다.
 
모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다. 
큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다.
 
1. 진입차수가 0인 노드 1을 큐에 담습니다.

노드1234567
진입차수0112121
큐노드 1

 
2. 큐에 담긴 노드 1을 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드1234567
진입차수0012021
큐노드 2노드 5

 
3. 큐에 담긴 노드 2를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드1234567
진입차수0002021
큐노드 5노드 3

 
4. 큐에 담긴 노드 5를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드1234567
진입차수0002001
큐노드 3노드 6

 
5. 큐에 담긴 노드 3를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드가 존재하지 않으므로 넘어갑니다.

노드1234567
진입차수0001001
큐노드 6

 
6. 큐에 담긴 노드 6를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드1234567
진입차수0000001
큐노드 4

 
7. 큐에 담긴 노드 4를 꺼내어, 해당 노드에서 출발하는 간선을 모두 그래프에서 제거합니다. 그 후 진입차수가 0인 노드를 큐에 담습니다.

노드1234567
진입차수0000000
큐노드 7

 
8. 큐에 담긴 노드 7을 꺼내고 출발하는 간선과 전입차수가 0인 노드가 존재하지 않습니다. 이렇게 큐에서 꺼내어진 노드 순서대로 출력하여 위상 정렬을 마칩니다.
 

✅[ CODE ]

"""
< 위상 정렬>
"""
from collections import deque

v, e = map(int, input().split())

indegree = [0] * (v + 1)
graph = [[] for _ in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1


def topology_sort():
    result = []
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=" ")


topology_sort()

 

☑️ 시간 복잡도

모든 노드를 확인하며 해당 노드와 연결된 간선을 제거해야 하므로 시간 복잡도 $O(V + E)$가 됩니다.


포스팅 내용에 오류 및 문제가 있는 경우, 댓글로 남겨주시면 감사하겠습니다.
파파파파파이이팅
 
출처) 이것이 코딩 테스트다 with Python

반응형
저작자표시 (새창열림)
'🎯PS/Algorithm' 카테고리의 다른 글
  • [Algorithm/Python] 크루스칼 알고리즘이란? || 최소 신장 트리
  • [Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?
  • [Algorithm/Python] 플로이드 워셜 알고리즘이란?
  • [Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra
dmaolon
dmaolon
프로그래밍을 공부한 내용을 기록하는 공간입니다.
  • dmaolon
    기록 남기기
    dmaolon
  • 전체
    오늘
    어제
    • ALL (260)
      • ➰ Series (5)
      • 🎯PS (168)
        • Algorithm (15)
      • ☕ Java (11)
      • 🍀 Spring Boot (29)
      • 💬 Database (9)
      • 🐣 Computer Science (14)
      • 👍 Daily (4)
      • 🎁ReactJS (4)
  • 인기 글

  • 최근 댓글

  • 최근 글

  • 태그

    프로그래밍
    파이썬
    프로그래머스
    Spring
    백준
    BFS
    dfs
    알고리즘
    자바
    코딩
  • hELLO· Designed By정상우.v4.10.1
dmaolon
[Algorithm/Python] 위상 정렬(Topology Sort)란?
상단으로

티스토리툴바