목록정렬 (1)

If at first you don't succeed, try again

[알고리즘] 위상 정렬 알고리즘(Python)

* 개요 위상정렬은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이란, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬 알고리즘을 알기 위해서는 먼저 진입 차수(Indegree)를 알아야 한다. 진입 차수란 특정한 노드로 들어오는 간선의 개수를 뜻한다. 방향 그래프에서 위상 정렬을 수행하는 절차는 다음과 같다. 진입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다.(3 -> 4, 3 -> 4, ...) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에..
Computer Science/알고리즘(Python) 2022. 11. 25. 21:06
이전 Prev 1 Next 다음