목록Topological Sort (1)

Patrick's Devlog

[Algorithm] 위상 정렬(Topological Sort)

1. 위상 정렬 방향 그래프의 정점(vertex)들의 방향(순서)에 거스르지 않도록 나열하는 것을 의미한다. 순서가 정해져있는 작업들이 존재한다고 가정해보자. 특정한 작업을 수행하고 싶을 때, 그 작업을 바로 수행하는 것이 아닌 해당 작업을 위한 선행 작업을 해야한다. 이때, 작업들의 순서를 결정하는 알고리즘이 위상 정렬 알고리즘이다. 2. 수행 과정 자기 자신이 가리키는 방향이 없는 정점(진입 차수가 0인 노드)을 찾음 찾은 정점을 출력 후, 출력한 정점과 해당 정점에서 출발하는 간선을 삭제 아직 그래프에서 정점이 남아있으면 처음으로 돌아가고 아니면 알고리즘 종료 수행 과정을 예시로 들어보자. 아래의 그래프가 존재한다고 가정하자. 참고로 이 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 예시로..
Study/Algorithms & Data Structure 2024. 1. 22. 17:29
이전 Prev 1 Next 다음