그래프를 트래버스하는 선형 시간 알고리즘 개발

Question

알고리즘 기술을 향상시키기 위해 알고리즘 교과서를 사용하고 있지만이 질문에 완전히 얽매이고 나에게 괴롭 히고 있습니다. 기본 데이터 구조는 그래프라고 생각하지만이 문제로 어디서부터 시작해야할지조차 알지 못합니다. 아무도 통찰력을 줄 수 있습니까? 감사합니다

당신은 지형 두 이웃 도시 사이의 직접 도로를 따라 최대 고도 를 제공하는지도, 두 개의 도시 a와 b를 부여됩니다. 최대 고도를 최소화하는 s에서 t까지 경로를 찾는 선형 시간 알고리즘을 생각해 내십시오. 도로는 양쪽 방향으로 가로 지르는 이 될 수 있습니다.

Answer 1

이것은 까다로운 질문입니다. 나는 당신을 해결책으로 인도하기로되어있는 장에 몇 가지 힌트가 있다고 가정 할 것이다.

설명하는 문제는 미니 맥스 경로 문제 또는 가장 넓은 경로 문제입니다. http://en.wikipedia.org/wiki/Widest_path_problem

위키 백과에 따르면 선형 시간 알고리즘이 있지만 꽤 복잡하기 때문에이 책에서 알아낼 것으로 예상됩니다. 이 문제를 해결하는 더 간단한 방법은 최소 스패닝 트리를 찾는 것입니다. 최소 스패닝 트리의 "min cut"속성으로 인해 최소 스패닝 트리를 따라 a와 b를 연결하는 경로는 minimax 속성을 가지므로이 경로의 최대 고도는 a와 b를 연결하는 경로의 최소값이됩니다 .

그러나 선형 시간 최소 스패닝 트리 알고리즘은 없습니다. 다른 한편으로, 그래프가 평면 인 것으로 가정 할 수 있다면 (로드맵이므로 가능할 수 있음) 선형 시간에 최소 스패닝 트리를 찾는 것이 가능합니다. 그래서 나는 이것이 그들이 후에있을 것이라고 생각합니다. 이 문제를 포함하는 장에서 최소 스패닝 트리 및/또는 평면 그래프에 대해 이야기합니까?