Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
870 views
in Technique[技术] by (71.8m points)

algorithm - Finding Center of The Tree

I have a question which is part of my program.

For a tree T=(V,E) we need to find the node v in the tree that minimize the length of the longest path from v to any other node.

so how we find the center of the tree? Is there can be only one center or more?

If anyone can give me good algorithm for this so i can get the idea on how i can fit into my program.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

There are two approaches to do this (both runs in the same time):

  • using BFS (which I will describe here)
  • using FIFO queue.

Select any vertex v1 on your tree. Run BFS from this vertex. The last vertex (v2) you will proceed will be the furthest vertex from v1. Now run another BFS, this time from vertex v2 and get the last vertex v3.

The path from v2 to v3 is the diameter of the tree and your center lies somewhere on it. More precisely it lies in the middle of it. If the path has 2n + 1 points, there will be only 1 center (in the position n + 1). If the path has 2n points, there will be two centers at the positions n and n + 1.

You only use 2 BFS calls which runs in 2 * O(V) time.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...