이제 테스트 코드를 작성하고 실행해서 결과를 보겠습니다.
코드 12-4
if __name__ == "__main__":
d = DAG(7)
d.add_edge(0, 4)
d.add_edge(1, 3)
d.add_edge(1, 4)
d.add_edge(2, 3)
d.add_edge(3, 5)
d.add_edge(3, 6)
d.add_edge(4, 2)
ts_list = d.topological_sort()
for i in ts_list:
print(i, end=" ")
코드 12-4의 그래프 d는 지금까지 살펴본 그림 속 예제입니다. 그래프를 만들고 topological_sort() 메서드를 호출하여 위상 정렬을 한 후 출력해 보면 다음 실행 결과를 얻을 수 있습니다.
1 0 4 2 3 6 5
Tip 위상 정렬은 어디에 쓰나요?
위상 정렬을 쓰는 곳을 찾다 보니 위키백과에서 재미있는 쓰임새를 발견했습니다. 스프레드시트에서 어떤 셀 값이 변경되었을 때 이 값에 의존하는 모든 셀 값을 업데이트할 수 있는데, 이때도 위상 정렬이 쓰인다고 합니다. 신기하네요.
다음 장에서는 그래프 알고리즘 중에서 중요한 위치를 차지하는 최소 비용 신장 트리를 알아보겠습니다.