Notice
Recent Posts
목록위상정렬 (1)
천천히 빛나는
알고리즘 : 위상 정렬
위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같이 나열하는 것을 위상 정렬이라고 한다. 위상정렬을 알기 전 다뤄야 하는 용어에 진입차수와 진출차수가 존재한다. 진입차수 (Indegree) 특정한 노드로 들어오는 간선의 개수 진출차수 (Outdegree) 특정한 노드에서 나가는 간선의 개수 동작 과정 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 예시 진입차수가 0인 노드가 존재하기 위해서는 사이클이 없는 그래프가 필요하다 [초기단계] 진압차수가 0인 모든 노드를 큐에 넣는다. [1] 큐에서 노드 ..
STUDY/ALGORITHM
2024. 2. 23. 01:47