Topological Sort1 [알고리즘] ep5-3+) 위상순서 찾기 문제) 주어진 방향그래프 G에 대해 다음과 같이 수행하는 프로그램을 작성하라.1. G가 방향 비싸이클 그래프(directed acyclic graph: DAG)면 위상순서(topological order)를 구해 인쇄.2. G에 방향 싸이클(directed cycle)이 존재하면 위상순서를 구할 수 없으므로 0을 인쇄. 힌트:이 문제의 경우 그래프를 인접리스트 구조로 표현하는 것이 시간 성능 면에서 유리하며 배열로 구현하는 편이 코딩에 용이하다.위상 정렬 알고리즘에는 두 가지 버전이 있다. 첫째 깊이우선탐색(DFS)을 응용하는 버전, 둘째 각 정점의 진입차수(in-degree)를 이용하는 버전이다. 본 문제 해결을 위해 두 번째 버전을 사용하라. 이 버전은 그래프 G가 DAG면 위상순서를 구하고 그렇지 .. 2024. 7. 24. 이전 1 다음
