graphstackgraph-theorydepth-first-searchiterative-deepening

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?


Solution

  • 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