나는 Skienna의 알고리즘에 관한 책을 언급하고 있습니다.DAG에서 해밀턴 경로를 찾는 알고리즘
그래프 G가 Hamiltonian path를 포함하는지 여부를 테스트 문제는 해밀턴 경로 P 회만 각 정점을 방문하는 경로는 NP-hard이다. 해밀턴 순환 문제와는 달리 종점에서 P의 시작 꼭지점까지 G에서 모서리가있을 필요는 없습니다.
지향 비순환 그래프 G (DAG)가 주어진 경우, 해밀 토니안 경로가 포함되어 있는지 여부를 테스트하기 위해 O(n + m) 시간 알고리즘을 제공하십시오.
내 접근,
나는 DFS 및 Topological sorting을 사용할 계획입니다. 그러나 문제를 푸는 두 가지 개념을 어떻게 연결해야할지 몰랐습니다. 어떻게 토폴로지 정렬을 사용하여 솔루션을 결정할 수 있습니까?
제안 사항?
O (n + m)에서 DAG (토폴로지별로 정렬 할 수있는 모든 DAG)를 먼저 토폴로지별로 정렬 할 수 있습니다.
일단 이것이 끝나면 가장자리가 더 낮은 색인 정점에서 더 높은 정점으로 이동한다는 것을 알게됩니다. 연속 된 꼭지점 사이에 모서리가있는 경우에만 해밀턴 경로가 존재 함을 의미합니다.
(1,2), (2,3), ..., (n-1,n).
(해밀 토니안 경로에 당신이 "위로"수 없기 때문이고 아직 모든를 방문, 그래서 유일한 방법은 "건너 뛸"하는 것입니다)
당신은이를 확인하실 수 있습니다 O (n)의 조건.
따라서 전체 복잡도는 O (m + n)입니다.
@agassaa의 진술이 완전히 정확하다고 생각하지 않습니다. 노드 "A", "B", "C"및 모서리 A -> B, B -> C, A -> C가있는 간단한 예제를 생각해보십시오. A가 두 자녀를두고 C가 두 부모를 갖는 반면, A -> B -> C는 해밀턴 경로를 형성합니다. 경로가 해밀턴 인 경로에 대해 그래프의 모든 에지를 트래버스 할 필요는 없습니다.
@Peter Ivanov 고맙습니다! – user2302617
그러나 그래프가 연결되어 있다고 가정했는데, 연결이 끊긴 그래프에 대한 위상적인 정렬이있을 수 없습니까? – shinzou
그래프가 연결되어 있다고 가정하지 않습니다. 그래프가 연결되어 있지 않으면 해밀턴이 없으며 적어도 하나의 연속 된 꼭지점이 연결되지 않기 때문에이 알고리즘이이를 감지합니다 (그렇지 않으면 그래프가 연결될 것입니다).). –