Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Graph Traversal - Depth First Search(DFS)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Graphs are made up of nodes (vertices) connected by edges. Traversing a graph means visiting all its nodes in a structured way. This helps solve problems like finding paths, detecting cycles, and searching for specific values.

Two widely used traversal techniques are:

  • Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.
  • Breadth-First Search (BFS): Explores all neighbors of a node before moving deeper.

This lesson focuses on the Depth-First Search (DFS) approach.

Depth First Search(DFS) Using a Stack Data Structure

Depth-First Search (DFS) is a graph traversal algorithm that explores all the nodes in a graph by systematically visiting as far as possible along each branch before backtracking. It operates on both directed and undirected graphs and can be implemented using recursion or an explicit stack data structure.

DFS starts from a selected source node (or a starting point) and explores as deeply as possible along each branch before backtracking. The algorithm visits nodes in a depth ward motion until it reaches a leaf node with no unexplored neighbors. At that point, it backtracks and explores other unexplored branches.

Step-by-Step Algorithm

  1. Initialize the Data Structures:

    • Create a visited array to track whether a node has been visited.
    • Initialize an empty stack and push the starting node onto it.

  2. Traversal Loop:

    • While the stack is not empty:
      1. Pop the top node from the stack and mark it as visited.
      2. Process the node (e.g., print it).
      3. Traverse through all neighbours of the node and push unvisited neighbours onto the stack. This step ensures that we explore the graph as deeply as possible.

  3. End Condition:

    • The traversal ends when the stack becomes empty, indicating all reachable nodes have been visited.

Step-by-step Algorithm Walkthrough

Let's illustrate Depth-First Search (DFS) on a simple graph with its step-by-step traversal process.

Image

Code Implementation of Depth First Search Using a Stack

In this example implementation, we assume that the graph is represented as an adjacency list.

Python3
Python3
. . . .

Complexity analysis

Time Complexity

  1. Initialization:

    • The visited array is initialized, which takes O(V) time, where V is the number of vertices.

  2. Traversal Loop:

    • Each node is pushed onto and popped from the stack exactly once, resulting in O(V) operations for stack management.
    • The inner loop iterates over all neighbors of a vertex. Over the entire execution of the algorithm, all edges are traversed once (each edge is visited when exploring its endpoints).
      • For an undirected graph: Each edge is considered twice (once for each endpoint), but this is still O(E) where E is the number of edges.

  3. Total Time Complexity:

    • The traversal loop involves O(V + E) operations:
      • O(V) for visiting each vertex.
      • O(E) for traversing all edges.
    • Overall Time Complexity: O(V + E)

Space Complexity

  1. Visited Array:

    • A visited boolean array of size V is used to track whether each vertex has been visited.
    • Space Requirement: O(V).

  2. Stack:

    • In the worst case, the stack may contain all vertices in the graph, particularly in a graph with one long branch or a star graph.
    • Space Requirement: O(V).

  3. Overall Space Complexity:

    • The total space complexity is: O(V)

Depth First Search(DFS) Using a Recursive Approach

In the recursive approach, the function calls itself to traverse adjacent nodes, mimicking the natural depth-first behavior of the algorithm. This approach leverages the function call stack to manage backtracking, simplifying the implementation.

In recursive DFS, each node is visited once, and its unvisited neighbors are recursively explored. The recursion ends when all reachable nodes have been visited. A visited array is used to ensure nodes are not revisited, preventing infinite loops in cyclic graphs.

Step-by-Step Algorithm

  1. Graph Initialization:

    • Represent the graph using an adjacency list for efficient storage and neighbor lookup.

  2. Setup for DFS:

    • Create a visited array of size equal to the number of vertices, initialized to false.

  3. Start Recursive Traversal:

    • Call the recursive DFS function, passing the starting vertex and the visited array.

  4. Recursive Traversal:

    • Mark the current vertex as visited and process it (e.g., print its value).
    • Recur for each unvisited neighbor of the current vertex by calling the DFS function for that neighbor.

  5. Backtracking:

  • If there are no more unvisited neighbors for the current node, backtrack by returning from the recursive function.
  1. Termination:
  • The DFS algorithm terminates when all nodes reachable from the source node have been visited. This means that all connected components of the graph have been explored.

Algorithm Walkthrough

Input Graph:

  • Vertices: 5
  • Edges: (0, 3), (0, 2), (0, 1), (1, 2), (2, 4)

Starting Vertex: 0

Execution Steps:

  1. Initialization:

    • visited = [false, false, false, false, false]

  2. First Call from 0:

    • Call DFSRecursive(0, visited).
    • Mark 0 as visited: visited = [true, false, false, false, false].
    • Print 0.
    • Recur for neighbors 3, 2, 1.

  3. Second Call to 2:

    • Call DFSRecursive(3, visited).
    • Mark 3 as visited: visited = [true, false, false, true, false].
    • Print 3.
    • No unvisited neighbors for 3, return to previous call.

  4. Back to 0, and visit 2:

    • Call DFSRecursive(2, visited).
    • Mark 2 as visited: visited = [true, false, true, true, false].
    • Print 2.
    • Recur for neighbor 1.

  5. Visit 1:

    • Call DFSRecursive(1, visited).
    • Mark 1 as visited: visited = [true, true, true, true, true, false.
    • Print 1.
    • No unvisited neighbors for 1, return to previous call.

  6. Back to node 2, and visit 4:

    • Call DFSRecursive(4, visited).
    • Mark 4 as visited: visited = [true, true, true, true, true].
    • Print 4.
    • No unvisited neighbors for 4, return to previous call.

  7. End of Traversal:

    • All nodes have been visited, and the recursive calls terminate.

Output:

DFS Traversal: 0 3 2 1 4

Code Implementation For the Recursive DFS Approach

Python3
Python3
. . . .

Complexity Analysis for Recursive DFS

Time Complexity

  1. Traversal of Nodes (Vertices):

    • Each node is visited exactly once during the traversal.
    • Marking a node as visited and processing it are constant-time operations, contributing O(V) for all nodes, where V is the number of vertices.

  2. Traversal of Edges:

    • Each edge is explored exactly twice: once for each endpoint (due to the undirected nature of the graph).
    • Checking the adjacency list for unvisited neighbors takes time proportional to the number of edges.
    • The total time spent on edges is O(E), where E is the number of edges.

  3. Recursive Calls:

    • The recursion explores each node and its neighbors, visiting every edge exactly once.
    • The cost of recursive calls depends on the depth of recursion, which corresponds to the height of the DFS tree.

Total Time Complexity:

  • Overall: O(V + E), as all vertices and edges are visited once.

Space Complexity

  1. Visited Array:

    • The visited[] array requires O(V) space, where each element corresponds to a vertex in the graph.

  2. Recursive Call Stack:

    • The depth of the recursion stack corresponds to the height of the DFS tree:
      • In the worst case (e.g., a single long chain of nodes), the depth can be equal to V, requiring O(V) stack space.
      • In a balanced graph, the height of the DFS tree is proportional to \log V.

Total Space Complexity:

  • Overall: O(V), dominated by the recursion stack.

Final Words

DFS can be used for various applications, such as finding connected components, detecting cycles in the graph, topological sorting, and solving problems like maze exploration or finding paths between nodes.

It's essential to be cautious about infinite loops when traversing graphs that may have cycles. To avoid this, the algorithm must keep track of visited nodes and avoid revisiting nodes that have already been explored.

Overall, DFS is a powerful graph traversal algorithm that can efficiently explore the entire graph and is widely used in many graph-related problems.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible