🔁Data Structures Unit 11 – Graph Traversal Algorithms (BFS and DFS)

Key Concepts

• Graph traversal algorithms systematically visit all vertices in a graph
• BFS explores vertices in layers, visiting all neighbors before moving to the next level
• DFS explores vertices by going as deep as possible before backtracking
• Queue data structure used in BFS to keep track of vertices to visit next
  • Vertices are added to the queue when discovered and removed when visited
• Stack data structure used in DFS to keep track of vertices to visit next
  • Vertices are added to the stack when discovered and popped when visited
• Time complexity of BFS and DFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges
• Space complexity of BFS is $O(V)$ due to the queue, while DFS has a space complexity of $O(V)$ due to the stack

Graph Basics

• Graphs consist of vertices (nodes) connected by edges (links)
• Edges can be directed (one-way) or undirected (two-way)
• Adjacency list represents a graph using an array of linked lists
  • Each vertex has a linked list of its neighboring vertices
• Adjacency matrix represents a graph using a 2D array

  • matrix[i][j]

    indicates the presence or weight of an edge between vertices

    i

    and

    j

• Graphs can be weighted, where edges have associated costs or distances
• Degree of a vertex is the number of edges connected to it
  • In-degree refers to the number of incoming edges, and out-degree refers to the number of outgoing edges
• Connected graph has a path between every pair of vertices
• Acyclic graph contains no cycles (paths that start and end at the same vertex)

Breadth-First Search (BFS)

• BFS explores vertices in breadth-first order, visiting all neighbors before moving to the next level
• Starts at a given source vertex and visits all vertices reachable from it
• Uses a queue to keep track of vertices to visit next
  • Discovered vertices are enqueued, and visited vertices are dequeued
• BFS can be used to find the shortest path (in terms of number of edges) from the source to all other vertices
• Can detect cycles in an undirected graph by keeping track of visited vertices
• Pseudocode:

  BFS(graph, source):
    queue = new Queue()
    visited = new Set()
    queue.enqueue(source)
    visited.add(source)
    while queue is not empty:
      vertex = queue.dequeue()
      process(vertex)
      for each neighbor of vertex:
        if neighbor not in visited:
          queue.enqueue(neighbor)
          visited.add(neighbor)
  

Depth-First Search (DFS)

• DFS explores vertices in depth-first order, going as deep as possible before backtracking
• Starts at a given source vertex and explores as far as possible along each branch before backtracking
• Uses a stack to keep track of vertices to visit next
  • Discovered vertices are pushed onto the stack, and visited vertices are popped
• DFS can be implemented using recursion or iteration with a stack
• Recursive implementation:

  DFS(graph, vertex, visited):
    visited.add(vertex)
    process(vertex)
    for each neighbor of vertex:
      if neighbor not in visited:
        DFS(graph, neighbor, visited)
  

• Iterative implementation uses a stack to simulate the recursive call stack
• DFS can be used to detect cycles in a directed graph by keeping track of visited vertices and vertices on the current path
• Topological sorting of a directed acyclic graph (DAG) can be achieved using DFS

Comparison of BFS and DFS

• BFS explores vertices in breadth-first order, while DFS explores vertices in depth-first order
• BFS uses a queue to keep track of vertices to visit next, while DFS uses a stack
• BFS is suitable for finding the shortest path (in terms of number of edges) from the source to all other vertices
• DFS is suitable for exploring all vertices reachable from the source and detecting cycles
• BFS generally requires more memory than DFS due to the queue
  • In the worst case, BFS may need to store all vertices in the queue
• DFS has the advantage of using less memory than BFS in most cases
  • DFS only needs to store the vertices on the current path and their neighbors in the stack
• Time complexity of both BFS and DFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges

Implementation Techniques

• Adjacency list is commonly used to represent graphs in BFS and DFS implementations
  • Provides efficient access to neighboring vertices
• Adjacency matrix can also be used, but it may consume more memory for sparse graphs
• Visited set or array is used to keep track of visited vertices to avoid revisiting them
  • Prevents infinite loops in graphs with cycles
• Queue is used in BFS to store vertices to visit next
  • Can be implemented using a linked list or a dynamic array (e.g.,

    std::queue

    in C++)
• Stack is used in DFS to store vertices to visit next
  • Can be implemented using a linked list or a dynamic array (e.g.,

    std::stack

    in C++)
• Recursive implementation of DFS is often more concise and easier to understand
  • Recursion stack keeps track of the vertices on the current path
• Iterative implementation of DFS explicitly uses a stack to simulate the recursive call stack
  • Allows for more control over the traversal process

Applications and Use Cases

• Shortest path finding in unweighted graphs using BFS
  • Example: finding the minimum number of hops between two nodes in a network
• Cycle detection in undirected graphs using BFS or DFS
  • Example: detecting circular dependencies in a build system
• Topological sorting of directed acyclic graphs (DAGs) using DFS
  • Example: determining the order of tasks in a project with dependencies
• Connected components in undirected graphs using BFS or DFS
  • Example: identifying isolated clusters in a social network
• Solving puzzles and mazes using BFS or DFS
  • Example: finding the shortest path to the exit in a maze
• Web crawling and indexing using BFS or DFS
  • Example: traversing web pages to build a search engine index
• Bipartite graph checking using BFS or DFS
  • Example: assigning students to projects without conflicts

Practice Problems

• Implement BFS and DFS traversals for a given graph
• Find the shortest path between two vertices in an unweighted graph using BFS
• Detect cycles in an undirected graph using BFS or DFS
• Perform topological sorting of a directed acyclic graph (DAG) using DFS
• Find connected components in an undirected graph using BFS or DFS
• Determine if a graph is bipartite using BFS or DFS
• Solve a maze or puzzle using BFS or DFS
• Implement a web crawler using BFS or DFS to traverse web pages
• Find the minimum spanning tree of a weighted graph using BFS or DFS (Prim's or Kruskal's algorithm)
• Solve the knight's tour problem on a chessboard using BFS or DFS