Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that systematically visits all nodes in a graph, exploring all the nodes at a particular level before moving on to the next level.

Definition of Breadth-First Search

Breadth-First Search starts at a specific 'source' node and explores all its neighboring nodes before moving on to their neighbors. This process continues until all nodes in the component containing the source have been explored.

Characteristics of Breadth-First Search

• Level-by-Level Traversal: BFS visits nodes in a level-wise order. It first visits all nodes at one level before moving to the next.
• Queue Utilization: BFS uses a queue data structure to manage the order of node traversal. Nodes are dequeued for exploration and their unvisited neighbors are enqueued.
• Marking Visited Nodes: To avoid processing a node more than once, BFS marks each node as visited when it is enqueued.
• Uniformity in Path Lengths: BFS is especially useful in finding the shortest path in unweighted graphs, as it visits nodes in order of their distance from the source, ensuring the shortest path is found first.

Implementation of Breadth-First Search

1. Define a Queue size as total number of vertices in the graph.
2. Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
3. Visit all the non-visited adjacent vertices of the vertex which is in front of the Queue and insert them into the Queue.
4. When there is no new vertex to visited from the vertex at front of the Queue then delete that vertex.
5. Repeat steps 3 and 4 until queue becomes empty.
6. When queue becomes empty, then produce final spanning tree by removing unused edges from the graph

BFS(graph, start_vertex):
    Create a queue Q
    Mark start_vertex as visited and enqueue it into Q
    While Q is not empty:
        vertex = Q.dequeue()  // Remove the vertex from the front of the queue
        Visit(vertex)
        For each neighbor 'n' of vertex:
            If n is not visited:
                Mark n as visited
                Enqueue n into Q

Advantages of Breadth-First Search

• Simple and easy to implement.
• Guaranteed to find all reachable nodes.
• Efficient for finding shortest paths in unweighted graphs.

Disadvantages of Breadth-First Search

• May be less efficient than Depth-First Search (DFS) for large graphs.
• May explore unnecessary nodes if searching for a specific target node.