Iterative Deepening Depth-First Search (DFS) Algorithm in Python

What is an Iterative Deepening Depth-First Search Algorithm?

Continuing our story even further, after introducing graphs and basic graph traversal algorithms, we will refine the Depth-First Search Algorithm by introducing the iterative depth limitation.

An iterative deepening depth-search algorithm also traverses a graph by exploring it vertex-by-vertex, but it does it by following the vertical order of the vertices. However, its depth is initially limited and gets increased by each consecutive iteration.

What is the Purpose of Iterative Deepening DFS?

Contrary to the depth-first search algorithm, the iterative deepening depth-first search algorithm does guarantee the shortest path between any two reachable vertices in a graph, it is widely used in many applications.

Some of those are:

• finding connected components,
• performing topological sorting,
• finding the bridges of a graph,
• determining the closeness of any two vertices in a graph or a tree, and
• solving puzzles with a unique solution such as labyrinths.

Before we’ll dive into the algorithm and the Python implementation, let’s first skim over some related graph tutorials you may enjoy and that may help your understanding!

Related Graph Tutorials

This algorithm is part of our graph algorithm tutorials:

• Breadth-First Search (BFS) Algorithm in Python
• Python Depth-First Search (DFS) Algorithm
• Iterative Deepening Depth-First Search (DFS) Algorithm in Python
• Python Best-First Search Algorithm
• Python Dijkstra Algorithm
• Python A* Algorithm
• Jump Search Algorithm in Python
• Python Backtracking
• Python Beam Search Algorithm

Each of these tutorial links opens in a new browser tab.

How Does Iterative Deepening DFS Work?

The iterative deepening depth-first search algorithm begins denoting the start vertex as visited and placing it onto the stack of visited nodes.

The algorithm will check if the vertex corresponds to the entity being searched for (in our example below, this is commented as a trivial check).

If the entity being searched for is found, the algorithm will stop executing and it will return the corresponding vertex.

Otherwise, the algorithm will loop through its neighboring vertices and recursively descent to each one of them, one step deeper in each iteration.

This way, the algorithm will:

• a) eventually find the target entity along the downward path;
• b) reach the last (leaf) vertex in the branch, backtrack through the graph (implementation-wise: it will return to the previous caller in the function call stack) and repeat the descent along the next neighboring vertex;
• c) exhaust the graph by marking all the vertices as visited without finding the target entity;
• d) finish in case of reaching the depth search limit.

We can say that the iterative deepening depth-first search algorithm will behave as a best-of-both-worlds solution by effectively visiting the vertices in rounds, similarly to the breadth-first search algorithm.

However, it will not build a list of vertices to be visited next. Instead, it will complete each round by descending as deep as allowed, limited by the iteration depth. This change of approach is known as space-time tradeoff, because, instead of additional space, we’re using additional time by repeating the traversal of previously visited vertices.

What Are the Properties of Iterative Deepening DFS?

The iterative deepening depth-first search algorithm is slightly less efficient and simple in terms of traversing a graph, but still quite appropriate.

However, it might take a significantly smaller amount of time to find the solution in a deep graph because the search depth is increased per round, contrary to the original depth-first search algorithm, where the search depth is virtually unlimited. The next path of the graph can be explored much sooner, as soon as the depth limit is reached.

How is Iterative Deepening DFS Implemented in Python?

The implementation of our iterative deepening depth-first search algorithm is achieved by functions IDDFS(), and the underlying function DFS().

IDDFS() has four parameters: the graph parameter takes an initialized Graph object (see the blog on the breadth-first search algorithm, the section on graphs).

• The vertex parameter takes the starting vertex, which we choose freely (remember, a graph is not a tree, there is no absolute root).
• The target parameter is the entity we want to find in the graph, enclosed in a vertex.
• The search_depth_max parameter is optional (defaults to 20) and sets the maximum depth of descent during the search.

DFS() takes three mandatory parameters: graph, vertex, and search_depth, and two optional parameters: target and drawing_depth. 

• The graph parameter receives a Graph object.
• The vertex parameter takes the starting vertex, which is chosen when IDDFS() was called. 
• The search_depth parameter is determined by the loop progression in IDDFS() and ranges from 0 to search_depth_max.
• The target parameter is the entity we want to find in the graph, enclosed in a vertex.
• The drawing_depth parameter is never set explicitly. It has no functional significance and is used purely for the algorithm’s output indentation.

