Dag2 [알고리즘] ep5-3+) 위상순서 찾기 문제) 주어진 방향그래프 G에 대해 다음과 같이 수행하는 프로그램을 작성하라.1. G가 방향 비싸이클 그래프(directed acyclic graph: DAG)면 위상순서(topological order)를 구해 인쇄.2. G에 방향 싸이클(directed cycle)이 존재하면 위상순서를 구할 수 없으므로 0을 인쇄. 힌트:이 문제의 경우 그래프를 인접리스트 구조로 표현하는 것이 시간 성능 면에서 유리하며 배열로 구현하는 편이 코딩에 용이하다.위상 정렬 알고리즘에는 두 가지 버전이 있다. 첫째 깊이우선탐색(DFS)을 응용하는 버전, 둘째 각 정점의 진입차수(in-degree)를 이용하는 버전이다. 본 문제 해결을 위해 두 번째 버전을 사용하라. 이 버전은 그래프 G가 DAG면 위상순서를 구하고 그렇지 .. 2024. 7. 24. [알고리즘] ep5-3) 방향그래프 ㅁ방향그래프(directed graph): 모든 간선이 방향간선인 그래프 응용: 일방통행 도로, 항공노선, 작업 스케줄링 방향 DFS 알고리즘에서, 네 종류의 간선이 발생한다1. 트리간선(tree edges): 새로운 정점 방문 시 사용되는 간선2. 후향간선(back edges): 현재 정점에서 이미 방문한 정점으로 돌아가는 간선3. 전향간선(forward edges): 조상의 정점에서 자손의 정점으로 향하는 간선4. 교차간선(cross edges): 같은 레벨 또는 다른 서브트리의 정점으로 향하는 간선 방향그래프 G의 두 정점 u와 v에 대해 만약 u에서 v로의 방향경로가 존재한다면, "u는 v에 도달한다(reach)" 또는 "v는 u로부터 도달 가능(reachable)하다"라고 말한다 방향그래프 G.. 2024. 7. 23. 이전 1 다음
