위상 정렬 – 순서를 정해야 할 때 사용하는 그래프 알고리즘

2025. 4. 18. 15:00·Computer Science
목차
  1. 위상 정렬이란?
  2. 전제 조건: 사이클이 없어야 한다 DAGDAG
  3. 핵심 개념: 진입 차수 IndegreeIndegree
  4. 위상 정렬 알고리즘 BFS방식BFS 방식
  5. DFS로도 구현할 수 있을까?
  6. 위상 정렬 흐름 이해하기
  7. 사이클 탐지는 어떻게?
  8. 시간복잡도
  9. 정리
728x90

위상 정렬이란?

여러 작업이 있고, 어떤 작업은 다른 작업이 끝난 후에만 시작할 수 있을 때,
전체 작업의 합리적인 순서를 정리하는 방법입니다.

 

예를 들어:

  • 1학년 수학을 들어야 2학년 미적분을 들을 수 있고,
  • 미적분을 들어야 3학년 공업수학을 들을 수 있다면
    → 이 관계를 반영한 전체 수강 순서를 정해주는 게 위상 정렬입니다.

비유로 말하자면,

위상 정렬은 요리를 할 때, 어떤 재료를 언제 준비해야 할지를 알려주는 순서표와 같습니다.
감자 껍질을 벗기고 삶은 다음에야 감자 샐러드를 만들 수 있듯이,
"선행 과정이 끝난 후에만" 다음 단계로 넘어갈 수 있습니다.

 

이렇게 작업간의 선후관계가 존재하는 상황에서,

그 순서를 위배하지 않고 전체 작업을 나열하는 알고리즘이 바로 위상 정렬 TopologicalSortTopologicalSort 입니다.


전제 조건: 사이클이 없어야 한다 DAGDAG

위상 정렬이 가능한 그래프:

DAG DirectedAcyclicGraph — 방향이 있고 사이클이 없는 그래프

 

왜 사이클이 있으면 안 될까요?

ex: 

  • 과목 A → 과목 B → 과목 C → 과목 A 라는 관계가 있다면 
    → A를 들으려면 B  → C → A 무한 루프

이런 경우엔 논리적 모순이 생기므로,

위상 정렬은 항상 사이클이 없는 그래프에서만 가능합니다.


핵심 개념: 진입 차수 IndegreeIndegree

진입 차수란?

한 노드로 들어오는 화살표간선의 개수

 

진입 차수가 0이라는 건,

→ "아무도 이 작업을 선행 조건으로 요구하지 않는다"

→ 즉, 바로 실행 가능한 작업이라는 의미

위상 정렬은 바로 이 "진입 차수가 0인 노드" 부터 시작해

선후관계를 유지하며 그래프를 순서대로 정리합니다.


위상 정렬 알고리즘 BFS방식BFS 방식

전체 흐름 요약

1. 모든 노드의 진입 차수indegree를 계산한다.
2. 진입 차수가 0인 노드를 큐에 넣는다.
3. 큐에서 노드를 꺼낸다 → 결과에 추가
4. 꺼낸 노드와 연결된 노드들의 진입 차수를 1씩 줄인다.
5. 다시 진입 차수가 0이 된 노드는 큐에 넣는다.
6. 반복

 

Python 코드 구현

from collections import deque

def topological_sort(n, graph):
    indegree = [0] * (n + 1)

    # 1. 진입 차수 계산
    for u in range(1, n + 1):
        for v in graph[u]:
            indegree[v] += 1

    # 2. 진입 차수 0인 노드 큐에 추가
    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    result = []

    # 3. 큐 순회
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != n:
        raise ValueError("사이클 존재 – 위상 정렬 불가능")

    return result

DFS로도 구현할 수 있을까?

위상 정렬은 DFS 방식으로도 구현이 가능합니다.

DFS에서는 후위 순회post−order의 아이디어를 사용합니다.

def dfs_topo_sort(n, graph):
    visited = [False] * (n + 1)
    result = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)

    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i)

    return result[::-1]

위상 정렬 흐름 이해하기

예제 그래프

과목 1 → 2, 3
과목 2 → 4
과목 3 → 4

 

→ 가능한 수강 순서:

1 → 2 → 3 → 4  
또는  
1 → 3 → 2 → 4

 

이처럼 위상 정렬은 유일한 결과가 아닐 수 있으며,

조건을 만족하는 모든 순서 중 하나를 반환합니다.


사이클 탐지는 어떻게?

  • 위상 정렬 결과의 노드 개수가 전체 노드 수보다 적다면
    → 중간에 순서를 정할 수 없었던 노드=사이클가 있었던 것
    → 사이클 존재

시간복잡도

연산 복잡도
전체 알고리즘 V:노드수,E:간선수 OV+E

 

→ 매우 효율적이고 실무에서도 자주 사용됩니다.

정리

  • 위상 정렬은 선후관계가 있는 작업의 순서 결정 문제를 해결한다.
  • 전제 조건: 그래프는 사이클 없는 방향 그래프DAG 여야 한다.
  • 핵심 개념: 진입 차수, 큐, 순차적 노드 제거
  • BFS/DFS 둘 다 구현 가능하며, 대부분은 BFS 방식이 직관적이고 실전적이다.
  • 사이클이 있다면 정렬은 불가능하다 → 검출 가능
 
728x90
반응형
저작자표시 비영리 변경금지 새창열림

'Computer Science' 카테고리의 다른 글

플로이드–워셜 알고리즘 모든노드간최단경로구하기  0 2025.04.21
벨만-포드 알고리즘 Dijkstra를넘어서는그래프알고리즘  1 2025.04.21
백트래킹Backtracking - 조합, 순열, N-Queen  0 2025.04.18
Union-Find  0 2025.04.17
DPDynamicProgramming란?  0 2025.04.17
  1. 위상 정렬이란?
  2. 전제 조건: 사이클이 없어야 한다 DAGDAG
  3. 핵심 개념: 진입 차수 IndegreeIndegree
  4. 위상 정렬 알고리즘 BFS방식BFS 방식
  5. DFS로도 구현할 수 있을까?
  6. 위상 정렬 흐름 이해하기
  7. 사이클 탐지는 어떻게?
  8. 시간복잡도
  9. 정리
'Computer Science' 카테고리의 다른 글
  • 플로이드–워셜 알고리즘 모든노드간최단경로구하기
  • 벨만-포드 알고리즘 Dijkstra를넘어서는그래프알고리즘
  • 백트래킹Backtracking - 조합, 순열, N-Queen
  • Union-Find
Balang
Balang
음악 전공생의 개발일지
  • Balang
    Balang
    Balang
  • 전체
    오늘
    어제
  • 반응형
    • All Post 147
      • python 45
        • selenium 4
        • algorithm 9
        • Django 6
        • Pandas | Numpy 22
      • SQL 9
      • Data Engineer 29
      • Data Scientist 3
      • Data Analysis 9
      • Computer Science 35
      • Why? 15
      • 마음가짐 2
  • 인기 글

  • 최근 댓글

  • 최근 글

  • 250x250
  • hELLO· Designed By정상우.v4.10.3
Balang
위상 정렬 – 순서를 정해야 할 때 사용하는 그래프 알고리즘
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.