Breadth-First Search (BFS)

Overview

• Definition: BFS is an algorithm for searching a graph.
• Behavior:
  • Breadth means broad or wide. The algorithm progresses horizontally before progressing vertically.
  • Uses a queue (First-In-First-Out, FIFO) to keep track of vertices.

Key Concepts

• Visited Nodes: Colored black.
• Queue Nodes: Nodes that are in line to be visited, colored gray.

Example Explanation

• Goal: Find all nodes discoverable from the root node 'A'.
• Steps:
  1. Start with node 'A'.
  2. Pop 'A' from the queue and mark it as visited.
  3. Add adjacent nodes of 'A' to the queue.
  4. Repeat process for each node (B, C, and so on).
• Principle: Visit all nodes at the same level before moving vertically.

Code Walkthrough

• Graph Representation: Using an adjacency list.
• Initialization: Add the root node to both the visited list and the queue.
• Main Loop:
  • Continue while the queue is not empty.
  • Remove the first node from the queue.
  • Check adjacent nodes; add to visited list and queue if not yet visited.

Time Complexity

• Worst Case: Visit each node and explore every edge.
• Big O Notation: O(number of vertices + number of edges).

Additional Resources

• Code Example: Link to a working Python example provided in the description.

Conclusion

• BFS is a fundamental graph search algorithm.
• Make sure to subscribe and share if you found this helpful.