Graph Algorithms-

BFS & DFS

Presented By:
Dr. Parvinder Singh
Assistant Professor
Central University of Punjab, Bathinda

This hand-notes/e-lecture is only for academic purpose and learning, don’t use
the contents for any profit/ research purpose without acknowledge the authors.
Don’t upload this hand note/e-lecture on any website like slide share etc.
 References
• I am very thankful to :-
• Giving credit where credit is due:
• https://www.slideshare.net/KevinJadiya/breadth-first-search-depth-first-search
• https://www.slideshare.net/shimulsakhawat/breadth-first-search-and-depth-first-search
• https://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/51demo-bfs.ppt
• https://visualgo.net/en/sorting
• Books
– Cormen, T.H., Leiserson, C. E., Rivest, R.L., and Stein, C. (2015).
Introduction to Algorithms. New Delhi: PHI Learning Private Limited.
Topic Covered – BFS and DFS Algorithms
 Graph Search (traversal)
▪ How do we search a graph?
– At a particular vertices, where shall we go next?
▪ Two common framework:
▪ the depth-first search (DFS)
▪ the breadth-first search (BFS) and
▪ In DFS, go as far as possible along a single path until reach
a dead end (a vertex with no edge out or no neighbor
unexplored) then backtrack
▪ In BFS, one explore a graph level by level away (explore
all neighbors first and then move on)
 Breadth First Search
 Given
 a graph G=(V,E) – set of vertices and edges
 a distinguished source vertex s
 Given a graph G=(V, E) and a distinguished source vertex s.
Breadth first search systematically explores the edges of
graph G to discover every vertex that is reachable from s.
 The algorithm finds the distance of each vertex from
the source vertex. It finds the minimum distance
(smallest number of edges) from source s to each
reachable vertex.
 It also produces a breadth first tree with root s that
contains all reachable vertices.
 Breadth first search is so named because the algorithm
discovers all vertices at distance k from s before
discovering any vertices at distance k+1
 What is BFS ?????
• B F S stands for Breadth First Search.

• B F S is an algorithm for traversing or searching a

tree or graph data structures.

• It uses a queue data structure for implementation.

• In B F S traversal we visit all the nodes level by level

and the traversal completed when all the nodes are
visited.
 Breadth First Search
• It works for both directed and undirected graphs
• To keep track of progress BFS colors each vertex white,
gray or black. All vertices start with white and may later
become gray and then black. White color denote
undiscovered vertex. Gray and black denote discovered
vertex. While gray denote discovered vertex which is still
under process or in the queue. And black denote
completely processed and discovered vertex.
• d[u] denotes the distance of vertex u from source s
• ᴨ (u) denotes the parent of vertex u
• Adj[u] denotes the adjacent vertices of u
Breadth first search - concepts
 To keep track of progress, it colors each vertex - white,
gray or black.
 All vertices start white.
 A vertex discovered first time during the search
becomes nonwhite.
 All vertices adjacent to black ones are discovered.
Whereas, gray ones may have some white adjacent
vertices.
 Gray represent the frontier between discovered and
undiscovered vertices.
 For any vertex v reachable from s, the path in the
breadth first tree corresponds to the shortest path in
graph G from s to v.
  Algorithm for BFS :
Step 1: Initialize all nodes with status=1.(ready state, White)

Step 2: Put starting node in a queue and change status to

status=2.(waiting state Gray)

Step 3: loop:
repeat step 4 and step 5 until queue gets empty.

Step 4: Remove front node N from queue, process them and

change the status of N to status=3.(processed state
Black)

Step 5: Add all the neighbours of N to the rear of queue and

change status to status=2.(waiting status)
 BFS Algorithm
BFS(G, s) // G is the graph and s is the starting node
1 for each vertex u ∈ V [G] - {s}
2 do color[u] ← WHITE // color of vertex u
3 d[u] ← ∞ // distance from source s to vertex u
4 π[u] ← NIL // predecessor of u
5 color[s] ← GRAY
6 d[s] ← 0
7 π[s] ← NIL
8 Q←Ø // Q is a FIFO - queue
9 ENQUEUE(Q, s)
10 while Q ≠ Ø // iterates as long as there are gray vertices. Lines 10-18
11 do u ← DEQUEUE(Q)
12 for each v ∈ Adj[u]
13 do if color[v] = WHITE // discover the undiscovered adjacent vertices
14 then color[v] ← GRAY // enqueued whenever painted gray
15 d[v] ← d[u] + 1
16 π[v] ← u
17 ENQUEUE(Q, v)
18 color[u] ← BLACK // painted black whenever dequeued
 BFS: Example
