Scribd
Upload
15 views12 pages

Depth Search Algorithm

Graph traversal is a method for visiting all vertices of a graph systematically, essential for tasks like searching elements, finding paths, and detecting cycles. Depth-First Search (DFS) is a specific traversal technique that explores paths from a starting vertex using a stack data structure, marking nodes as visited to avoid repetition. The procedure involves pushing unvisited adjacent nodes onto the stack and backtracking until all nodes are visited.

Uploaded by

keerthi2005srinivas
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
15 views12 pages

Depth Search Algorithm

Graph traversal is a method for visiting all vertices of a graph systematically, essential for tasks like searching elements, finding paths, and detecting cycles. Depth-First Search (DFS) is a specific traversal technique that explores paths from a starting vertex using a stack data structure, marking nodes as visited to avoid repetition. The procedure involves pushing unvisited adjacent nodes onto the stack and backtracking until all nodes are visited.

Uploaded by

keerthi2005srinivas
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

Graph traversal ff

Graph traversal is the process of visiting all vertices of a


graph exactly once in a systematic way.

Need for Graph traversal:


Search an element
Find paths
Check connectivity
Detect cycles
Find shortest paths
Solve real-world problems (maps, networks, AI)
Depth-First Search (DFS)ff

Depth First Search (DFS) is a graph traversal method that


starts from a source vertex and explores each path
completely before backtracking and exploring other paths.
Stack datastructure used for DFS

Procedure:
Start at the initial node
Mark the node as visited
unvisited adjacent node push to stack
Repeat step 2 and 3 until no unvisited adjacent node
exists
Backtrack and repeat for remaining nodes
Stop when all nodes are visited
Depth-First Search (DFS) ff

//Let G(V,E) is a set of vertices and edges


Let v be the starting vertex
//visited [i]=false initially for all vertices
//For any node i, visited[i]=true if has already been visited ,else it contains false
//stack is represented as s.
{
for (all v in G)
visited[v]=false;
Add source vertex ‘v’ to stack ‘s’
while(stack is not empty){
pop top element N from staack s;
if(visited[N]==false) then {
visited[N]=true;
}
for all vertices W adjacent from N do{ push w into stack s;}
}}
Depth-First Search (DFS)
ff
Starting point:1

1 2 0 1 2
1 0 2 0 F
4
2 0 1 3 4 1 F
2 2

0 3 3 2 2 F
4
3 F
22
4 F
STACK

Visited
Depth-First Search (DFS)
ff
Starting point:1

1 2 0 1 2
1 0 2 0 F
4
2 0 1 3 4 1 F
2 2

0 3 3 2 2 F
4
3 F
Push the node 1 to stack 22
4 F
1 STACK

Visited
Depth-First Search (DFS) ff
Starting point:1

1 2 0 1 2
1 0 2 0 F
4
2 0 1 3 4 1 T
2 2

0 3 3 2 2 F
4
3 F
push adjacent edjes which is unvisited 22
4 F
0 2 STACK
1
visited[1]=true
1 Visited
Depth-First Search (DFS) ff

1 2 0 1 2
1 0 2 0 F
4
2 0 1 3 4 1 T
2 2

0 3 3 2 2 T
4
3 F
push adjacent edjes which is unvisited 2
2

4 F
0 3 4 STACK
visited[2]=true 1 2
1 2 Visited
Depth-First Search (DFS) ff

1 2 0 1 2
1 0 2 0 F
4
2 0 1 32 1 T
0 3 3 2 2 T
4
3 F
push adjacent edjes which is unvisited 22
4 T
0 3 STACK 1 2
visited[4]=true
4
1 2 4 Visited
Depth-First Search (DFS) ff

1 2 0 1 2
1 0 2 0 F
4
2 0 1 32 1 T
0 3 3 2 2 T
4
3 T
push adjacent edjes which is unvisited 22
4 T
0 STACK 1 2
visited[3]=true
4
1 2 4 3 Visited
3
Depth-First Search (DFS) ff

1 2 0 1 2
1 0 2 0 T
4
2 0 1 32 1 T
0 3 3 2 2 T
4
3 T
22
4 T
STACK 1 2
visited[0]=true
4
1 2 4 3 0 Visited 0 3

You might also like