Two methods:
1. try BFS on each vertex, calculate the longest shortest path to
each other vertex, compare them
It is easy to implement, but gives O(n*n) running time
2. divide and conquer
randomly divide the tree into two parts, calculate the height of
the two subtrees then merge them.
This is not so easy to implement, but really gives a good running
time which is O(nlogn)
On Oct 21, 9:21 am, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> Q) You are given a root-less tree (which can also be thought of as an
> undirected acyclic connected graph). The problem is to choose one of
> the nodes from the tree as root such that the height of the resultant
> tree is minimum.
>
> Device an appropriate data-structure and write a program for the
> same.
> mum height possible is 2. So for this example the code should return
> the node '3'.
>
> Note: All nodes are numbered from 1 to n, where 'n' is the number of
> nodes. Incase there are more than one roots possible, then your
> program can return any one of them.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
