Depth First Search

Graph Traversal
S.Bharathiraja,
Associate Professor,
School of Computer Science and Engineering,
VIT – University - Chennai
Graph Traversal
Types:
1. DFS Depth First Search
2. BFS  Breadth First Search

Graph Traversal
DFS Depth First Search
Depth-first search (DFS) is an algorithm for
traversing or searching tree or graph data structures.
One starts at the root (selecting some node as the
root in the graph case) and explores as far as
possible along each branch before backtracking.

Depth First Search
B F
C
A
E
H
G D
B F
C
A
E
H
G D
Depth First Search
B F
C
E A
H A
G D
Result : A
Make use of Stack for performing DFS in a graph
Select a vertex randomly say ‘A’ and mark it visited

Depth First Search
B F B F
C C
E A A
E B
H H
G D G D
A
Result : A B
Adjacent vertices of ‘A’ are B,G & D.
Select the least vertex out of B,G & D, say ‘B’ and mark it visited
& Push it on to stack and update the result.

Depth First Search
B F B F
C C
E A A E
E B
H H
G D G D
A
Result : A B E
Adjacent vertices of ‘B’ are A,E & F.
‘A’ is already visited.
Select the least vertex out of E & F, say ‘E’ and mark it visited &
Push it on to stack and update the result.

Depth First Search
B F B F
G
C C
E A A E
E B
H H
G D G D
A
Result : A B E G
Adjacent vertices of ‘E’ are B & G.
‘B’ is already visited.
Mark ‘G’ as visited & Push it on to stack and update the result.
Depth First Search
B F B F
G
X
C C
E A A E
E B
H H
G D G D
A
Result : A B E G
Adjacent vertices of ‘G’ are A & E.
Both ‘A’ & ‘E’ are already visited.
Pop ‘G’ out of stack which makes us to point at vertex ‘E’.

Depth First Search
B F B F
C C
E A A XE
E B
H H
G D G D
A
Result : A B E G
Adjacent vertices of ‘E’ are B & G.
Both ‘B’ & ‘G’ are already visited.
Pop ‘E’ out of stack which makes us to point at vertex ‘B’.

Depth First Search
B F B F
C C
E A A F
E B
H H
G D G D
A
Result : A B E G F
Adjacent vertices of ‘B’ are E, A & F.
Both ‘E’ & ‘A’ are already visited.
Mark ‘F’ as visited, push it on to stack and update the result.

Depth First Search
B F B F
C
C C
E A A F
E B
H H
G D G D
A
Result : A B E G F C
Adjacent vertices of ‘F’ are B, D & C .
Vertex ‘B’ is already visited. Out of ‘D’ & ‘C’ mark ‘C’ as marked.
Push ‘C’ on to stack mark it visited and update the result.

Depth First Search
B F B F H
C
C C
E A A F
E B
H H
G D G D
A
Result : A B E G F C H
Adjacent vertices of ‘C’ are F & H .
Vertex ‘F’ is already visited, So mark ‘H’ as visited.
Push ‘H’ on to stack mark it visited and update the result.

Depth First Search
B F B F
C
C C
E A A F
E B
H H
G D G D
A
Adjacent vertices of ‘H’ is ‘C’ .
Vertex ‘C’ is already visited.
Pop ‘H’ from the stack, so that top pointer points to ‘C’.
Depth First Search
B F B F
C C
E A A F
E B
H H
G D G D
A
Adjacent vertices of ‘C‘ are ‘F’ & ‘H’ .
Vertex ‘F’ & ‘H’ are already visited.
Pop ‘C’ from the stack, so that top pointer points to ‘F’.
Depth First Search
B F B F
D
C C
E A A F
E B
H H
G D G D
A
Result : A B E G F C H D
Adjacent vertices of ‘F‘ are ‘B’, ‘D’ & ‘C’ .
Vertex ‘B’ & ‘C’ are already visited, So mark ‘D’ as visited.
Push ‘D’ on to the stack and update the result.

