Table of Contents
- Introduction
- Depth-First Search
- Algorithm
- Note on Depth-First Search Forest
- How Efficient is DFS
- DFS Python Code
- FAQ's
Introduction
The term "exhaustive search" can also be applied to two very important algorithms that systematically process all vertices and edges of a graph. These two traversal algorithms are depth-first search (DFS) and breadth-first search (BFS). These algorithms have proved to be very useful for many applications involving graphs in artificial intelligence and operations research.
 |
| Depth First Search (DFS) |
In addition, they are indispensable for efficient investigation of fundamental properties of graphs such as connectivity and cycle presence.
Depth-First Search
Depth-first search starts a graph's traversal at an arbitrary vertex by marking it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. This process continues until a dead end - a vertex with no adjacent unvisited vertices - is encountered.
The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end.
 |
| Example of DFS Traversal. (a) Graph. (b) Traversal's stack. (c) DFS forest |
By then, all the vertices in the same connected component as the starting vertex have been visited. If unvisited vertices still remain, the depth-first search must be restarted at any one of them.
It is convenient to use a stack to trace the operation of depth-first search. Explanation is given below 👇.
Explanation
- The starting vertex of the traversal serves as the root of the first tree in such a forest.
- Whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached.
- Such an edge is called a tree edge because the set of all such edges forms a forest. The algorithm may also encounter an edge leading to a previously visited vertex other than its immediate predecessor (i.e., its parent in the tree).
- Such an edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth-first search forest.
- The above image is the perfect example of a depth-first search traversal, with the traversal stack and corresponding depth-first search forest shown as well.
Algorithm
//Implements a depth-first search traversal of a given graph
//Input: Graph G = (V,E)
//Output: Graph G with its vertices marked with consecutive integers in the order they are // first encountered by the DFS traversal mark each vertex in V with 0 as a mark of // being “unvisited”
count ← 0
for each vertex v in V do
if v is marked with 0
dfs(v)
//visits recursively all the unvisited vertices connected to vertex v by a path and numbers
// them in the order they are encountered via global variable count
count ← count + 1; //mark v with count
for each vertex w in V adjacent to v do
if w is marked with 0
dfs(w)
Depth-First Search Forest
A DFS forest, which is obtained as a by-product of a DFS traversal, deserves a few comments, too.
- To begin with, it is not actually a forest. Rather, we can look at it as the given graph with its edges classified by the DFS traversal into two disjoint classes: tree edges and back edges.
- Again, tree edges are edges used by the DFS traversal to reach previously unvisited vertices. If we consider only the edges in this class, we will indeed get a forest.
- Back edges connect vertices to previously visited vertices other than their immediate predecessors in the traversal. They connect vertices to their ancestors in the forest other than their parents.
How Efficient is depth-first search?
It is not difficult to see that this algorithm is in fact, quite efficient since it takes just the time proportional to the size of the data structure used for representing the graph in question.
Thus, for the adjacency matrix representation, the traversal time is in Θ (|V|2), and for the adjacency list representation, it is in Θ (|V| + |E|) where |V| and |E| are the number of the graph’s vertices and edges, respectively.
DFS Python Code
Consider the following graph that is implemented in the code below👇:
 |
| Depth First Search in Python |
# Using a Python dictionary to act as an adjacency list
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function for dfs
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')
Output:
The output of the above code is as follows:
Following is the Depth-First Search5 3 2 4 8 7
FAQ's
1. Difference between DFS and BFS.
|
DFS
|
BFS
|
|
|
Data structure
|
a stack
|
a queue
|
|
Number of vertex orderings
|
two orderings
|
one ordering
|
|
Edge types (undirected graphs)
|
tree and back edges
|
tree and cross edges
|
|
Applications
|
connectivity, acyclicity, articulation points
|
connectivity, acyclicity, minimum-edge paths
|
|
Efficiency for adjacency matrix
|
Θ (|V|2)
|
Θ (|V|2)
|
|
Efficiency for adjacency lists
|
Θ (|V| + |E|)
|
Θ (|V| + |E|)
|
2. What is depth first search and backtracking?
- If feasible, it involves moving forward and, if not, going backward to thoroughly search every node.
3. Is backtracking DFS or BFS?
- Backtracking uses DFS to traverse the solution space. It is Explained above👆.
4. What is depth first search in Python?
- An algorithm for tree traversal on graph or tree data structures is called depth-first search (DFS). Recursion and data structures like dictionaries and sets make it simple to implement.
