[알고리즘] 트리의 지름 (Diameter of Tree)

트리의 지름 이란? 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함수로 나타낼 수 있으며, 최장거리(지름)는 이러한 d(u, v) 값들중 최대인 Max d(u, v)라고 할 수 있다. 트리의 지름을 찾는 알고리즘 BFS(node) 를 통하여 node로 부터 가장 멀리있는 node를 구한다고 해보자. 이 방식은 greedy 방식에 해당된다. < 알고리즘 > 1. 임의의 시작 정점 s로부터 가장 멀리있는 정점인 u를 BFS(s)로 구한다. (DFS도 가능) 2. 이렇게 구한 정점 u를 시작정점으로 하여 다시 BFS(u)를 구한다. 3. BFS(u)를 통하여 구해진 가장 멀리있는 정점 v를 얻었다면, 이렇게 구해..........

원문링크 : [알고리즘] 트리의 지름 (Diameter of Tree)