Data structure & algorithms (BFS & DFS notes)

Data Structures and Algorithm
(CC-2042)
Lecture 31
E N G R. D R B I L A L A S H FA Q A H M E D
S C H O O L O F S Y S T E M S A N D T E C H N O LO GY ( S S T )
C O M P U T E R S C I E N C E FA C U LT Y

,Breadth-First Search (BFS)
Breadth-First Search (BFS) is a fundamental graph traversal algorithm that
explores a graph in “layers.”
Key Concept
•Starting Point: You choose a source vertex.
•Layer-by-Layer Exploration:
• Visit all direct neighbors of the source (distance 1).
• Then, for each neighbor, visit their unvisited neighbors (distance 2), and so on
• This naturally proceeds in “layers” from the source.

This approach guarantees that you discover vertices in order of their distan
(in edges) from the source.



09/06/2025 DS

,How It Works (Algorithm Steps)
Initialization:
 Mark all vertices as “not visited.”
 Use a queue data structure to keep track of vertices to process.
Enqueue Source:
 Mark the source vertex as visited and enqueue it.
Main Loop:
 While the queue is not empty:
 Dequeue a vertex u.
 Process u (e.g., print it or record its order).
 For each unvisited neighbor v of u:
 Mark v as visited.
 Enqueue v.
Terminate when the queue is empty (no more vertices to explore).



09/06/2025 DS

, Shortest Path (Unweighted
Graph)
Distance Layers: In an unweighted graph, BFS naturally finds the shortes
number of edges between the source and every other reachable vertex.
Reason: By the time BFS reaches a vertex, it has taken the minimum
possible steps from the source (due to the layer-by-layer exploration).




09/06/2025 DS