Logseq/pages/위상 정렬(Topological Sort).md

deck:: Logseq/coding tip

• 1. 개념(Concept)

  • 정의 :-> 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 거스르지 않도록 나열하는 알고리즘. id:: 694a355c-b251-4b21-bcf0-1d19912a0150
  • 대상 : {{cloze 사이클이 없는}} 방향그래프 에서만 사용 가능 #card id:: 694a3575-2dc7-4567-ae8a-55f3b2f41c63 extra:: 사이클이 존재한다면 순서를 정할 수 없기 때문
  • 특징
    • 정답결과가 {{cloze 하나가 아닐 수도 있음}} #card extra:: 진입 차수가 0인 노드가 동시에 여러 개라면 선택 순서에 따라 결과가 달라짐 id:: 694a369e-6bc2-4e36-a9d3-cca9f3c2dc42
    • 모든 원소를 방문하기 전에 큐가 빈다면 {{cloze 사이클}} 이 존재하는 것입니다. id:: 694a36e1-53a9-4afa-be3d-a76239551547

• 2. 동작 원리 (Algorithm Flow)

  • 1) 순서

    • 위상 정렬은 주로 진입 차수(Indegree) 와 큐(Queue) 를 이용하여 동작함.
    • 1단계 : 진입차수 계산
      • 그래프의 모든 노드에 대해, {{cloze 자신을 향하는 간선의 개수( indegree )}} 를 미리 계산해 둡니다. id:: 694a3899-c5bb-4f46-9a5f-80dd8316d7fe
    • 2단계 : 초기 큐 설정
      • 진입 차수가 {{cloze 0}} 인 모든 노드를 큐에 넣습니다. #card extra:: 이 노드들이 바로 작업의 시작점이 됩니다. id:: 694a389e-1f99-497e-9f2f-d4574f634d87
    • 3단계 : 큐를 이용한 반복
      • 큐에서 노드를 하나 꺼내 결과 리스트에 추가.
      • 꺼낸 노드에서 출발하는 모든 간선을 제거. id:: 694a3884-ec0c-4308-9719-42ceea861a0d (실제로는 {{cloze 연결된 노드들의  indegree 를 1씩 감소시킴}} )
      • 이때 새롭게  indegree 가 0이 된 노드가 생기면, 즉시 큐에 추가합니다.
    • 4단계 : 종료 및 사이클 확인
      • 큐가 비면 모든 과정이 끝.
      • 만약 결과 리스트에 담긴 노드의 개수가 전체 노드 개수보다 적다면 ? #card id:: 694a38d5-9470-4258-abc0-f7dcdebe0267
        • 이는 사이클이 존재하여 모든 노드를 정렬할 수 없었음을 의미.

  • 2) 코드(python 기준)

    • 다음과 같이 초기화 되어 있을 때, topology_sort() 함수의 정의는 다음과 같다. id:: 694a390d-a75a-4fb7-80c4-5933ab1ea454

      from collections import deque
      
      # 노드 개수(v)와 간선 개수(e)
      v, e = 7, 8 # 예시
      
      # 진입 차수 배열 (모두 0으로 초기화)
      indegree = [0] * (v + 1)
      
      # 그래프 표현 (인접 리스트 방식)
      graph = [[] for _ in range(v + 1)]
      
      # 예시 간선 정보 (a -> b)
      # 1->2, 1->5, 2->3, 3->4, 4->6, 5->6, 6->7, 7->4(X)
      edges = [(1,2), (1,5), (2,3), (3,4), (4,6), (5,6), (6,7), (7,4)] # 7->4는 사이클 유발 가능성
      
      for a, b in edges:
          graph[a].append(b)
          indegree[b] += 1
      
      

      #card

      • def topology_sort():
            result = []
            q = deque()
        
            # 1. 진입 차수가 0인 노드를 큐에 삽입
            for i in range(1, v + 1):
                if indegree[i] == 0:
                    q.append(i)
        
            # 2. 큐가 빌 때까지 반복
            while q:
                now = q.popleft()
                result.append(now)
        
                # 3. 연결된 노드들의 진입 차수 감소
                for i in graph[now]:
                    indegree[i] -= 1
                    if indegree[i] == 0: # 새롭게 0이 되면 큐에 삽입
                        q.append(i)
        
            # 결과 출력
            print(*result)
        
        

• 3. 시간 복잡도

  • 시간복잡도는 {{cloze $O(V + E)$}} (V: 노드 수, E: 간선 수) #card extra:: 모든 노드를 한 번씩 큐에 넣고 확인하며(V), 그 과정에서 모든 간선을 한 번씩 확인(E)하여 진입 차수를 줄이기 때문. id:: 694a39c0-ff89-4801-8cb2-8e1297d62ccb

• 4. 사용 예시

  • 선수 과목(Prerequisite
    • 특정 과목을 들어야 다음 과목을 들을 수 있을 때 들어야 하는 과목 순서를 정렬하는 작업.
  • 프로젝트 일정 관리
    • A 작업이 끝나야 B 작업을 시작할 수 있는 스케줄링.