How to find the 'central node' of a tree?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
saatvik
New poster
Posts: 3
Joined: Thu Jul 28, 2005 3:22 pm

How to find the 'central node' of a tree?

Post by saatvik »

Hi,

I was hoping somebody could explain me an algorithm to find the 'central node' of a tree, i.e. - the node from which the maximum distance to any other vertex is minimized over all vertices.

Thank You

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Identify the longest path of the tree. Then it's median node is the central node.

To identify the longest path, apply dfs from any node. Pick one of the deepest node from the dfs tree. Apply dfs again from this node. The path from this node to the deepest node of the second dfs tree is the longest path.

sharpobject
New poster
Posts: 4
Joined: Sun Jul 31, 2005 6:37 am
Contact:

Post by sharpobject »

The first solution that comes to mind is to run Floyd-Warshall on the graph, then search for the optimal node. Almost as soon as I started typing that, I realized it sucked. So instead, I made up another algorithm and realized 20 minutes later it was broken. Sorry.

Floyd-Warshall takes O(n^3) time and O(n^2) space in the number of nodes when coded correctly.

Edit: Cho owns me :)

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro »

You can at the first step eliminate all the leaves of a tree, doing so decreases the largest distance by 1. We repeat this until one or two nodes remain, these will be the nodes with the largest distance to other nodes. You can use this algoritm to find the center of the tree in O(n).

saatvik
New poster
Posts: 3
Joined: Thu Jul 28, 2005 3:22 pm

Post by saatvik »

Cosmin - Does your solution work on weighted trees?
Cho - I didn't really understand why the algo you suggested works.

Thanks

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro »

No my algorithm doesn't work on weighted trees. For weighted trees you could try something like this: add another node and join every leaf with this node and the weigth of each added edge will be 0. Now just apply the Dijkstra algorithm with heaps and the node that is farthest away from the new node will be the center. So the algoritm will be O(M log N) but the number of edges is O(M) so we have a O(N log N) solution.

Post Reply

Return to “Algorithms”