Menu
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.
204
Algorithm to find centers and bi-centers of a treeIf a single vertex is left then it is the center of the tree and if two vertices joined by an edge is left then it is the bi-center of the tree.
Heartwood is the central, supporting pillar of the tree.
Algorithm to find centers and bi-centers of a tree Step 1 − Remove all the vertices of degree 1 from the given tree and also remove their incident edges. Step 2 − Repeat step 1 until either a single vertex or two vertices joined by an edge is left.
A center of a graph is a vertex with minimal eccentricity. A graph can have an arbitrary number of centers. However, Jordan (1869) has proved that for trees, there are only two possibilities: The tree has precisely one center (centered trees).
There are two approaches to do this (both runs in the same time):
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.
141
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
