그래프에서 가장 긴 경로를 찾는 방법은 무엇입니까?

Question

우리는 형식의 인접리스트를 부여

U -> (U,V,C) -> (U,V,C) ... 
U2 -> ... 
U3 -> ... 
. 
. 
etc 

(U,V,C) 따라서 포함 된 노드들이 비용 C.

주어진 인접리스트는 N 단일 연결 트리입니다와 V에 U에서 가장자리가 있다는 뜻 N-1 개의 가장자리.

노드 세트 F=F1,F2,F3...Fk이 제공됩니다.

이제는 F 노드의 가장 긴 경로를 찾는 가장 좋은 방법은 무엇입니까? O (N)에서 가능합니까?

F의 각 노드에서 오는 DFS가 유일한 옵션입니까?

Answer 1

나는이 두 노드 사이의 고유 경로가 가능한 한 길게되도록 집합 F에서 노드 쌍을 찾으라는 질문을 이해했습니다. 그래프가 나무이기 때문에 경로가 고유합니다.

문제는 언급로서 n은 그래프 (k)의 크기 인 O (NK) 용액에 대해, F의 모든 노드에서 DFS를 수행하여 사소 해결 세트의 크기가 될 수 F.

그러나 분할 및 정복 방식을 사용하면 잠재적으로 더 빨리 해결할 수 있습니다. 그래프에서 임의의 노드 R을 선택하고 하나의 DFS를 사용하여 다른 모든 노드 aa와의 거리 Dist (R, a)를 산정하고 동시에 노드를 하위 트리 S1, ..., Sm으로 분할합니다. 여기서 m은 R에서 가장자리; 즉, 이들은 루트 R에 매달려있는 m 개의 나무입니다. 이제는 서로 다른 하위 트리에 속하는 모든 f와 g에 대해 Dist (R, f) + Dist (R, g) 모서리가 있으므로 그 사이의 경로가 유지됩니다. O (k^2) 시간에서 가장 긴 경로를 탐색 할 수 있습니다. 또한 S1, ..., Sm의 하위 문제를 되풀이하여 최장 경로가 해당 트리의 내부에있는 경우를 처리해야합니다. 전반적인 복잡도는 O (n k)보다 낮을 수 있지만 수학은 독자에게 운동으로 남겨 둡니다.

Answer 2

질문을 올바르게 이해했다면 스패닝 트리에서 가장 긴 비용 경로를 찾으려고합니다.

당신이 단계 이하로해야 N.

의 큰 값 단지 2 완전한 탐색 즉, O (2N) ~ O (N)의 경로를 찾을 수 있습니다.

1. 스패닝 트리에서 노드를 선택하십시오.
2. 노드에서 algo (DFS 또는 BFS)를 실행하고이 노드에서 가장 긴 비용 경로를 찾으십시오.

무작위로 노드를 선택하여 시작한 경우 비용이 가장 많이 소요되는 경로가 아닙니다.

는 는

2 단계
1. 이 시간 당신이 얻을 가장 긴 비용 경로에서 발견 긴 비용 경로 의 마지막 노드에서
2. 실행 BFS 또는 DFS 한 번 더, 가장 긴 것 스패닝 트리의 경로는 입니다.

각 노드에서 DFS를 실행할 필요가 없습니다.