BFS를 두 번 사용하여 undirected unweighted graph의 직경이나 최대 거리를 찾을 수 있다는 것을 알고 있습니다. 제 질문은이 알고리즘의 특성에 관한 것입니다.BFS 구현을 통한 최대 거리?
만약 내가 이것을 구현했다면 필자는 문자 그대로 BFS를 두 번하고 최대 거리를 반환 할 것입니까? 또는 각 노드에 대한 거리 및 가중치를 BFS 알고리즘을 통해 설정하고 새 max가 이전 max보다 큰지 등을 계산해야합니까? 내가 BFS를 사용한다면 원래 방문한 값이 원래 노드의 최대 거리가 될 것이라는 말을 들었 기 때문에 모든 작업을 수행 할 필요가 없습니다.
각 노드에서 BFS n 번 실행해야합니다. 거리가 항상 0에서 계산되어야합니다. 어떤 노드의 거리는 다른 노드 v에서 bfs를 실행할 때 아무런 의미가 없으므로 완전히 재 계산해야합니다.
이제 각 노드에 대해 v 다른 노드에 최대 거리를 저장합니다. 그래프의 지름은 최대 값입니다.
그러나 귀하의 의견에서 알 수 있듯이 일반 그래프가 아닌 트리에 대한 문제를 해결하고 있습니다. 나무의 경우, 더 간단합니다. 모든 노드에서 BFS를 실행하십시오. v. 에서 가장 먼 노드를 찾습니다. v; d1으로합시다. 이제 노드 d1에서 BFS를 다시 실행하고 가장 먼 노드를 찾으십시오. 그것을 d2으로합시다. 그런 다음 d1에서 d2까지의 경로는 트리 (그 중 하나)의 직경입니다. 답변에 this 질문에 대한 답이 있습니다.
이 두 BFS는 여전히 처음부터 모든 거리를 계산합니다. 그래서 예, BFS를 두 번 실행해야합니다.
그래서 그래프의 경우 모든 노드에 대해 BFS를 수행 한 다음 가장 큰 거리가 직경이됩니까? – dshawn
첫 문장이 틀림 없음을 확신합니다. – user3386109
그것은 무엇입니까? 어쩌면 나는 그것을 잘못 이해하고있다, 내가 이것을 배웠던 사이트는 "우리는 두 개의 BFS를 사용하여 가장 긴 경로를 찾을 수있다. 아이디어는 다음 사실에 기반한다 : 어떤 노드 x에서 BFS를 시작하고 가장 긴 노드를 찾으면 x와의 거리가 가장 긴 경로의 종점이어야하며, 모순을 사용하여 증명할 수 있으므로 알고리즘이 간단한 두 개의 BFS로 축소됩니다. 첫 번째 BFS는이 경로에서 가장 긴 경로의 끝점과 두 번째 BFS를 찾습니다. 실제 가장 긴 경로를 찾으십시오. " – dshawn