코드 12-3에서 dfs() 메서드를 보면 마지막 라인에 있는 ts_list.append() 코드만 빼고는 일반적인 dfs와 같습니다. 이 코드가 어떻게 작동하는지 그림 12-3으로 살펴보죠.

▲ 그림 12-3 위상 정렬 1

임의의 한 노드 2에서 시작했다고 하겠습니다. 그럼 dfs()로 스택 프레임은 오른쪽 그림과 같이 쌓여 있을 것입니다. 그림은 단순화하고자 함수 이름은 생략했습니다. 함수 이름은 당연히 dfs입니다. 이때 노드 5에서 보니 진출 차수가 없습니다. 즉, 5번 일이 맨 마지막에 할 일이라는 것입니다. 이때 ts_list에 노드를 삽입합니다.