kindly explain visualizing a balanced BST as a graph and unable to
underdstand your point
thanks
--mac
On Fri, May 24, 2013 at 6:04 AM, Avi Dullu avi.du...@gmail.com wrote:
On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote:
2. from this no*de u*, again apply*
My bad, I wrote out degree where I should have written in degree.
My proposal:
Topological Sort http://en.wikipedia.org/wiki/Topological_sorting the
graph and keep removing the nodes from vertices which have in degree of 0
(given the DAG, there will always be at least one such vertex).
For a BST,
On Sat, May 11, 2013 at 10:29 AM, Aman Jain pureama...@gmail.com wrote:
2. from this no*de u*, again apply* dfs* to find longest distant node
from this node.Let us say that node is v.
Small doubt about the solution. Consider this graph a - b - c - d
You randomly choose vertex 'b' and do a
@atul anand : got it thanks for pointing it out
On Mon, May 13, 2013 at 12:19 AM, atul anand atul.87fri...@gmail.comwrote:
@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo
@karthikeyan : It is an acyclic graph not a binary tree. your solution
will work if given graph is a binary tree.
problem can be solved using dfs as suggested above
On 5/11/13, Karthikeyan V.B kartmu...@gmail.com wrote:
Since it is an acyclic graph, find the appropriate node that can be the
@atul anand : acyclic graph can be converted to a tree using prim/kruskal
or by finding an appropriate node that can act like the root of a tree
On Sun, May 12, 2013 at 5:55 PM, atul anand atul.87fri...@gmail.com wrote:
@karthikeyan : It is an acyclic graph not a binary tree. your solution
@Karthikeyan : Given graph is directed and does not carry edge
weight.So you cannot use pris/kruskal algo to convert them to
tree.Even if you tweak prism/krukal algo to form a tree , you can
never guarantee that each node will have only 2 child , it can have
more than 2 children.So your
Given an acyclic graph. Give an algorithm to find the pair of nodes which
has the maximum distance between them, i.e. the maximum number of edges in
between them
any suggestion ?
thanks
--mac
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
In a connected and acyclic graph,that is a tree, we can apply this approach
1. apply *dfs *on any random node and find the longest distant node from
this node.Let us say this node i*s u*.
2. from this no*de u*, again apply* dfs* to find longest distant node from
this node.Let us say that node is
Since it is an acyclic graph, find the appropriate node that can be the
root of this tree.
Now apply the logic to find the diameter of the tree here, which finds the
longest path in the graph as follows:
int diameter(Tree * t) { if (t == 0) return 0; int lheight =
height(tree-left); int rheight
10 matches
Mail list logo
