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]](https://towardsdatascience.com/wp-content/uploads/2021/08/0hQrlbnE4yu3Gy-3U.png)
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:


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. -
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.
References
[1] Search algorithm – Wikipedia