Depth First Traversal of Graph

In this lesson, we will learn about depth first traversal of graph using recursion.

We'll cover the following

What is a Graph?

Graphs represent pairwise relationships between objects. Graphs are mathematical structures and therefore can be visualized by using two basic components, nodes and edges

A node, also known as a vertex, is a fundamental part of a graph. It is the entity that has a name, known as the key, and other information related to that entity. A relationship between nodes is expressed using edges. An edge between two nodes expresses a one-way or two-way relationship between the nodes.

Graphs can be represented as Adjacency Matrix or Adjacency List. We will be using adjacency list representation for this course. If you want to study graphs in detail have a look at our Interview Refresher Course on Data Structures in Python.

The diagram below shows an example graph. It had 66 nodes and 66 edges.

What does “Depth First Traversal of Graph” Mean?

The depth-first graph traversal involves visiting all nodes of the graph once depth-wise.

Starting from any node, we keep moving to an adjacent node until we reach the farthest level (deepest node). Then we move back to the starting point and pick another adjacent node. Once again, we probe to the farthest level and move back. This process continues until all nodes are visited.

Let’s have a look at the visual representation of the depth first algorithm:

Implementation

Press + to interact
main.py
graph.py
import graph as g
def helperFunction(myGraph, currentNode, visited) : 
  # Mark the currentNode as visited and print it 
  if(visited[currentNode] == False) :
    visited[currentNode] = True
    print(currentNode) 
  # Recur for all the vertices adjacent to currentNode
  for i in myGraph.graph[currentNode]: 
    if visited[i] == False: 
      helperFunction(myGraph, i, visited) 
def DFS(myGraph): 
  visited = [False]*(myGraph.vertices) # Initially all vertices are marked as unvisited
  helperFunction(myGraph, 0, visited) # Call helper function starting from node 0
# Driver code 
# Create a graph given in the above diagram 
myGraph = g.Graph(6) 
myGraph.addEdge(0, 1) 
myGraph.addEdge(1, 2) 
myGraph.addEdge(1, 3) 
myGraph.addEdge(2, 4) 
myGraph.addEdge(3, 4) 
myGraph.addEdge(3, 5) 
print("DFS Graph Traversal")
DFS(myGraph)

Explanation

In the recursive implementation of Depth-First Traversal, we traverse as far as possible from each branch, backtracking when the last node of that branch has been visited.

In the above code, all the initializations take place in the main DFS() function. However, the important part of the code is the helperFunction() where recursion takes place.

The algorithm for the helper function is:

helperFunction(vertex u)
    if u has is not visited :
    # mark u as visited

    for each adjacent vertex v :
      helperFunction(v)

    return

Notice, that the recursive case is easily detectable in the code. However, what will be the base case for this code?

Now, it’s your turn to try solving some problems.