위상순서3 [알고리즘] ep7) 최단경로 ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제최단경로길이: 간선들의 무게 합 응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 [최단경로 속성 2가지]속성1)최단경로의 부분경로(subpath) 역시 최단경로이다 속성2)출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path) - 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다- 최단경로트리(shortest path tree)는 루트.. 2024. 7. 26. [알고리즘] 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 다음
