BFS

BFS:

DFS:

BFS:
Lecture Flow

1) Pre-requisites
2) Definition
3) Applications of BFS
4) BFS Variations
5) Practice questions
6) Quote of the day

3
Pre-requisites
● Introduction to Graph
● Basic understanding of Queue Data Structure
● DFS graph traversal algorithm

4
Introduction
- BFS (Breadth-First Search) is a graph traversal algorithm that visits all the
nodes of a graph in breadth-first order.

- It visits all the nodes at a given level before moving on to the next level.

- It starts at the root node and explores all the neighboring nodes before
moving on to the next level.

5
Output: 0, 1, 2, 3, 4, 5, 6 Output: 0, 1, 3, 4, 2, 5, 6
6
What is the bfs traversal of the graph if we start at 0?

7
Answer: 0, 1, 4, 2, 3
8
Visualization

9
10
11
12
13
14
15
16
17
18
19
20
21
22
 Time Complexity Space Complexity

● We have V nodes and E edges ● We have V nodes and we only visit

each node at most once.
● We will only visit a node once, and if
it’s a complete graph we will also ● the space complexity is just the

use every edge. space required to input them in the

visited set.
Time Complexity = O (V + E)
Space Complexity = O (V)

23
Here is an example

24
965. Univalued Binary
Tree

25
 Approach

1. Initialize a variable val who has the same value as the root

2. Initialize a queue with the root node.

3. Loop through each level of the tree( as long as queue is not empty):

● Check if the popped node value is same as val

● If it is not then return False immediately

● Else Add the children of all nodes in the level to the queue.

4. Return True

26
 Time Complexity Space Complexity

● We have V nodes and we visit each ● We store at most M nodes in the queue,
node exactly once. where M is the maximum number of
nodes in a level of the binary tree
● Since the number of edges is constant
for every node, we can say that E = 2V. Space Complexity = O (M)
Which we ignore.

Time Complexity = O (V)

27
Applications

28
1. Level Order Traversal

29
 Level order traversal

● BFS can be used for level order traversal by visiting nodes based on their distance

from the root node.

30
Binary Tree Level Order Traversal

31
 Approach
1. Initialize your queue,visited set, current level array, current level you are currently at.
2. Check the current level with global level:
● If They are not equal, add current level array to answer and set the current level array to empty.
3. Add current node to current level array.
4. Traverse through the neighbours and insert neighbour’s with their level in to your queue.
5. Repeat step 2, 3 , 4 until you left with empty queue.

32
 Time Complexity Space Complexity

● We have V nodes and we visit each ● We store at most M nodes in the queue,
node exactly once. where M is the maximum number of
nodes in a level of the binary tree
● Since the number of edges is constant
for every node, we can say that E = 2V. Space Complexity = O (M)
Which we ignore.

Time Complexity = O (V)

33
2.Finding shortest path in unweighted
graph

34
 Problem
Given an unweighted undirected graph, we have to find the shortest path from the

given source to the given destination using the Breadth-First Search algorithm.

35
 Approach
● Use BFS to traverse a graph or tree.

● Compare visited nodes with the end node. Stop BFS when the end node is found.

● Use either a cleared queue or a boolean flag to mark the end of BFS.

36
How to trace path from start to end node?

37
 Trace path
● We use "prev" array or dictionary to store the reference of the preceding node.

● Using the "prev" value, we can trace the route back from the end node to the starting node.

38
The shortest path

39
 Approach
1. In order to track the shortest path we can use path tracing. We can either maintain a
list or a dictionary. Let’s assume we’re using a dictionary.
2. Once we start our traversal, while we are going through the neighbors of that certain
node, we can make the neighbors a key, and their parent i.e. the current node the
value.
3. Now if our target is not in our dictionary then we can return -1
4. Otherwise we can return the shortest path by going all the way back to the initial
node.

40
 Time Complexity Space Complexity

● We have V nodes and E edges ● We have V nodes and E edges

● We will only visit a node once, and if ● We will store the nodes, and also the
it’s a complete graph we will also use edges.
every edge.
Space Complexity = O (V + E)
Time Complexity = O (V + E)

41
BFS Variations

42
1.Multi-Source BFS

43
 Multi-source BFS
● If we have multiple starting locations for our BFS, there is nothing stopping us from
appending all those locations into our starting queue.

44
Rotting Oranges

45
 Approach
1. Initialize your queue.
2. Traverse through the grid and insert all rotten orange indices in to your queue.
3. After the insertions, while we still have elements in our queue, and as long as we have remaining fresh
oranges in our grid we will continue our iteration.
a. In here we will go through every element in our queue, and we will pop the leftmost
element.
b. As long as that cell is not in bound and the grid is containing a fresh orange.
i. We change that orange to rotten, and we append the new grid in to our queue.
c. Once the above steps are completed then we can decrease the number of fresh oranges
that we have.
4. Now once we are done with going through the queue we can return the minimum time taken to make all
oranges in that grid rotten.

46
 Time Complexity Space Complexity

● Let N be number of rows and M be ● Let N be number of rows and M be

number of columns. number of columns.

● We are traversing through the entire ● At worst we might have the entire grid in
grid. Which would take a time our queue if all grid positions are
complexity of O(N * M). occupied by either rotten or fresh
oranges, so the space complexity will
also be O(N * M).

47
2. BFS with State Storing

48
 BFS with state storing
● In some problems, a cell can be revisited with new information. To keep track of previously
visited cells with different states, we mark each cell visited with a combination of its state and
cell_id.

● In other words, We revisit same node but with different information.

49
Shortest Path with Alternating Colors

50
Is there a valid path to node “4”?

51
 Approach
1. Create a new graph but for every node, we we have two types of edges, red edges, and
blue edges.
2. Initialize a queue with the root node, the starting color, and the starting distance.
3. Loop through the queue:
● Compare the current distance for the node, with the distance in the answer array.
● Add the neighbours in the opposite color list of the node
4. Return the list of distances

52
 Time Complexity Space Complexity

● We have V nodes and E edges ● We have V nodes and E edges

● We will only visit a node once, and if ● We will store the nodes, and also the
it’s a complete graph we will also use edges.
every edge.
Space Complexity = O (V + E)
Time Complexity = O (V + E)

53
Common Pitfalls

54
 Not maintaining visited nodes

It is important to keep track of visited nodes to avoid revisiting them and

getting stuck in an infinite loop.

55
 Improper handling of visited nodes
In certain situations, it's possible to return to a cell with new data. While we might
label a node as visited based on earlier visits, we may not always consider it as
such when encountering it again with new information.

56
 Not handling disconnected graphs

BFS may not visit all nodes in a disconnected graph if it starts from a single
source node. To address this, multiple BFS runs may be required starting from
different source nodes.

57
 Using the wrong data structure

BFS requires a data structure that allows for FIFO (first in, first out) access, such
as a queue. If you use a data structure that does not allow for FIFO access, such
as a stack, you may not get the correct traversal order.

58
 Not Checking for Goal State

It's essential to incorporate checks for the goal state within the BFS algorithm.
Failure to include this check can lead to unnecessary exploration of the entire
search space, even after finding the solution.

59
 Practice Problems
● Shortest Path in Binary Matrix ● Nearest Exit from Entrance in Maze

● Keys and Rooms ● Snakes and Ladders

● Open the lock ● Rotting Oranges

● 01 Matrix ● Race Car

● Map of highest peak ● Bus Routes

● As Far from Land as Possible ● Word Ladder

● All Nodes Distance K in Binary Tree

60
 Quote of the day
"Exploration is really the essence of the
human spirit."

Frank Borman

61