Scribd
Upload
3 views6 pages

Understanding Depth First Search (DFS)

Uploaded by

padma sri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views6 pages

Understanding Depth First Search (DFS)

Uploaded by

padma sri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DEPTH FIRST SEARCH

WHAT IS DFS?

DFS is a graph traversal algorithm that explores as far as possible


along each branch before backtracking. It can be implemented using
recursion (implicit stack) or an explicit stack (iterative approach).

How DFS Works?


Starts at a source node and explores deeply before backtracking.
Follows LIFO order, using a stack for traversal.
Marks nodes as visited to prevent cycles.
EXAMPLE
6

1 5

SOURCE = 1
4 2 7

1,4,3,10,9,2,5,6,7,8
3 8

10 9
DFS SPANNING TREE
6

1 5

4 2 7

3 8

10 9
ALGORITHM
Algorithm DFS(v)
// Given an undirected(directed) graph G = (V,E) with
// n vertices and an array visited[] initially set
//to zero, this algorithm visits all vertices
//reachable from v. G and visited[] are global.
{
visited[v] :=1;
for each vertex w adjacent from v do
{
if (visited[w] = 0) then DFS(w);
}
}
THANK YOU

You might also like