Depth-first search is a way to explore nodes in a tree or graph.
suppose you are somewhere and want to visit your friend’s home. you are new and don’t have anyone to guide you.
what you can do, start from the source and start walking until you find a blocker then you go back until one new path found.
you stop finally found your destination.
1 procedure DFS(v) is
2 label v as discovered
3 for each neighbour w of v do
4 if vertex w is not labeled as discovered then
5 recursively call DFS(w)
code explanation -
suppose v = 5 neighbours = [ 6, 7, 8 ] , discovered started = empty
line -1 , 5 is discovered
loop
iteration -1 , DFS(6)
iteration-2 start when iteration-1 as exploration from 6 is done , DFS(7)
iteration-3 start when iteration-2 as exploration from 7 is done , DFS(8)
finally neighbours are discovered. and finally exploration of 5 is done.
how to solve the problem using the DFS approach
procedure DFS(G, v) is
label v as discoveredadd logic when first time node is discoveredfor each neighbour w of v do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)add logic when node is completed discovered or all its children is finished
example — calculate total coins after visiting all nodes in the binary tree
procedure Ask(v) is
coins = v ;
// now ask from both its children
if left child exist
coins+ = Ask(leftChild)
if right child exist
coins+ = Ask(RightChild)
// once received answer from both of children
return coins
end
the output from parent requires to finish all its children then, DFS can be a possibility there.
for this, you need to write a reoccurrence relation.
simple reoccurrence may be
the output from parent = left subtree + right subtree