�ݺ�ߣ

Breadth-first search
 Breadth-first search (BFS) is an algorithm for traversing
or searching tree or graph data structures.
 It starts at the tree root (or some arbitrary node of a
graph, sometimes referred to as a ‘search key’), and
explores all of the neighbor nodes at the present depth
prior to moving on to the nodes at the next depth level.
 It is implemented using a queue(FIFO).
 BFS traverses the tree “shallowest node first”, it would
always pick the shallower branch until it reaches the
solution (or it runs out of nodes, and goes to the next
branch).

Algorithm
3
 Declare a queue and insert the starting vertex.
 Initialize a visited array and mark the starting vertex as
visited.
 Follow the below process till the queue becomes empty:
 Remove the first vertex of the queue.
 Mark that vertex as visited.
 Insert all the unvisited neighbors of the vertex into the
queue.

⚫Consider the Following Example
Example-1

Breadth First Search- STEP1
 Choose the Starting Vertex as A
 VISIT A
 Insert A into the Queue
A
QUEUE:

⚫Visit all adjacent vertices of A which
are not visited(Here: D,E,B)
⚫Insert newly visited vertices into the queue
and delete A from the Queue
D E B
QUEUE:
RESULT: A

⚫Visit all adjacent vertices of D which
are not visited (No Vertex)
⚫Delete D from the Queue
E B
QUEUE:
RESULT: A D

⚫ Visit all adjacent vertices of E which are not visited(Here
C, F)
⚫ Insert newly visited vertices into the queue and delete E
from the Queue
B C F
QUEUE:
RESULT: A D E

⚫Visit all adjacent vertices of B which
are not visited(No Vertex)
⚫Delete B from the Queue
C F
QUEUE:
RESULT: A D E B

⚫ Visit all adjacent vertices of C which are
not visited(Here G)
⚫ Insert newly visited vertices into the queue and delete
C from the Queue
F G
QUEUE:
RESULT: A D E B C

⚫ Visit all adjacent vertices of F which are not
visited(Here No Vertex)
⚫ Delete F from the Queue
G
QUEUE:
RESULT: A D E B C F

⚫Visit all adjacent vertices of G which are
not visited(Here No Vertex)
⚫Delete G from the Queue
QUEUE:
Queue Empty, End the
Process
RESULT: A D E B C F G

BFS Traversal - Result
AD EBCF G

14
Advantages
• BFS will provide a solution if any solution exists.
• If there are more than one solution for a given problem, then BFS
will provide minimum solution which requires the least number of
steps.
Disadvantage
• It requires lot of memory since each level of the tree must be saved
into memory to expand the next level.
• BFS needs lot of time if the solution is far a way from the root.

Example
15
 BFS Output will be ?
 Output of BFS : 1 2 3 4 5 6 7 8 9 10 11 12

19
Time complexity: Equivalent to the number of nodes
traversed in BFS until the shallowest solution.
T(n) = 1 + n^2 + n^3 + ... + n^s = O(n^s)
• s = the depth of the shallowest solution.
• n^i = number of nodes in level i.
Space complexity: Equivalent to how large can the fringe
get.
S(n) = O(n^s)

20
• Completeness: BFS is complete, meaning for a given search
tree, BFS will come up with a solution if it exists.
• Optimality: BFS is optimal as long as the costs of all edges
are equal.

�ݺ�ߣ

Breadth First Search with example and solutions

Recommended

More Related Content

Similar to Breadth First Search with example and solutions (20)

Recently uploaded (20)

Breadth First Search with example and solutions