🕵️‍♂️

Depth First Search (DFS) Traversal in Graphs

Jul 4, 2024

Depth First Search (DFS) Traversal in Graphs

Introduction

  • Learn about DFS traversal in graphs
  • Previous video covered BFS (Breadth First Search)
  • DFS (Depth First Search) is based on depth

Key Concepts

  • Graph: Consists of nodes and edges connecting them
  • Starting Node: DFS begins from a given starting node
  • DFS explores the depth of a graph before backtracking

DFS Traversal Steps

  1. Start at the root node: E.g., node 1
  2. Choose a neighboring node: e.g., node 2
  3. Move to the deepest node without revisiting nodes
  4. Backtrack once no further depth is available
  5. Continue to the next branch

Example

  • Start at node 1
    • Move to node 2
      • Move to node 5
        • Backtrack to node 2
      • Move to node 6
        • Backtrack to node 2
    • Backtrack to node 1
    • Move to node 3
      • Move to node 7
        • Move to node 8
          • Move to node 4
        • Backtrack through nodes 8 and 7 to node 3
      • Alternative traversals possible

Variability in Traversal

  • Starting node can change DFS path
  • E.g., starting at node 3 instead of node 1
  • Order of visiting neighboring nodes affects traversal

Recursion and DFS

  • DFS is implemented using recursion
  • Recursion helps in exploring depth first

Storing Graphs

  • Graphs are typically stored using adjacency lists
  • Adjacency list represents neighboring nodes

Implementation Details

  1. Visited array: Track visited nodes
    • Initialize with false values
  2. Recursive DFS function: Traverses nodes
    • Mark nodes as visited
    • Visit unvisited neighbors
    • Backtrack when necessary

Example DFS Code (C++)

void dfs(int node, vector<vector<int>>& adjList, vector<bool>& visited, vector<int>& result) { visited[node] = true; result.push_back(node); for (int neighbor : adjList[node]) { if (!visited[neighbor]) { dfs(neighbor, adjList, visited, result); } } }
  • Main Function: Initializes DFS
vector<int> dfsTraversal(int start, vector<vector<int>>& adjList) { vector<int> result; vector<bool> visited(adjList.size(), false); dfs(start, adjList, visited, result); return result; }

Complexity Analysis

  • Space Complexity: O(N) (visited array, recursion stack)
  • Time Complexity: O(N + E)
    • N: Number of nodes
    • E: Number of edges
    • Traverses each edge and node once

Conclusion

  • DFS is crucial for depth-based graph exploration
  • Understanding recursion is essential for DFS
  • Adjacency lists are effective for graph representation
  • Practice DFS by implementing it in code (C++/Java)

Full transcript