(알고리즘) 트리의 지름 구하기

입력: 하나의 트리

출력: 두 정점 (u,v)의 거리의 최댓값

 

Brute Force: O(n^2) ~ O(n^3)

BFS로 가능한 (u, v)의 모든 조합을 다 해본다.

가장 간선의 갯수가 많은 두 점이 정점이다.

시간복잡도: O(n^3)

*시간복잡도: O(n^2) (점 하나를 고정한 상태에서 BFS 할 경우)

 

O(n) 알고리즘

점 하나를 지정한 상태에서 BFS로 가장 먼 지점 u를 찾는다.

그 점에서 BFS로 가장 먼 지점 v를 찾는다.

*간선의 갯수가 가장 많은 경우가 n개라고 했을때, n개의 간선의 갖는 점이 여러개인 것이 아니라면 자명하다.