Find the leaf of tree then put all leaf in a queue.
While queue not empty:
remove u from queue
remove u of tree
if some v adjacent a u become leaf
insert v in queue
the last vertice is the center of the tree
On Wed, Oct 6, 2010 at 8:08 AM, Ruturaj <[email protected]> wrote:
> I am thinking on these lines.
>
> Start from any node. DFS to the fartheset node from there. let the
> farthest node be B. Start a new DFS from B to reach the fartheset node
> from B , let that be C. It can be proved that BC is the longest path
> in the tree. Then, the node in the center will be the answer to the
> question. Incase the path length is even we will have two nodes.
>
> I havent proved it yet, the second part of my solution. this was a
> quick thought.
>
> On Sep 29, 9:41 pm, jayapriya surendran <[email protected]> wrote:
> > In graph theory, a tree is defined as a graph on N nodes,and (N-1)
> > un-directed edges such that there are no cycles in the graph.Each node
> > has a single unique path to every other node.
> > Let D(u,v) be the number of edges in the unique path from node 'u' to
> > node 'v' (or from node 'v' to 'u' since the edges are
> > un-directed).D(u,u) is 0 for all nodes 'u'.
> > M(u)=MAX(D(u,i):for all nodes i)
> > The center of a tree is the node (or nodes) 'u',for which M(u) is
> > minimum among all the nodes in the graph.
> > You'll be given a graph which has N nodes (1<=N<=20).The nodes are
> > labeled 1,2,3,..N.You will be provided with N-1 edges in the form of
> > "a b" pairs where 1<=a,b<=N.No edge will be repeated.You can assume
> > that the edges are specified such that the graph is a valid tree as
> > defined above.
> > Output the node labels of the center(or centers) of the tree.
> > Sample Input:
> > 6(value of N)
> > 1 3 (edges)
> > 1 4
> > 1 2
> > 2 5
> > 2 6
> >
> > Sample Output
> > 1
> > 2
> > Expected:O(N) complexity algo
> > can anyone plz help me out with O(N) algo?
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
