Search Algorithm – Depth-first search, with Python

Python implementation from scratch

Aug 9, 2021

2 min read

In this article, I will introduce one of the foundation search algorithms called Depth-first search (DFS).

The search algorithm is an algorithm to retrieve information stored within some data structure, or calculated in the search space of a problem domain [1]. A search strategy is defined by picking the order of node expansion. Strategies can be evaluated along the following dimensions:

Completeness: Does it always find a solution if one exists?
Time Complexity: How long does it take to find a solution?
Space Complexity: Maximum number of nodes in memory
Optimality: Does it always find the best (least-cost) solution?

Definition

Depth-first search is an algorithm for traversing or searching tree or graph data structures [2]. Before explaining the DFS algorithm, let’s introduce the graph data structure. A graph G is a pair (V, E), where V is a finite set and E is a set of binary relations on V.

❖ V is called the vertex set and its elements are vertices.

❖ E is called the edge set and its elements are called edges. An edge is represented by a pair of vertices.

👁 Example of the GRAPH data structure [3]

Example of the GRAPH data structure [3]

The diagram is a schematic representation of the graph with vertices V={1, 2, 3, 4, 5, 6}, E={{1, 2},{1, 5},{2, 3},{2, 5},{3, 4},{4, 5},{4, 6}}

Depth-first search (DFS)

Now, let’s start explaining DFS in detail. It starts at the root node and expands the deepest unexpanded node, backtracks only when no more expansion. Let’s go through an example with the following GRAPH:

👁 Example GRAPH to go through DFS. Image by Author.

Example GRAPH to go through DFS. Image by Author.

👁 DFS Algorithm, step by step expansion. Image by Author.

DFS Algorithm, step by step expansion. Image by Author.

From the above step by step expansion diagram, we can see that the DFS algorithm prioritizes edges along the path to perform a search.

Now, let’s evaluate this algorithm: Denote m as the maximum depth of the state space and b as the maximum branching factor of the search tree or graph

Completeness: • infinite-depth spaces: No • finite-depth spaces with loops: No • finite-depth spaces with repeated-state checking: Yes • finite-depth spaces without loops: Yes
Time Complexity: O(bᵐ)
Space Complexity: O(bm)
Optimality: No

Code Implementation

Let’s use the above example to implement the DFS algorithm using Python.

The diagram is a schematic representation of the graph with vertices V={A, B, C, D, E, F, G, H, I, J, K, L, M}, E={{A, B}, {A, C}, {B, D}, {B, E}, {C, F}, {C, G}, {D, H}, {D, I}, {E, J}, {E, K}, {F, L}, {F, M}}

Creating the function that takes in edges of the GRAPH which outputs the adjacency list for undirected graph

👁 The output of the code. Image by Author.
The output of the code. Image by Author.
Creating the function that takes in the adjacency list and starting vertex which output the sequence of DFS search

👁 The output of the code. Image by Author.
The output of the code. Image by Author.