0
노드의 최대 거리를 노드의 노드와 트리의 다른 모든 노드 사이의 거리 중 최대 값으로 정의하십시오. . 내 문제는 트리 내에서 모든 노드의 최대 거리를 찾아서 인쇄하는 것입니다 (반드시 바이너리가 아닌). 기본적으로 각 노드마다, 우리가보고있는 노드와 트리 내의 다른 노드 사이에 노드가 가지고있는 최대 거리를 출력해야합니다. 런타임은 O (n) 일 것으로 예상됩니다.트리의 모든 노드에 대한 최대 거리를 선형 시간으로 찾으십시오.
내가 가장 잘 접근하는 방법은 모두 O (N^2) 시간이 걸리고이 문제를 해결할 수있는 다른 방법이 무엇인지 알지 못합니다. 나는 현재 트리의 각 노드에서 BFS를 실행하여 트리의 각 노드에 대한 최대 거리를 찾고 있지만 더 나은 방법은 동적 프로그래밍의 일부 형식을 사용하는 것입니다. 나는 확실하지 않다.
사전에 도움을 주셔서 감사합니다.
당신이 물어 보는 질문은 여기에서 대답하는 http://stackoverflow.com/questions/10462736/graph-dijkstra-for-the-single-source-longest-path에있는 가장 긴 경로입니다. 두 노드 사이의 최대 거리를 찾는다면 그래프가 가능합니다. http://stackoverflow.com/questions/13501216/how-to-find-the-max-distance-between-a-set-of-nodes - 어 - 나무 – thebenman