위상이란?
위상 수학(Topology)의 위상이다. 원소들의 상대적인 연결 관계, 순서 관계 등을 의미한다
수학적 관계로는 유한 집합 위의 부분 순서는 그 집합의 위상과 일대일로 대응한다
순서 관계 하나를 정의 하는 것과 위상 하나를 정하는 것이 완전히 같다는 말이다
예를 들어 순서 관계가 주어졌을 때 다음을 만족하는 부분집합 U를 열린 집합이라 정의할 시
x ∈ U이고 y ≤ x이면 y ∈ U
어떤 원소를 넣었으면 그보다 앞선 것들도 전부 들어있는 집합이란 의미
선행 조건이 모두 해당 집합에 들어가게 된다
위상 정렬에선?
마찬가지로 방향 그래프의 **모든 간선 (u, v)**에 대해 결과 배열에서 u가 v보다 앞에 오도록 정점을 일렬로 나열하는 것이 위상 정렬이다. 무조건 사이클이 없는(DAG) 그래프 여야 한다
사이클이 있다면
서로가 서로보다 앞에 있어야 하므로 모순이 생긴다
from collections import deque
def topological_sort(vertices, edges):
arr = [0 for _ in range(vertices)]
result = deque()
for edge in edges:
arr[edge[1]] += 1
for idx in range(len(edges)):
if edges[idx][0] not in result:
result.append(edges[idx][0])
arr[edges[idx][1]] -= 1
if arr[edges[idx][1]] == 0:
result.append(edges[idx][1])
return list(result)
# 테스트 케이스
if __name__ == "__main__":
# 과목 선수과목 예제
vertices = 4
edges = [
(0, 1), # 0 → 1
(0, 2), # 0 → 2
(1, 3), # 1 → 3
]
print("=== 위상 정렬 ===")
print("과목 관계:")
print(" 0(기초) → 1(중급) → 3(고급)")
print(" 0(기초) → 2(응용)")
print()
result = topological_sort(vertices, edges)
print(f"수강 순서: {result}")
위의 코드를 설명하면
arr 배열이 일종의 차수를 저장한 곳이 되게 된다. 일렬로 정점을 펼친다 했을 때 같은 우선순위를 갖는 정점에 대한 문제 해결을 위함이다
그리고 진행하게 되면 만약 특정 Edge에 차수 조건이 맞게 되고 선행 차수 조건을 0으로 만들 경우 해당 조건이 발동 될 때 그 정점에 대한 확인을 진행하는 도중이기 때문에 Result 배열에 집어넣게 된다
이 경우 만약 아직 차수가 0이 되지 않았거나 해당 시작 정점이 도착한 적이 있다면 그냥 지나가게 된다
위상 정렬의 장단점
장점
- V + E에 비례해 끝나게 된다 (선형 시간)
- 어려운 문제를 쉽게 풀게 해준다
- 최장 경로 문제의 경우 일반 그래프에서는 NP-난해이다
- 하지만 위상 순서를 갖는 경우는 한 번의 순회로 해결된다
- 사이클 검출을 함께 할 수 있다
- 구현이 단순하다
단점
- 적용 범위가 DAG로 한정된다
- 답이 유일하지 않을 수 있다
