위상정렬

• 정의
  • 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
  • 항상 유일한 값으로 정렬되지 않는다
  • 시간 복잡도는 O(V+E)이다 (노드수 V, 에지 수 E)
• 핵심 이론
  • 
  • 
  • 진입차수는 자기 자신을 가르키는 에지의 갯수로, 그래프를 인접 리스트로 구현한 뒤, 실시간으로 진입 차수 배열을 초기화해준다
  • 
  • 진입 차수가 0인 노드를 선택 후 정렬 배열에 저장한 뒤, 인접리스트에 연결된 값의 진입 차수를 1씩 빼준다
  • 
  • 선택한 노드를 제외한 노드 중 진입 차수가 0인 노드를 다시 선택해준 뒤 위의 작업을 반복해준다
  • 이때 2,3번 노드의 값이 둘다 0이므로 어떤것이 먼저 배열에 들어가도 상관이 없으므로 항상 유일 값으로 정렬되지 않는것을 볼 수 있다
  • 
  • 모든 배열이 정렬되면 위와같은 결과를 볼 수 있다