CODEWITHSUNDEEP
graphstackgraph-theorydepth-first-searchiterative-deepening
Jonathan
Jonathan

Reputation: 165

Writing a DFS with iterative deepening without recursion

So currently i have a DFS with the following pseudocode

procedure DFS(Graph,source):
      create a stack S
      push source onto S
      mark source
      while S is not empty:
          pop an item from S into v
          for each edge e incident on v in Graph:
              let w be the other end of e
              if w is not marked:
                 mark w
                 push w onto S

How do I alter this function to accept a third argument that limits the depth of the search?

Upvotes: 1

Views: 7351

Answers (2)

rendon
rendon

Reputation: 2363

Let Node be a structure for each node of the graph, add a field called level, then process the graph as follows:

procedure DFS(Graph,source, depth):
  create a stack S
  source.level = 0
  push source onto S
  mark source
  while S is not empty:
      pop an item from S into v
      if v.level > depth
        continue

      for each edge e incident on v in Graph:
          let w be the other end of e
          if w is not marked:
             mark w
             w.level = v.level + 1
             push w onto S

Upvotes: 3

NeoZoom.lua
NeoZoom.lua

Reputation: 2921

  1. The procedure will return success when an object is found.
  2. When an object is found, the S will contain nodes in the path [root, source). (the source itself is not included.)
procedure DFS(Graph, source, depth):
    StackInit(S)
    if source is goal then
        return success
    markVisited(source)
    S.push(null, source)              // S is a close-list
    while S is not empty then do
        c, p := S.pop()
        r := next(c, p)               // return the next sibling of c
        if r is null then
            continue
        S.push(r, p)
        if r is marked visited then   // that already marked means it cannot be goal
            continue
        if r is goal then
            return success
        markVisited(r)
        if equal(depth(r), depth) then // here is what OP wants.
            continue
        S.push(null, r)

return fail

Upvotes: 0

Related Questions