이번에는 1을 선택해 볼까요? 3은 방문했으니 남은 4를 방문한 상태가 다음 그림입니다.

▲ 그림 12-5 위상 정렬 2

그림 12-5에서 dfs(4) 스택 프레임에서 adj[4]={2}인데 2는 이미 방문했습니다. 그러므로 4도 ts_list에 append합니다. dfs(1)도 마찬가지이므로 3과 4를 이미 방문해서 ts_list에 추가하며 끝날 것입니다. ts_list={5, 6, 3, 2, 4, 1}입니다. 이제 방문하지 않은 노드는 0뿐입니다. dfs(0)에서 ts_list에 노드 0을 추가합니다. topological_sort에서 각 정점에 대해 모두 방문했으니 ts_list를 reverse로 바꾸어 줍니다. ts_list={0, 1, 4, 2, 3, 6, 5}가 될 것입니다. 위상 정렬된 결과이지요. 리스트 대신에 연결 리스트를 만들고 맨 앞에 노드를 추가하면 reverse 연산은 하지 않아도 됩니다.