Depth First Search
B F B F
C C
E A A F
E B
H H
G D G D
A
Adjacent vertices of ‘D‘ are ‘A’ & ‘F’ .
Vertex ‘A’ & ‘F’ are already visited.
Pop ‘D’ from the stack, so that the top pointer points to ‘F’.
Depth First Search
B F B F
C C
E A A
E B
H H
G D G D
A
Adjacent vertices of ‘F‘ are ‘B’, ‘D’ & ‘C’ .
Vertices ‘B’, ‘D’ & ‘C’ are already visited.
Pop ‘F’ from the stack, so that the top pointer points to ‘B’.
Depth First Search
B F B F
C C
E A A
E
H H
G D G D
A
Adjacent vertices of ‘B‘ are ‘E’, ‘A’ & ‘F’ .
Vertices ‘E’, ‘A’ & ‘F’ are already visited.
Pop ‘B’ from the stack, so that the top pointer points to ‘A’.
Depth First Search
B F B F
C C
E A A
E
H H
G D G D
Adjacent vertices of ‘A‘ are ‘B’, ‘G’ & ‘D’ .
Vertices ‘B’, ‘G’ & ‘D’ are already visited.
Pop ‘A’ from the stack, if stack is empty stop the process. Traversal
out put would be A B  EGFCHD

Depth First Search Algorithm
DFS(G, u):
let St be stack
Push u in the stack
mark u as visited.
while ( St is not empty)
v = Node at the top of stack
remove the node from stack
for all neighbors adj_node of v in Graph
G:
if adj_node is not visited :
mark adj_node as visited
push adj_node in stack
Exercise
3
1
4 5
2 2
4
3
Solution: a  b  c  f  e  d  g

Depth First Search

Uploaded by

Copyright:

Available Formats

Depth First Search

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Depth First Search

Uploaded by

Copyright:

Available Formats

Graph Traversal

1. DFS Depth First Search

2. BFS  Breadth First Search

DFS Depth First Search

Depth-first search (DFS) is an algorithm for

traversing or searching tree or graph data structures.

One starts at the root (selecting some node as the

root in the graph case) and explores as far as

possible along each branch before backtracking.

Make use of Stack for performing DFS in a graph

Select a vertex randomly say ‘A’ and mark it visited

Adjacent vertices of ‘A’ are B,G & D.

& Push it on to stack and update the result.

Adjacent vertices of ‘B’ are A,E & F.

‘A’ is already visited.

Push it on to stack and update the result.

Adjacent vertices of ‘E’ are B & G.

‘B’ is already visited.

Adjacent vertices of ‘G’ are A & E.

Both ‘A’ & ‘E’ are already visited.

Pop ‘G’ out of stack which makes us to point at vertex ‘E’.

Adjacent vertices of ‘E’ are B & G.

Both ‘B’ & ‘G’ are already visited.

Pop ‘E’ out of stack which makes us to point at vertex ‘B’.

Adjacent vertices of ‘B’ are E, A & F.

Both ‘E’ & ‘A’ are already visited.

Mark ‘F’ as visited, push it on to stack and update the result.

Adjacent vertices of ‘F’ are B, D & C .

Push ‘C’ on to stack mark it visited and update the result.

Adjacent vertices of ‘C’ are F & H .

Vertex ‘F’ is already visited, So mark ‘H’ as visited.

Push ‘H’ on to stack mark it visited and update the result.

Adjacent vertices of ‘H’ is ‘C’ .

Vertex ‘C’ is already visited.

Adjacent vertices of ‘C‘ are ‘F’ & ‘H’ .

Vertex ‘F’ & ‘H’ are already visited.

Adjacent vertices of ‘F‘ are ‘B’, ‘D’ & ‘C’ .

Push ‘D’ on to the stack and update the result.

Adjacent vertices of ‘D‘ are ‘A’ & ‘F’ .

Vertex ‘A’ & ‘F’ are already visited.

Adjacent vertices of ‘F‘ are ‘B’, ‘D’ & ‘C’ .

Vertices ‘B’, ‘D’ & ‘C’ are already visited.

Adjacent vertices of ‘B‘ are ‘E’, ‘A’ & ‘F’ .

Vertices ‘E’, ‘A’ & ‘F’ are already visited.

Adjacent vertices of ‘A‘ are ‘B’, ‘G’ & ‘D’ .

Vertices ‘B’, ‘G’ & ‘D’ are already visited.

out put would be A B  EGFCHD

You might also like