we can do like creating an adjacency matrix......populate all values i.e. cost to reach each node...finally find the nodes that has min value...any other gud solutions??
On Wed, Jul 27, 2011 at 2:16 AM, sivaviknesh s <sivavikne...@gmail.com>wrote: > the question is clear..you draw the sample test case and work out .. > you will understand > > 1 > / / \ > 4 2 3 > /\ > 5 6 > > ....here from node 2 the maximum cost to reach any node 'i' is 2 and > minimum is 1 > > ...so M(2) = max(1,2)=2..the same is the case for node 1 also > > ...if you consider node 4 , to reach 6 , cost is 3....similar is > applicable for other nodes.... > > ....therefore centre = min(M(1..6)) = 1 and 2. > ...hope u got me!! > > On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh <sivavikne...@gmail.com>wrote: > >> >> >> >> ---------- Forwarded message ---------- >> From: jayapriya surendran <priya7...@gmail.com> >> Date: Sep 29 2010, 9:41 pm >> Subject: Directi question-centre of the tree >> To: Algorithm Geeks >> >> >> In graph theory, atreeis 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) >> Thecenterof atreeis 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 validtreeas >> defined above. >> Output the node labels of thecenter(or centers) of thetree. >> 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? >> > > > > -- > Regards, > $iva > > -- Regards, $iva -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
