위상 정렬

정렬이라고 해서 마치 리스트의 정렬 알고리즘 처럼 값의 크기에 따라 각 값들을 정렬하는 것으로 착각할 수 있다. 하지만 이 개념과 혼동하지 않고 완전히 다른 시각으로 바라보아야 한다. 위상 정렬이란 사이클이 없는 방향 그래프에서 모든 노드를 방향성에 거스르지 않고 순서대로 나열하는 방법이다. 즉 모든 노드를 순회하되 방향성에 맞게 순회하는 방법이라고 생각하면 된다. 그래프에서 이 방법이 왜 필요할까? 예를들어 적분을 학습하기 위해서는 미분을 선행으로 학습해야하고, 미분을 학습하기 위해서는 공통수학을 선행학습해야 한다. 결과적으로 그래프 내에서 특정 정점부터 적분까지 도달할 수 있는 경로는 여러 가지가 있을 것이다. 그 중에 루트(진입차수가 없는)노드를 기준으로 하나의 정점인 적분이 기준이 되었을 때, 어떤 노드로 부터 연결되었는지를 알아내는 방법이라고 볼 수 있다.

알고가야할 용어

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수