위상정렬 Topological Sort

나무위키 위상정렬 이미지

위상정렬(Topological Sort)

?? 일반 순회와의 차이점

• ##의존성관계##를 지키며 순서를 찾음

  1. 위상정렬이란?

위상정렬은 방향 그래프(directed graph)에서 정점들을 선형으로 나열하되, 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 앞에 오도록 정렬하는 알고리즘. 즉, 방향 그래프의 정점들을 간선의 방향을 거스르지 않도록 일렬로 나열하는 것.

2. 위상정렬을 사용하는 조건

• 방향 그래프(Directed Graph): 반드시 방향이 있는 그래프
• 비순환 그래프(DAG - Directed Acyclic Graph)
• 가중치: 가중치는 위상정렬에 영향을 주지 않음.

3. 위상정렬의 원리

위상정렬의 핵심 아이디어는 진입차수(in-degree)

• 진입차수: 어떤 정점으로 들어오는 간선의 개수
• 진입차수가 0인 정점은 다른 정점에 의존하지 않으므로 언제든 처리할 수 있음
• 정점을 처리한 후, 그 정점에서 나가는 간선을 제거하면 다른 정점들의 진입차수가 감소
• 이 과정을 반복하면 모든 정점을 순서대로 처리할 수 있음

4. 위상정렬하는 방법

Kahn's Algorithm (BFS 기반)

1. 모든 정점의 진입차수를 계산  
2. 진입차수가 0인 정점들을 큐에 삽입  
3. 큐가 빌 때까지 반복:  
   - 큐에서 정점을 하나 꺼내어 결과에 추가  
   - 해당 정점에서 나가는 모든 간선을 제거  
   - 진입차수가 0이 된 정점들을 큐에 추가  
4. 결과 배열의 크기가 정점 수와 같으면 성공, 아니면 사이클 존재  

DFS 기반 방법

1. 각 정점에 대해 DFS 수행  
2. DFS에서 정점 방문이 완료되면 스택에 푸시  
3. 모든 DFS 완료 후 스택에서 pop하면서 위상정렬 결과 얻기  

5. 장점과 단점

장점

• 선형 시간 복잡도: O(V + E)
• 명확한 순서:
• 사이클 감지: 위상정렬 과정에서 사이클 존재 여부를 확인가능
• 구현이 비교적 간단:

단점

• 제한적 적용: 방향비순환그래프 에서만 사용 가능
• 유일하지 않은 결과: 여러 개의 올바른 위상정렬 결과가 존재할 수 있음
• 동적 변경 어려움:

6. 활용방안

• 프로젝트 스케줄링: 작업 간 의존성이 있는 프로젝트의 작업 순서 결정
• 컴파일 순서: 모듈 간 의존성에 따른 컴파일 순서 결정
• 대학 수강계획: 선수과목이 있는 과목들의 수강 순서
• 빌드 시스템: Makefile에서 파일 의존성에 따른 빌드 순서
• 패키지 매니저: 소프트웨어 패키지 설치 순서
• 데이터베이스: 외래키 제약조건을 고려한 테이블 생성/삭제 순서

7. 실제 예제

예제: 대학 수강계획

다음과 같은 과목 의존성이 있다고 가정합시다:

• 수학1 → 수학2 → 통계학
• 수학1 → 물리학
• 프로그래밍기초 → 자료구조 → 알고리즘
• 수학2 → 알고리즘

8. 복잡도

전체 시간복잡도: O(V + E)

# 모든 간선을 한 번씩 확인  
for u in graph:  
    for v in graph[u]:  
        indegree[v] += 1  
# 시간복잡도: O(E)  

# 모든 정점의 진입차수 확인  
for i in range(V):  
    if indegree[i] == 0:  
        queue.append(i)  
# 시간복잡도: O(V)