Cheap and Secure Web Hosting Provider : See Now

[Solved]: What is the complexity of depth first traversal that don't label nodes as discovered?

, , No Comments
Problem Detail: 

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before.

  A  / \ B   C  \ /   D   |   E 

If run on this graph, the algorithm will traverse in this order:

A, B, D, E, D, B, A, C, D, E

Is there any way I can express the run-time complexity of this algorithm in terms of edges, nodes, or the depth of the graph? I expect it would be high, I have the feeling it will be exponential, but I'm struggling to explain why.

EDIT: The real algorithm that I am analyzing is computing the result of an expression tree, only it is not run at a tree, but at a DAG. This means, that nodes that have several parents get computed once for all parents.

Simple pseudo-code for the algorithm might be:

calculate(root){     if(root.isLeaf){         return root.value;     } else {         leftval = calculate(root.left);         rightval = calculate(root.right);         return root.operator(leftval, rightval);     } } 
Asked By : bobbaluba

Answered By : Rick Decker

For general DAGs, the runtime could indeed be exponential in the depth. Here's an example of a family of such graphs. Let $G_d$ be a digraph comprised of a vertex stacked on a collection of 4-cycles as below, where I've illustrated $G_3$:

enter image description here

In this figure, the edges are directed from top to bottom and every vertex has two children. The number of function calls your algorithm makes (and hence the run time) for a digraph $G_d$ of depth $d$ will satisfy $T(0)=1, T(d)=2T(d-1)+1$, since every $G_d$ is comprised of a root vertex at the top with two overlapping copies of $G_{d-1}$ below it. This recurrence has solution $T(d) = 2^{d+1}-1$, exponential in the depth.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback