Algorithem
트리의 지름 구하기 : 단 두번의 dfs 탐색
jamong5
2023. 1. 6. 07:42
트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:
1. 트리에서 임의의 정점 x를 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.
트리의 지름은 정점 y와 정점 z를 연결하는 경로다.