트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:
1. 트리에서 임의의 정점 x를 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.
트리의 지름은 정점 y와 정점 z를 연결하는 경로다.
'Algorithem' 카테고리의 다른 글
| 유용한 해싱 (0) | 2023.01.06 |
|---|---|
| 실시간으로 변하는 경우 heap으로 중앙값 찾기 (0) | 2023.01.06 |
| 트리의 두번째 지름 : 지름 구하기 3번으로 (0) | 2023.01.06 |
| 수학 : 최대공약수와 최소공배수, 소수 구하기 (0) | 2023.01.06 |
| 최장 공통 부분 수열 (LCS) : 다이나믹, 2차원배열, 역추적 (0) | 2023.01.06 |
