Breadth First Search Algorithm

Breadth First Search Flaticon

Introduction to Breadth First Search algorithm

Breadth First Search (BFS) algorithm is a fundamental graph traversal algorithm used to explore and analyze the structure of a graph or tree. It is a systematic method for visiting all the vertices and edges of a graph, starting from a specific source vertex and moving outward in layers.

Breadth First Search is a simple and intuitive algorithm that is primarily used for two main tasks: Exploration of Graphs and Connectivity Analysis. 

What is Breadth First Search?

Breadth First Search (BFS) is a graph traversal algorithm used to explore and analyze the structure of a graph or tree.

  • It systematically visits all the vertices and edges of a graph, starting from a specific source vertex and moving outward in layers.
  • BFS employs a queue data structure to maintain the order of traversal, ensuring that it visits vertices in order of their distance from the source.
  • It is often used to find the shortest path in unweighted graphs, perform network analysis, determine graph connectivity, and solve various graph-related problems.

 

Breadth First Search Algorithm

The algorithm follows these basic steps:

  1. Start with a source vertex.

  2. Initialize a queue (FIFO data structure) to keep track of the vertices to be visited.

  3. Mark the source vertex as visited and enqueue it.

  4. While the queue is not empty, do the following: a. Dequeue a vertex from the queue. b. Visit and process the dequeued vertex. c. Enqueue all the unvisited neighbors of the dequeued vertex.

  5. Continue this process until the queue is empty.

Implementation of BFS

Here’s a Python implementation of the Breadth First Search algorithm for traversing a graph. In this example, we assume the graph is represented as an adjacency list.

from collections import deque

def bfs(graph, start_vertex):
    visited = set()  # To keep track of visited vertices
    queue = deque()  # Initialize a queue for BFS

    visited.add(start_vertex)  # Mark the start_vertex as visited
    queue.append(start_vertex)  # Enqueue the start_vertex

    while queue:
        current_vertex = queue.popleft()  # Dequeue the vertex and process it
        print(current_vertex)  # Print or process the current_vertex as needed

        for neighbor in graph[current_vertex]:
            if neighbor not in visited:
                visited.add(neighbor)  # Mark the neighbor as visited
                queue.append(neighbor)  # Enqueue the neighbor

# Define a sample graph as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start_vertex = 'A'  # Starting vertex for BFS
print("Breadth First Search starting from vertex A:")
bfs(graph, start_vertex)

Output :

Breadth First Search starting from vertex A:
A
B
C
D
E
F

Explanation :

The Python code implements the Breadth First Search (BFS) algorithm for graph traversal. It begins at a specified starting vertex (‘A’ in this case) and explores the graph systematically. A queue is employed to manage the order of exploration, and a set keeps track of visited vertices to prevent revisiting. The code prints or processes each visited vertex and its neighbors. The BFS algorithm ensures that vertices are visited in layers, making it useful for tasks like finding the shortest path.

BFS Algorithm Pseudocode

Pseudocode for the Breadth First Search algorithm:

BFS(graph, start_vertex):
    queue = create_queue()
    mark start_vertex as visited
    enqueue start_vertex into the queue
    
    while the queue is not empty:
        current_vertex = dequeue from the queue
        process current_vertex
        
        for each unvisited neighbor of current_vertex:
            mark neighbor as visited
            enqueue neighbor into the queue

Breadth First Search Algorithm in AI

An overview of the Breadth-First Search (BFS) algorithm in the context of Artificial Intelligence (AI):

Applications of Breadth First Search Algorithm

To Wrap it up: 

Breadth First Search is a versatile and powerful algorithm for exploring and analyzing graphs. Its simplicity and efficiency make it a fundamental tool in computer science, enabling a wide range of applications, from pathfinding to network analysis and more. Understanding the BFS algorithm is essential for anyone working with graphs or graph-like data structures.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Question 1.

How does BFS differ from Depth First Search (DFS)?

BFS explores a graph layer by layer, while DFS explores one branch as deeply as possible before backtracking. BFS is often used for finding the shortest path, while DFS is used for tasks like topological sorting and cycle detection.

Question 2.

What data structures are commonly used in BFS?

BFS typically uses a queue data structure to maintain the order of traversal and a set (or other data structure) to keep track of visited vertices.

Question 3.

What is the time complexity of BFS?

The time complexity of BFS is O(V + E), where V is the number of vertices, and E is the number of edges in the graph.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription