Breadth First Search

Explanation

- Breadth First Search (BFS) is a graph traversal algorithm used to search nodes in a graph or tree data structure. It explores all the neighboring nodes at the present level before moving on to nodes at the next level. BFS uses a queue data structure to keep track of the nodes to be processed.

-

• Steps:

  • Start from a node (typically the root node or any arbitrary node).
  • Mark the node as visited and enqueue it.
  • While the queue is not empty:
    • Dequeue the front node.
    • Visit all its adjacent unvisited nodes and enqueue them.
• This process continues until all nodes are visited.

• Time Complexity:

  • For a graph with V vertices and E edges, the time complexity of BFS is O(V + E).