그래프이론 파이썬 (1) 썸네일형 리스트형 [알고리즘] - 위상정렬 Topology Sort 정렬 알고리즘의 일종인 위상정렬 알고리즘은 '순서가 정해져 있는 일련의 작업을 수행할때' 사용하는 알고리즘이다. 즉 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것을 위상정렬이라고 한다. 예를들면 선수과목을 생각하면 편하다. B라는 과목을 듣기 위해서 A라는 과목을 필수로 들어야 한다는 것과 동일하다. 즉 순서가 정해져있는 일련의 작업을 의미하게 된다. Toplogy Sort Algorithm 위상정렬 알고리즘은 다음 순서로 동작한다. - 진입차수가 0인 노드를 큐에 넣음 - 큐가 빌때까지 다음 과정을 반복 - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 - 새롭게 진입차수가 0이 된 노드를 큐에 넣음 만약 이 과정에서 모든 원소를 .. 이전 1 다음