For a better understanding of the algorithm and its implementation, each step is precisely described in the code below.

import graph
sep = '  '

# The 'drawing_depth' parameter tracks the drawing depth in the call stack 
# the algorithm is currently at, for visualization purposes.
def DFS(graph, vertex, search_depth, target=None, drawing_depth=1):
    print(sep*drawing_depth + f'Exploring vertex {vertex.entity()}')
    
    result = None
    
    # Add the vertex to 'path' for the search path reconstruction.
    path.append(vertex.entity())
    
    if search_depth == 0:
        # Trivial check #1: searches for None are immediately terminated.
        if target is None:
            print(f' The vertex {target} does not exist')
            return None, False
        
        # Trivial check #2: if the entity is in the starting vertex.
        elif target == vertex.entity():
            result = vertex
            return result, True
        else:
            # Pop the vertex from 'path' - not leading to the solution.
            path.pop()
            return None, True
    elif search_depth > 0:
        any_remaining = False
        for edge in graph.adjacent_edges(vertex):
            # Gets the second endpoint.
            v_2nd_endpoint = edge.opposite(vertex)
            
            # If the vertex is not already in the vertex path...
            if v_2nd_endpoint.entity() not in path:
                # Keep searching at the lower level, from the second endpoint.
                result, remaining = DFS(graph, v_2nd_endpoint, search_depth-1, target, drawing_depth+1)
                print(sep*drawing_depth + f'Returning to vertex {vertex.entity()}')

                # If the search was successful, stop the search.
                if result is not None:
                    return result, True
                if remaining:
                    any_remaining = True
        
        # Pop the vertex from 'path' - not leading to the solution.
        path.pop()
        return None, any_remaining

def IDDFS(graph, vertex, target, search_depth_max=20):
    for search_depth in range(search_depth_max+1):
        print(f'Iteration started - search_depth = {search_depth}')
        result, remaining = DFS(graph, vertex, search_depth, target, 1)
        print('Iteration ended.', end=2*'\n')
        if result is not None:
            return result
        elif not remaining:
            return None

Before we can test the algorithm, we have to initialize a graph and build it by adding vertices and edges to it:

# Initializes an empty graph (object).
g = graph.Graph()

# Loads the graph with the first ten vertices.
for i in range(10):
    g.add_vertex(i)

# Constructs the 'vertices' dictionary for a more
# convenient access during the graph construction.
vertices = {k.entity():k for k in g.vertices()}

# Constructs an arbitrary graph from
# the existing vertices and edgs.
g.add_edge(vertices[0], vertices[1])
g.add_edge(vertices[0], vertices[2])
g.add_edge(vertices[0], vertices[4])
g.add_edge(vertices[4], vertices[3])
g.add_edge(vertices[3], vertices[5])
g.add_edge(vertices[0], vertices[5])
g.add_edge(vertices[2], vertices[6])

# Initializes the search path.
path = []

Now that we have prepared everything, we can test IDDFS() and see how it works. Here is the part of the code that runs the algorithm, constructs the search path (if there is one), and shows in a step-by-step manner how it proceeds through the graph:

# Starts the search.
result = IDDFS(g, vertices[5], 6, 20)

# If the entity is found...
if result is not None:
    # The search path ends with the found vertex (entity). 
    # Each vertex is a container for its real-world entity.
    path_vertex = result

    # Constructs the rest of the search path (if it exists)...
    print('Search path found:', end=' ')

    # The path starts with the root vertex.
    print(*path, sep=' -> ')

# Otherwise...
else:
    print('The entity is not found.')

The test run gave us the output:

Iteration started - search_depth = 0
  Exploring vertex 5
Iteration ended.

Iteration started - search_depth = 1
  Exploring vertex 5
    Exploring vertex 3
  Returning to vertex 5
    Exploring vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 2
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
    Returning to vertex 0
      Exploring vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 3
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
        Exploring vertex 0
      Returning to vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
        Exploring vertex 6
      Returning to vertex 2
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Search path found: 5 -> 0 -> 2 -> 6

Based on the output, we can see that the search started from vertex 5 and that the IDDFS() has found the entity vertex 6. The entire search path is also displayed, and we should note that the search path is the shortest one (a property inherited from the Breadth-First Search algorithm idea): 5 -> 0 -> 2 -> 6.

