farthest from
2: Find a vertex v1 | the farthest form r.
3: Find a vertex v2 | the farthest form v1.
won't v2 be farthest from r? or we are talking about alternate pats also
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jun 20, 2012
@ashish it wont be...first we r finding one end from any node dat is r n
den frm dat end we r traversing to other deepest end...
it is possible dat r b d intermediate node...n distance from r to v2 is
smaller than from r to v1
--
You received this message because you are subscribed to the Google
I am asking again .. can any one please suggest better method for getting
the median on the longest path of the tree ..
efficient method .
On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
for getting diameter we can simply add the max height of left subtree
As you traverse along and find the diameter of the tree, keep track of the
number of nodes thereby traversed. Let that be equal to n.
Now, centre is the node corresponding to floor((n+1)/2).
On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
I am asking again
for getting diameter we can simply add the max height of left subtree and
max height of the right sub tree .
the main issue is how efficiently we find median on that longest path to
get the center of the tree .
can any bdy sugest optimized algo for that ?
On Mon, Jun 18, 2012 at 6:08 PM, rajesh
I found it in some paper ;)
Diameter and center
De nition 4. The diameter of tree is the length of the longest path.
De nition 5. A center is a vertex v such that the longest path from v to a
leaf is minimal
over all vertices in the tree.Tree center(s) can be found using simple
algorithm.
I think this algorithm is used for calculating poset in graph.
On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote:
+ 1 for DK's solution. Is that a standard algorithm coz I feel like I have
heard it somewhere ??
On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com
+ 1 for DK's solution. Is that a standard algorithm coz I feel like I have
heard it somewhere ??
On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote:
@KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3).
Could you please state how you can use the traversals directly to get the
Traverse the tree inorder. Store the values in an array. Find the element in
the middle of the array.
On Sun, Aug 7, 2011 at 8:57 AM, subramania jeeva
subramaniaje...@gmail.comwrote:
5
/\
6 7
/
8
Here the centre is both 5 and 6 . we need to find both of them..:)
@Everyone: Wladimir has posted the correct solution to the problem and it is
an O(N) bottom up solution.
*The original solution:*
On Wednesday, 6 October 2010 21:10:40 UTC+5:30, wladimirufc wrote:
Find the leaf of tree then put all leaf in a queue.
While queue not empty:
remove u from
Codechef Ques(Initiative of Directi)
use DFS, BFS or Floyd Warshall... :)
--
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
@KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3).
Could you please state how you can use the traversals directly to get the
center? (And prove your correctness too?)
The solution given by Wladimir ( expanded upon by me) is O(N) and uses
(somewhat) the inverse of a BFS as a traversal.
--
From any node, find the farthest node by DFS, save its location(say
A). Now start DFS from A, and reach the farthest node, say B. AB will
be diameter of tree and longest path. The central node will be the
centre of tree. O(n) solution.
On Jul 27, 1:53 am, sivaviknesh s sivavikne...@gmail.com
5
/\
6 7
/
8
Here the centre is both 5 and 6 . we need to find both of them..:)
Cheers
~ Jeeva ~
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
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
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.comwrote:
the question is clear..you draw the sample test
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
I don't understand what you mean when you say minimum among all the
nodes in the graph.
In any case, your definition of centre of tree looks similar to the
closeness centrality measure -
http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Closeness
I doubt you can do it in O(N)...
18 matches
Mail list logo
