Difference between Breadth First Search, and Iterative deepening

theraven picture theraven · Jun 8, 2010 · Viewed 29.9k times · Source

I understand BFS, and DFS, but for the life of me cannot figure out the difference between iterative deepening and BFS. Apparently Iterative deepening has the same memory usage as DFS, but I am unable to see how this is possible, as it just keeps expanding like BFS. If anyone can clarify that would be awesome.

tree to work on if required:

    A
   / \
  B   C
 /   / \
D   E   F

Answer

Roman A. Taycher picture Roman A. Taycher · Jun 8, 2010

From What I understand iterative deepening does DFS down to depth 1 then does DFS down to depth of 2 ... down to depth n , and so on till it finds no more levels

for example I think that tree would be read

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

I believe its pretty much doing a separate DFS with depth limit for each level and throwing away the memory.