��Breadth First Search Traversal(BFS)�

​

Smt M.Jeevana Sujitha

Assistant Professor

Department of Computer science and Engineering

SRKR Engineering College, Bhimavaram, AP-534204

​

Advanced Data Structures Graph Traversals

� Objectives�

• To understand the concept of BFS Traversal

​

​

• How to use BFS Traversal in solving the real world problems

​

​

​

​

​

​

​

Breadth First Search Traversal(BFS)

• BFS traversal of a graph produces a spanning tree as final result.

​

​

• Spanning Tree is a graph without loops.

​

​

• We use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal.

Steps to implement BFS Traversal

• Step 1 - Define a Queue of size total number of vertices in the graph.
• Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
• Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and insert them into the Queue.
• Step 4 - When there is no new vertex to be visited from the vertex which is at front of the Queue then delete that vertex.
• Step 5 - Repeat steps 3 and 4 until queue becomes empty.
• Step 6 - When queue becomes empty, then produce final spanning tree by removing unused edges from the graph

Example�

Consider the following graph to perform BFS Traversal

• Graph Traversals

A

B

C

D

E

F

G

BFS Traversal �

• Step-1:Select the vertex A as starting vertex(visit A)
• Insert A into the Queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-2:Visit the adjacent vertex of A which is not visited(D,E,B)
• Insert newly visited vertices into the Queue and delete A from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-3:Visit all adjacent vertices of D which are not visited(there is no vertex)
• Delete D from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-4:Visit all the adjacent vertices of E which are not visited(C,F)
• Insert newly visited vertices into the Queue and delete E from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-5:Visit all the adjacent vertices of B which are not visited(there is no vertex)
• Delete B from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-6:Visit all the adjacent vertices of C which are not visited(G)
• Insert newly visited vertex into the queue and delete C from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-7:Visit all the adjacent vertices of F which are not visited(there is no vertex)
• Delete F from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Step-8:Visit all the adjacent vertices of G which are not visited(there is no vertex)
• Delete G from the queue

A

B

C

D

E

F

G

Queue

BFS Traversal �

• Queue becomes empty.so,stop the process of BFS
• Final result of the spanning tree is shown below

A

B

C

D

E

F

G

​

​

​

Thank you