Lecture on Breadth First Search (BFS) and Depth First Search (DFS)

Introduction

• Topics Covered: Breadth First Search and Depth First Search
• Focus: Difference between BFS and DFS using examples
• Graph vs. Tree: A tree is a type of graph

Key Terminology

1. Visiting a Vertex: Going to a particular vertex
2. Exploration of a Vertex: Visiting all adjacent vertices of a particular vertex

Breadth First Search (BFS)

• Method: Explore a vertex, then go to the next vertex for exploration.
• Example: Start from vertex 1
  • Visit 1, then explore adjacent vertices 5, 4, and 2 in any order.
  • After visiting 2, explore 7, 6, and 3 in any order.
• Result: All vertices are visited, and none remain for exploration.
• Analogy: BFS is like level-order traversal of a binary tree.

BFS Steps:

1. Initialization: Start from any vertex (e.g., vertex 1).
2. Using Queue:
   • Add starting vertex to the queue.
3. Repeating Steps:
   • Dequeue a vertex and explore it.
   • Add adjacent vertices to the queue.
   • Continue until all vertices are explored.
4. Freedom: Order of visiting adjacent vertices and starting vertex is flexible.

Depth First Search (DFS)

• Method: Once a new vertex is reached, suspend the current vertex exploration and start exploring the new vertex.
• Example:
  • Start from vertex 1, visit 2, suspend, explore 3, and continue deeper.
• Result: Visit all vertices, with an approach of going deeper first.
• Analogy: DFS is like pre-order traversal of a binary tree.

DFS Steps:

1. Initialization: Start from any vertex (e.g., vertex 1).
2. Using Stack:
   • Use stack to manage exploration.
3. Repeating Steps:
   • Push the current vertex onto the stack and explore.
   • Suspend current vertex and start exploring the new vertex.
   • Continue until all vertices are explored.

Comparison: BFS vs. DFS

• BFS: Explore each level fully before moving deeper.
• DFS: Go as deep as possible, then backtrack.
• Data Structures:
  • BFS uses a queue.
  • DFS uses a stack.

Examples and Valid Traversals

• BFS Examples:
  • Different starting points and orders of exploring adjacent vertices lead to different valid BFS results.
• DFS Examples:
  • Various starting points and orders of vertex exploration.

Time Complexity

• BFS and DFS: Both have a time complexity of O(n), where n is the number of vertices.