[그래프] 위상 정렬 (Topological Sorting) 알고리즘
위상정렬 알고리즘이란?정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이때 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능하다. 인접 리스트를 사용하면 시간 복잡도가 O(V+E)이고 인접 행렬을 사용하면 시간 복잡도가 O(V^2)이다. 위 DAG 그래프를 위상정렬하면 아래와 같이 여러 결과가 나올 수 있다.구현 방법진입차수를 이용한 BFS 방법과 재귀를 이용한 DFS 방법이 있다.BFS 방법알고리즘 설명진입차수 (in-degree) : 특정한 노드로 들어오는 간선의 개수진출차수 (out-degree) : 특정한 노드에서 나가는 간선의 개수(시작) 진입차수가 0인 정점을 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.큐에서 ..