If we run a search for a non-existing entity, the algorithm will traverse the whole graph and form a traversal tree, showing the order in which the vertices were visited.

We should note that iterations with search_depth = 5 and  search_depth = 6 coincide, yielding the same search paths of the same lengths. With search_depth = 5 the iteration finishes because it has reached the allowed depth.  With search_depth = 5 the iteration finishes because there are no more vertices left to visit.

# Starts the search.
result = IDDFS(g, vertices[5], 66)
…

Iteration started - search_depth = 0
  Exploring vertex 5
Iteration ended.

Iteration started - search_depth = 1
  Exploring vertex 5
    Exploring vertex 3
  Returning to vertex 5
    Exploring vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 2
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
    Returning to vertex 0
      Exploring vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 3
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
        Exploring vertex 0
      Returning to vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
        Exploring vertex 6
      Returning to vertex 2
    Returning to vertex 0
      Exploring vertex 4
        Exploring vertex 3
      Returning to vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 4
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
        Exploring vertex 0
          Exploring vertex 1
        Returning to vertex 0
          Exploring vertex 2
        Returning to vertex 0
      Returning to vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
        Exploring vertex 6
      Returning to vertex 2
    Returning to vertex 0
      Exploring vertex 4
        Exploring vertex 3
      Returning to vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 5
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
        Exploring vertex 0
          Exploring vertex 1
        Returning to vertex 0
          Exploring vertex 2
            Exploring vertex 6
          Returning to vertex 2
        Returning to vertex 0
      Returning to vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
        Exploring vertex 6
      Returning to vertex 2
    Returning to vertex 0
      Exploring vertex 4
        Exploring vertex 3
      Returning to vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

Iteration started - search_depth = 6
  Exploring vertex 5
    Exploring vertex 3
      Exploring vertex 4
        Exploring vertex 0
          Exploring vertex 1
        Returning to vertex 0
          Exploring vertex 2
            Exploring vertex 6
          Returning to vertex 2
        Returning to vertex 0
      Returning to vertex 4
    Returning to vertex 3
  Returning to vertex 5
    Exploring vertex 0
      Exploring vertex 1
    Returning to vertex 0
      Exploring vertex 2
        Exploring vertex 6
      Returning to vertex 2
    Returning to vertex 0
      Exploring vertex 4
        Exploring vertex 3
      Returning to vertex 4
    Returning to vertex 0
  Returning to vertex 5
Iteration ended.

The entity is not found.

Efficiency Analysis

The algorithm’s worst-case time complexity is O(b^d), where b represents the branching factor, and d stands for the depth of the shallowest solution. The algorithm may visit each vertex and edge multiple times, but only once per search path.

The algorithm’s worst-case space complexity is O(d), with d representing the depth of the shallowest solution.

The algorithm is optimal, as is the breadth-first search algorithm, but requires much less space than BFS. It uses recursion and is inherently limited by the maximum depth of the call stack. This property gets very pronounced as the traversal progresses through a very deep graph.

Conclusion

In this article, we learned about the iterative deepening depth-first search algorithm.

• First, we explained what an iterative deepening depth-first search algorithm is.
• Second, we got took a look at what are its common purposes and applications.
• Third, we went through an explanation of how the algorithm works.
• Fourth, we examined the algorithm’s main properties.
• Fifth, we went through the implementation of the algorithm, which is based on the Graph abstract data structure (for class implementation, see the blog on the breadth-first search algorithm). We also tested the algorithm by calling its main function, IDDFS(), and analyzed its steps of execution.
• Sixth, we analyzed the algorithm efficiency.

In the end, we concluded that the algorithm’s efficiency is optimal, and if the solution exists, the iterative deepening depth-first search algorithm will always find it following the shortest path and it will always take a finite time in reaching the solution.

Academy Course – Mastering the Top 10 Graph Algorithms

If you want to improve your fundamental computer science skills, there’s nothing more effective than studying algorithms.

To help you master the most important graph algorithms, we’ve just launched the “Top 10 Algorithms” course at the Finxter Computer Science Academy. This great course from Finxter Star Creator Matija ⭐ teaches you the most important graph algorithms such as BFS, DFS, A*, and Dijkstra. 

Understanding these algorithms will not only make you a better coder, but it’ll also lay a strong foundation on which you can build your whole career as a computer scientist.

Click the screenshot to find out more: