1 of 27

�Depth First Search Traversal(DFS)�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

2 of 27

� Objectives�

To understand the concept of DFS Traversal

How to use DFS Traversal in solving the real world problems

To understand when to use DFS and when to use BFS

3 of 27

Introduction

Graph traversal is a technique used for a searching vertex in a graph.

The graph traversal is also used to decide the order of vertices is visited in the search process.

A graph traversal finds the edges to be used in the search process without creating loops. That means using graph traversal we visit all the vertices of the graph without getting into looping path.

4 of 27

Graph Traversal Techniques

The following are the two graph traversal techniques

Depth First Search Traversal(DFS)

Breadth First Search Traversal(BFS)

5 of 27

Depth First Search Traversal(DFS)

DFS traversal of a graph produces a spanning tree as final result.

Spanning Tree is a graph without loops.

We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.

6 of 27

Depth First Search Traversal(DFS)

DFS traversal of a graph produces a spanning tree as final result.

Spanning Tree is a graph without loops.

We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal.

7 of 27

Steps to implement DFS Traversal

Step 1 - Define a Stack of size total number of vertices in the graph.
Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and push it on to the stack.
Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of the stack.
Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

8 of 27

Example�

Consider the following graph to perform DFS Traversal

Graph Traversals

A

B

C

D

E

F

G

9 of 27

DFS Traversal �

Step-1:Select the vertex A as starting vertex(visit A)

Push A onto the stack

A

B

C

D

E

F

G








A

Stack

10 of 27

DFS Traversal �

Step-2:Visit the adjacent vertex of A which is not visited(B)
Push newly visited vertex B onto the stack

A

B

C

D

E

F

G







B
A

Stack

11 of 27

DFS Traversal �

Step-3:Visit the adjacent vertex of B which is not visited(C)
Push vertex C onto the stack

A

B

C

D

E

F

G






C
B
A

Stack

12 of 27

DFS Traversal �

Step-4:Visit the adjacent vertex of C which is not visited(E)
Push vertex E onto the stack

A

B

C

D

E

F

G





E
C
B
A

Stack

13 of 27

DFS Traversal �

Step-5:Visit the adjacent vertex of E which is not visited(D)
Push vertex D onto the stack

A

B

C

D

E

F

G




D
E
C
B
A

Stack

14 of 27

DFS Traversal �

Step-6:There is no new vertex to be visited from D.so use back track
Pop vertex D from the stack

A

B

C

D

E

F

G





E
C
B
A

Stack

15 of 27

DFS Traversal �

Step-7:visit any adjacent vertex of E which is not visited(F)
Push F onto the stack

A

B

C

D

E

F

G




F
E
C
B
A

Stack

16 of 27

DFS Traversal �

Step-8:visit any adjacent vertex of F which is not visited(G)
Push G onto the stack

A

B

C

D

E

F

G



G
F
E
C
B
A

Stack

17 of 27

DFS Traversal �

Step-9:There is no new vertex to be visited from G.so use backtrack
Pop G from the stack

A

B

C

D

E

F

G




F
E
C
B
A

Stack

18 of 27

DFS Traversal �

Step-10:There is no new vertex to be visited from F.so use backtrack
Pop F from the stack

A

B

C

D

E

F

G





E
C
B
A

Stack

19 of 27

DFS Traversal �

Step-11:There is no new vertex to be visited from E.so use backtrack
Pop E from the stack

A

B

C

D

E

F

G






C
B
A

Stack

20 of 27

DFS Traversal �

Step-12:There is no new vertex to be visited from C.so use backtrack
Pop C from the stack

A

B

C

D

E

F

G







B
A

Stack

21 of 27

DFS Traversal �

Step-13:There is no new vertex to be visited from B.so use backtrack
Pop B from the stack

A

B

C

D

E

F

G








A

Stack

22 of 27

DFS Traversal �

Step-14:There is no new vertex to be visited from A.so use backtrack
Pop A from the stack

A

B

C

D

E

F

G

Stack

23 of 27

DFS Traversal �

Stack becomes empty.So stop DFS traversal
Final result of DFS traversal is the following spanning tree

A

B

C

D

E

F

G

24 of 27

Applications of DFS �

If we perform DFS on unweighted graph, then it will create minimum spanning tree for all pair shortest path tree

We can detect cycles in a graph using DFS. If we get one back-edge during BFS, then there must be one cycle.

25 of 27

Applications of DFS �

If we perform DFS on unweighted graph, then it will create minimum spanning tree for all pair shortest path tree

We can detect cycles in a graph using DFS. If we get one back-edge during BFS, then there must be one cycle.

26 of 27

Applications of DFS �

Using DFS we can find path between two given vertices u and v.

We can perform topological sorting is used to scheduling jobs from given dependencies among jobs. Topological sorting can be done using DFS algorithm.

Using DFS, we can find strongly connected components of a graph. If there is a path from each vertex to every other vertex, that is strongly connected.

27 of 27

Thank you