r s t u

   

   
v w x y
 BFS: Example
r s t u

 0  

   
v w x y

Q: s
 BFS: Example
r s t u

1 0  

 1  
v w x y

Q: w r
 BFS: Example
r s t u

1 0 2 

 1 2 
v w x y

Q: r t x
 BFS: Example
r s t u

1 0 2 

2 1 2 
v w x y

Q: t x v
 BFS: Example
r s t u

1 0 2 3

2 1 2 
v w x y

Q: x v u
 BFS: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: v u y
 BFS: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: u y
 BFS: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: y
 BFS: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: Ø
 Breadth First Search

-
A B C D

E F G H

front

FIFO Queue
 Breadth First Search

-
A B C D

E F G H

enqueue source node front A

FIFO Queue
 Breadth First Search

-
A B C D

E F G H

dequeue next vertex front A

FIFO Queue
 Breadth First Search

-
A B C D

E F G H

visit neighbors of A front

FIFO Queue
 Breadth First Search

-
A B C D

E F G H

visit neighbors of A front

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

B discovered front B
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of A front B

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I discovered front B I
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

finished with A front B I

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

dequeue next vertex front B I

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

F discovered front I F
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of B front I F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

A already discovered front I F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

finished with B front I F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

dequeue next vertex front I F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

A already discovered front F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

visit neighbors of I front F

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

E discovered front F E
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

visit neighbors of I front F E

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

F already discovered front F E

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

I finished front F E
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

dequeue next vertex front F E

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B

visit neighbors of F front E

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

G discovered front E G
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

F finished front E G
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

dequeue next vertex front E G

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

visit neighbors of E front G

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

E finished front G
FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

dequeue next vertex front G

FIFO Queue
 Breadth First Search

- A
A B C D

E F G H

I B F

visit neighbors of G front

FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F

C discovered front C
FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F

visit neighbors of G front C

FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F G

H discovered front C H
FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F G

G finished front C H
FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F G

dequeue next vertex front C H

FIFO Queue
 Breadth First Search

- A G
A B C D

E F G H

I B F G

visit neighbors of C front H

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

D discovered front H D
FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

C finished front H D
FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

get next vertex front H D

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

visit neighbors of H front D

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

finished H front D
FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

dequeue next vertex front D

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

visit neighbors of D front

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

D finished front

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

dequeue next vertex front

FIFO Queue
 Breadth First Search

- A G C
A B C D

E F G H

I B F G

STOP front

FIFO Queue
 Analysis of Time Complexity
▪ BFS takes O(V) time for initialization
▪ The operations of enqueuing and dequeuing take O(1) time
for each vertex. So the total time devoted to queue
operation for v vertices is O(V).
▪ Now the adjacency list of each vertex is scanned only when
the vertex is dequeued. Then the sum of the lengths of all
the adjacency lists is ɵ(E). So the total time spent in
scanning adjacency lists is O(E).
▪ So the total time complexity of BFS is O(V+E)
 BFS: Time Complexity

▪ Queuing time is O(V) and scanning all edges

requires O(E)
▪ Overhead for initialization is O (V)
▪ So, total running time is O(V+E)
 BFS: Application

• Shortest path problem

 Depth First Search
▪ DFS, go as far as possible along a single path until it reaches
a dead end (that is a vertex with no edge out or no neighbor
unexplored) then backtrack
▪ As the name implies the DFS search deeper in the graph
whenever possible. DFS explores edges out of the most
recently discovered vertex v that still has unexplored edges
leaving it.
 What is DFS ?????

• DFS stands for Depth First Search.

• DFS is an algorithm for traversing or searching a tree or graph

data structures.

• It uses a stack data structure for implementation.

• In DFS one starts at the root and explores as far as possible along
each branch before backtracking.
 Algorithm of DFS
[1]-- Initialize all nodes with status=1.(ready state white)
[2]– Put starting node in the stack and change status
to status=2(waiting state grey).
[3]– L oop:-
Repeat step- 4 and step- 5 until stack get empty.
[4]– Remove top node N from stack process them and
change the status of N processed state (status=3 black).
[5]–Add all the neighbours of N to the top of stack and
change status to waiting status-2.
 Working of DFC : Stack data structure

B D F E
B C
A C C C C C
output
D E A A A A A A
B B B B B
D D D D
F F F F
E E
C
 Depth First Search
▪ To keep track of progress DFS colors each vertex white, gray or
black. Initially all the vertices are colored white. Then they are
colored gray when discovered. Finally colored black when
finished.
▪ Besides creating depth first forest DFS also timestamps each
vertex. Each vertex goes through two time stamps:
▪ Discover time d[u]: when u is first discovered
▪ Finish time f[u]: when backtrack from u or finished u
▪ f[u] > d[u]
Depth first search
 It searches ‘deeper’ the graph when possible.
 Starts at the selected node and explores as far as
