BFS(Breadth First Search)

Breadth-First Search

 "BFS" typically stands for "Breadth-First Search," which is a graph traversal algorithm. In BFS, you explore a graph level by level, starting from a chosen source vertex. The algorithm visits all the vertices at the current level before moving on to the next level.

Here's a basic outline of the BFS algorithm:

1. Enqueue the source vertex and mark it as visited.

2. While the queue is not empty:

   a. Dequeue a vertex from the queue.

   b. Process the dequeued vertex (e.g., print it or perform some operation).

   c. Enqueue all adjacent vertices that haven't been visited yet and mark them as visited.

This process continues until the queue is empty, meaning all reachable vertices have been visited.

BFS is commonly used in various applications, such as finding the shortest path in an unweighted graph or exploring all connected components in a graph.

Here's a simple implementation of the Breadth-First Search (BFS) algorithm in Python. In this example, I assume that the graph is represented as an adjacency list:

 from collections import deque

def bfs(graph, start):

    visited = set()  # To keep track of visited vertices

    queue = deque([start])  # Initialize the queue with the starting vertex

    while queue:

        vertex = queue.popleft()  # Dequeue a vertex

        if vertex not in visited:

            print(vertex, end=' ')  # Process the vertex (e.g., print it)

            visited.add(vertex)

            # Enqueue all adjacent vertices that haven't been visited yet

            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not

                                     in visited)

# Example usage:

# Representing a simple undirected graph as an adjacency list

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F', 'G'],

    'D': ['B'],

    'E': ['B', 'H'],

    'F': ['C'],

    'G': ['C'],

    'H': ['E']

}

start_vertex = 'A'

print("BFS starting from vertex", start_vertex)

bfs(graph, start_vertex)

This code performs BFS on the given graph starting from the specified vertex (`start_vertex`). Adjust the `graph` dictionary to represent your specific graph structure.