Breadth First Search BFS Notes 2025 B.Tech/BCA with Applications and Diagrams

Introduction to Breadth First Search (BFS) Breadth First Search (BFS) is a fundamental traversal algorithm in graph theory and is widely used in computer science applications such as networking, pathfinding, and artificial intelligence. In the realm of B.Tech Data Structures Notes 2025, BFS is a core topic in Unit 2 Notes Data Structures. It systematically explores all the vertices of a graph or tree level by level starting from a given source node. BFS is particularly effective in finding the shortest path on unweighted graphs and for exploring connected components in undirected graphs.

Definition of BFS Breadth First Search (BFS) is an algorithm for traversing or searching graph data structures. It starts at a selected node (called the source node) and explores all its neighbors at the present depth before moving on to the nodes at the next depth level.

Characteristics of BFS BFS operates using a queue data structure, which follows the First-In-First-Out (FIFO) principle. The algorithm ensures that each vertex is visited once, making it efficient and reliable for discovering all reachable nodes from a starting node. It is best suited for shortest path problems in unweighted graphs and level-order traversal in trees.

Algorithm for BFS The BFS algorithm can be implemented as follows:

Step-by-step BFS Algorithm:

Create a queue and enqueue the starting vertex. Mark it as visited.
Repeat until the queue is empty: a. Dequeue a vertex from the queue. b. For every adjacent vertex of the dequeued vertex:
- If it has not been visited:
  - Mark it as visited.
  - Enqueue it.

Pseudo-code for BFS:

BFS(Graph G, Vertex v):
    create a queue Q
    mark v as visited and enqueue v into Q
    while Q is not empty:
        current = dequeue Q
        for each neighbor u of current:
            if u is not visited:
                mark u as visited
                enqueue u

ASCII Representation of BFS Traversal: Consider the following undirected graph:

    A
   / \
  B   C
 /     \
D       E

BFS traversal starting from A: Queue Sequence: A -> B, C -> D, E Visited Order: A -> B -> C -> D -> E

📌 Insert Diagram: Graph showing BFS traversal from node A using arrows and levels

Time and Space Complexity

Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges.
Space Complexity: O(V) for storing visited vertices and the queue.

Applications of BFS BFS is used in various applications across computer science domains:

Shortest Path in Unweighted Graphs: Since BFS explores all neighbors before going deeper, the first time it reaches a node is the shortest path.
Peer-to-Peer Networks: BFS is used in search operations in peer-to-peer networks like BitTorrent.
Web Crawlers: Used for level-wise crawling of web pages.
Social Networking Websites: Suggesting friends by finding users within a certain number of connections.
Network Broadcasting: BFS helps in broadcasting information in a computer network efficiently.
Cycle Detection: BFS can also be used to detect cycles in an undirected graph.
Connected Components: BFS helps identify disconnected parts of graphs.

BFS vs DFS (Depth First Search)

Feature	BFS	DFS
Data Structure	Queue	Stack / Recursion
Approach	Level-order	Depth-order
Space Usage	Higher	Lower (for sparse graphs)
Shortest Path	Yes (in unweighted graphs)	No
Applications	Shortest path, Broadcasting	Topological Sort, Cycle Detection

Example Implementation of BFS in C++

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

void BFS(int start, vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while(!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for(auto neighbor : adj[node]) {
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

Example: BFS Traversal Output Consider the following adjacency list representation:

0 -> 1, 2
1 -> 0, 3, 4
2 -> 0
3 -> 1
4 -> 1

Starting from node 0, the output will be: 0 1 2 3 4

Limitations of BFS Although BFS is powerful, it has certain limitations:

Memory Intensive: Requires more memory for large graphs due to queue and visited structures.
Not Suitable for Weighted Graphs: BFS does not handle weighted edges well; Dijkstra’s algorithm is used instead.

Optimizations in BFS Optimized BFS variations include:

Bidirectional BFS: Runs two simultaneous BFS—one from source and one from destination—stopping when they meet.
0-1 BFS: Used for graphs where edge weights are only 0 or 1, utilizing a double-ended queue (deque).

Real-life Analogy BFS can be likened to spreading a rumor in a classroom where each student passes the message to all their friends before it goes further. The message reaches all students layer by layer, not deep into any single branch.

🔹 Short Answer Questions (2-3 Marks)

What is the primary data structure used in BFS? – Queue (FIFO)
What is the time complexity of BFS? – O(V + E)
Where is BFS more advantageous than DFS? – When finding the shortest path in unweighted graphs.
What are the key components of a BFS implementation? – Queue, Visited Array, Graph Representation
How does BFS behave on disconnected graphs? – It explores only the connected component unless applied repeatedly.
Can BFS be used on directed graphs? – Yes, with appropriate direction handling.
Is BFS suitable for infinite graphs? – No, unless boundaries or constraints are specified.

🔸 Long Answer Questions (5-10 Marks)

Explain the BFS algorithm with a suitable example and diagram. – Breadth First Search begins at a source node, exploring all neighbors before diving deeper. Using a queue, it systematically visits each node in layers. Example: In a graph with nodes A–E, if A is connected to B and C, and B is connected to D and C to E, BFS will visit A → B → C → D → E. 📌 Insert Diagram: Example Graph for BFS
Discuss the differences between BFS and DFS with practical use-cases. – BFS uses a queue and explores level-wise, ideal for shortest path and broadcasting. DFS uses a stack or recursion to go deep, suitable for topological sorting and cycle detection.
Write and explain the C++ code to perform BFS on a graph. – [Insert code as above], followed by explanation of queue handling, visited tracking, and adjacency list processing.
Describe the applications of BFS in real-world computing problems. – Used in search engines, GPS routing (unweighted maps), social networking, and more.
How can BFS be modified to work for shortest path in a 2D grid? – Treat each cell as a node, neighbors as adjacent cells, and apply BFS to find the shortest route.

📝 Chapter Summary BFS stands for Breadth First SearchIt uses a Queue (FIFO) for traversalIt visits nodes level by level starting from a source nodeIt is efficient for unweighted shortest path problemsTime complexity is O(V + E)BFS is used in web crawling, social networks, broadcastingIt differs from DFS by approach, data structure, and use-caseIt is applicable to both directed and undirected graphsBFS cannot handle weighted graphs for shortest pathsUse of visited array prevents revisits and infinite loops

📘 Model Paper / Sample Internal Exam Questions