소피it블로그

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수 진출 차수(Outdegree): 특정 노드에서 나가는 간선의 개수 2. 큐를 이용하는 위상 정렬 알고리즘 진입 차수가 0인 모든 노드를 큐에 담는다. 큐가 빌 때까지 다음을 반복한다: 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거함 새롭게 진입 차수가 0이 된 노드를 큐에 넣음 결과적으로는, 각 노드가 큐에 들어온 순서와 위상 정렬을 수행한 결과가 동일하다. 위상 정렬에는 여러 가지 답이 존재할 수 있다. 모든 원소를 방문하기 전에 큐가 빈다면? 사이클..