Scribd
Upload
376 views3 pages

Depth-First Search Algorithm ?

The depth-first search (DFS) algorithm traverses a graph by exploring as far as possible along each branch before backtracking. It works as follows: 1) Select an unvisited node as the starting point and mark it as visited. 2) Visit any unvisited neighbors and recursively apply DFS to them, marking them visited. 3) Once all neighbors are visited, backtrack to the most recently visited node and continue exploring from there if possible. Otherwise backtrack further.

Uploaded by

G.pradeep Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
376 views3 pages

Depth-First Search Algorithm ?

The depth-first search (DFS) algorithm traverses a graph by exploring as far as possible along each branch before backtracking. It works as follows: 1) Select an unvisited node as the starting point and mark it as visited. 2) Visit any unvisited neighbors and recursively apply DFS to them, marking them visited. 3) Once all neighbors are visited, backtrack to the most recently visited node and continue exploring from there if possible. Otherwise backtrack further.

Uploaded by

G.pradeep Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 3

1.

GIVE A SUITABLE EXAMPLE AND EXPLAIN THE

DEPTH-FIRST SEARCH ALGORITHM ?

Graph searching:
The systematic follow up of the edges of the graph in
some specific order to visit the vertices of the graph is called
graph searching.

There are two searching algorithms:-

 Depth First Search ( DFS)


 Breadth First search (BFS)

DFS Follows the following rules:-


 select an unvisited node ‘v’, visit it, and treat as a
current node.
 Find an unvisited neighbour of current node,visit it,
and make it the new current node.If there are more
than one unvisited neighbours then resolve the tie
by following the alphabetical order.
 If the current node has no unvisited neighbours,
backtrack to its parent, and make it new current
node;
 Repeat the step 2 & 3 until no more nodes can be
visited.
 Repeat from step 1 for the remaining nodes.

Basic terminologies in depth first traversal:-


Let us define some terminologies in DFS formally
Depth first forest:-
The depth first forest is a collection of trees in which the
traversal’s starting vertex serves as the root of the first tree in
such a forest. Whenever a new unvisited vertex is visited the it
is attached as a child to the vertex from which it is being
reached.

Tree edge:-
In a graph ‘G’ containing an edge (u,v) if a new
unvisited vertex ‘v’ is reachd from the current vertex the the
edge (u,v) is called tree edge.

Back edge:-
In a graph ‘G’ if previously visited ‘v’ is reached from the
current vertex ‘u’ then edge (u,v) is called back edge.

ALGORITHM:-

//Problem Description: This algorithm is for traversing the


//graph in depth first manner
//Input: The graph ‘G’ which is collection of vertices(v)
//and edges(E) from which vertex ‘v’ is selected as a starting
//vertex
//Output: The sequence of depth first traversal
//Initially the vertex ‘v’ in visited array is marked 1, that
//means currently we are visiting vertex ‘v’.

visit[v]=1
for (each vertex adjacent from v) do
{
if (visit[u]=0)
DFS(u) // recursive call from next selected vertex ‘u’
}
ANALYSIS:-
Every node is visited once hence the time complexity of
depth first search is O(V + E) if the graph is created using
adjacency list and it is O(V)2 if the graph is created using the
adjacent matrix.

For example

You might also like