possible along each branch before backtracking.
 Vertices go through white, gray and black stages of
color.
 White – initially
 Gray – when discovered first
 Black – when finished i.e. the adjacency list of the vertex is
completely examined.
 Also records timestamps for each vertex
 d[v] when the vertex is first discovered
 f[v] when the vertex is finished
 DFS: Algorithm
DFS(G)
1 for each vertex u ∈ V [G]
2 do color[u] ← WHITE // color all vertices white, set their parents NIL
3 π[u] ← NIL
4 time ← 0 // zero out time
5 for each vertex u ∈ V [G] // call only for unexplored vertices
6 do if color[u] = WHITE // this may result in multiple sources
7 then DFS-VISIT(u)
DFS-VISIT(u)
1 color[u] ← GRAY ▹White vertex u has just been discovered.
2 time ← time +1
3 d[u]= time // record the discovery time
4 for each v ∈ Adj[u] ▹Explore edge(u, v).
5 do if color[v] = WHITE
6 then π[v] ← u // set the parent value
7 DFS-VISIT(v) // recursive call
8 color[u] ← BLACK ▹ Blacken u; it is finished.
9 time ← time +1
10 f [u] = time
 DFS Example
source
vertex
 DFS Example
source
vertex
d | f
1 | | |

| |

| | |
 DFS Example
source
vertex
d | f
1 | | |

2 | |

| | |
 DFS Example
source
vertex
d | f
1 | | |

2 | |

3 | | |
 DFS Example
source
vertex
d | f
1 | | |

2 | |

3|4 | |
 DFS Example
source
vertex
d | f
1 | | |

2 | |

3|4 5 | |
 DFS Example
source
vertex
d | f
1 | | |

2 | |

3|4 5|6 |
 DFS Example
source
vertex
d | f
1 | | |

2|7 |

3|4 5|6 |
 DFS Example
source
vertex
d | f
1 | 8 | |

2|7 |

3|4 5|6 |
 DFS Example
source
vertex
d | f
1 | 8 | |

2|7 9 |

3|4 5|6 |
 DFS Example
source
vertex
d | f
1 | 8 | |

2|7 9|10

3|4 5|6 |
 DFS Example
source
vertex
d | f
1 | 8|11 |

2|7 9|10

3|4 5|6 |
 DFS Example
source
vertex
d | f
1|12 8|11 |

2|7 9|10

3|4 5|6 |
 DFS Example
source
vertex
d | f
1|12 8|11 13|

2|7 9|10

3|4 5|6 |
 DFS Example
source
vertex
d | f
1|12 8|11 13|

2|7 9|10

3|4 5|6 14|

 DFS Example
source
vertex
d | f
1|12 8|11 13|

2|7 9|10

3|4 5|6 14|15

 DFS Example
source
vertex
d | f
1|12 8|11 13|16

2|7 9|10

3|4 5|6 14|15

Depth first search – example
 DFS: Complexity Analysis
▪ Initialization complexity is O(V)
▪ DFS_VISIT is called exactly once for each vertex
▪ And DFS_VISIT scans all the edges which causes
cost of O(E)
▪ Thus overall complexity is O(V + E)
 Container of BFS and DFS

▪ Choice of container used to store discovered

vertices while graph search…
▪ If a queue is used as the container, we get
breadth first search.
▪ If a stack is used as the container, we get depth
first search.
 BFS and DFS - comparison
 Space complexity of DFS is lower than that of BFS.
 Time complexity of both is same – O(|V|+|E|).
 The behavior differs for graphs where not all the vertices
can be reached from the given vertex s.
 Predecessor subgraphs produced by DFS may be different
than those produced by BFS. The BFS product is just one
tree whereas the DFS product may be multiple trees.
 BFS and DFS – possible
applications
Exploration algorithms in Artificial Intelligence
Possible to use in routing / exploration wherever travel is involved. E.g.,
I want to explore all the nearest pizza places and want to go to the nearest
one with only two intersections.
Find distance from my factory to every delivery center.
Most of the mapping software (GOOGLE maps, YAHOO(?) maps) should
be using these algorithms.
Companies like Waste Management, UPS and FedEx?
Applications of DFS
Topologically sorting a directed acyclic graph.
List the graph elements in such an order that all the nodes are listed
before nodes to which they have outgoing edges.
Finding the strongly connected components of a directed graph.
List all the subgraphs of a strongly connected graph which themselves
are strongly connected.
Thank You