그림 12-2를 보면 같은 그래프이지만 나열 순서가 다르지요. 그림 12-2에서 유의해서 볼 점은 모든 간선의 방향이 왼쪽에서 오른쪽이라는 것입니다. 오른쪽에서 왼쪽으로 오는 에지가 있다면 그것은 사이클이 있다는 것입니다.

위상 정렬을 구현해 보겠습니다. 먼저 그래프 표현부터 볼까요?¹

코드 12-1

class DAG:
    def __init__(self, vertex_num):
        self.adj_list = [[] for _ in range(vertex_num)]
        self.visited = [False for _ in range(vertex_num)]

    def add_edge(self, u, v):
        # u: tail, v: head
        self.adj_list[u].append(v)

코드 12-1은 DAG에 사용할 그래프입니다. 내부 표현은 인접 리스트를 이용할 것입니다. add_edge() 메서드를 보면 방향 그래프이므로 u가 꼬리, v가 머리입니다.