블로그 이사 중입니다 >> gumgood.github.io

Diameter of tree 본문

Problem Solving/분류없음

Diameter of tree

gumgood 2017. 5. 27. 03:08

- Diameter of tree : tree에서 가장 먼 두 node (최장 경로) 사이의 거리

- 종만북보다 매우 쉽게 구할 수 있다. DFS 두 번 돌리면 구할 수 있음


1. Diameter of tree

   

  - tree에서의 최장 경로는 항상 root node or leaf node이다. (pf, 귀류법)

  - 최장경로 양끝 node 중 하나를 알면 DFS로부터 반대편 node를 알 수 있다.


  위의 성질로부터 Diameter of tree를 구하는 방법을 알 수 있다.

    ① 임의의 node(ex, root)로부터 '가장 멀리 있는' node u를 찾는다

    ② node u로부터 '가장 멀리 있는' node v를 찾는다.

    ③ u~v 사이 경로가 최장 경로이다.


  특정 node로부터 가장 멀리있는 node를 찾는 연산이 두 번 필요한데 이는 DFS로 해결할 수 있다.


2. Diameter of tree 구현

  far() : tree t에 대해 node n으로부터 가장 먼 node와 그까지의 거리를 반환한다.

  diameter_far() : 위의 순서에 따라 tree의 지름을 계산한다.


  C++11


3. Diameter of tree의 시간복잡도

  DFS의 시간복잡도는 이다. n개의 node로 된 tree는 n-1개의 edge를 가지므로

  전체 시간복잡도는 



'Problem Solving > 분류없음' 카테고리의 다른 글

Segment Tree (구간 트리)  (0) 2017.05.27
Disjoint-set  (0) 2017.05.27
Diameter of tree  (0) 2017.05.27
Tree Traversal  (0) 2017.05.27
Treap  (0) 2017.05.27
Priority Queue & Heap  (0) 2017.05.27
0 Comments
댓글쓰기 폼