CODEWITHSUNDEEP
recursionstackgraph-algorithmdepth-first-searchdirected-graph
Harry
Harry

Reputation: 445

DFS on a graph the non-recursive way

I'm working on an exercise and I'm kind of stuck, need some help. Suppose we have the following vertices and edges on a directed graph: AB, BC, AD, CD, DC, DE, CE, EB, AE depicted below

Graph Trying to figure out how many "trips" exist from C to C, with no more than 3 edges. That would be two (2), C-D-C and C-E-B-C

So far I've managed to solve it by using DFS and recursion. I keep track of the depth (i.e. how many edges away from source) and when that becomes more that 3, the recursive function returns.

What I'm trying to do now is solve it without using recursion, that is, by using a stack, but I'm stuck! If I use something like the following (pseudo code):

s.create() <- create stack
s.push(nodeA)
depth = 0

while !s.empty
  n = s.pop()

  foreach (n.connectedVertices as c)
    s.push(c)
  depth++

Then I have no way to know which depth each vertex is supposed to be on. I've been thinking of using a stack of stacks somehow (saved for each depth?) but haven't figured that out yet.

Any help would be greatly appreciated.

Upvotes: 1

Views: 417

Answers (1)

Brijesh
Brijesh

Reputation: 320

You can do this by pushing pairs in stack .
the pair will contain (node , depth) .
Now initially push (node , 0) . 

s.create()
s.push(nodeA , 0)

while !s.empty
    cur_node , depth = s.pop()  
    if depth==3
        continue // if depth = 3 then we don't need to push anything .

    for each node connected with cur_node
        s.push(node , depth + 1)

I hope you got the idea of how can we calculate answer .

Upvotes: 1

Related Questions