Depth First Traversal for a Graph | GeeksforGeeks
Depth First Traversal for a Graph | GeeksforGeeks
Explanation for the article: http://www.geeksforgeeks.org/depth-fi…
This video is contributed by Illuminati.
Content
0.65 -> Hello friends!
1.979 -> In this video we are going to see depth first
traversal technique in graphs.
8.69 -> The idea in depth first search is pretty simple.
13.2 -> Given a graph we have to go forward depth
wise while there is any such possibility,
19.66 -> if not then we have to backtrack.
23.06 -> The term Backtrack here means
that we have achieve a dead end,
28.14 -> so move back and choose another path.
33.22 -> Lets learn depth first search with the help
of an example.
36.43 -> Consider the graph as shown.
38.33 -> We have 6 nodes labeled A to F.
Now we see that these nodes are connected
48.4 -> and traversing them can get us stuck in an
infinite loop.
53.2 -> So how can we fix it ?
The solution to this could be to have a boolean
59.12 -> visited flag for each node.
62.73 -> This flag will be true if we have visited
a particular node
66.24 -> else it would be false.
70.19 -> Since we have more than 1 node we will use
an array of such flags
75.06 -> and will call it a boolean visited array.
80.35 -> Lets quickly see to the ingredients required
to get our depth first algorithm running.
87.18 -> We will require a graph, a stack data structure,
and an output array.
94.78 -> Initially our stack is empty and all the nodes
are unvisited.
100.31 -> Note the color representation of visited and
unvisited nodes
107.07 -> and also for better visualization of
the algorithm we have shown the stack in a
114.04 -> vertical manner.
116.08 -> Now lets start our algorithm with this starting
vertex labeled A,
122.04 -> We push it into our stack,
print it as an output and mark it visited.
129.2 -> Next we look at the adjacent unvisited nodes
of A.
134.599 -> B and C holds the criteria,
we may pick any of them.
139.9 -> We will go and choose B.
Push node B into stack,
146.659 -> print it and also visit it.
149.79 -> Now we look at the unvisited adjacent nodes
of B.
154.499 -> Node D and node E are the required neighbors.
159.209 -> We choose D.
Push it onto our stack,
163.98 -> print it and also mark it as visited.
168.159 -> Now we look at the unvisited adjacent nodes
of D.
173.42 -> Vertex E and F are the nodes that satisfy
our given criteria.
179.709 -> We choose vertex E.
182.279 -> Push it onto stack,
print it and also visit it.
187.739 -> Now lets look at the adjacent unvisited nodes
of E.
192.659 -> We find node C and F as the one that holds
the given criteria.
199.859 -> We Push F onto stack,
print it and also visit it.
204.79 -> Now we see unvisited adjacent nodes of F.
209.719 -> We find that all the adjacent nodes are visited
and hence there is no way.
216.319 -> So we backtrack.
217.819 -> We pop node F from top of the stack.
222.14 -> Now we have node E as top of the stack.
225.79 -> We see for the unvisited adjacent nodes of
E.
231.169 -> We find one node which is C.
233.029 -> We push it onto our stack,
print it and mark it as visited.
240.48 -> Now we look at the adjacent unvisited node
of C,
243.939 -> there are no such nodes.
246.79 -> So we pop C from the stack.
249.579 -> We now have E as top of the stack.
253.389 -> There are no unvisited adjacent nodes of E,
so again we pop E from the stack.
260.739 -> Now comes the D and again we find that there
are no unvisited neighbors of node D.We therefore
270.19 -> pop D from the stack.
273.52 -> B is the new top of the stack.
275.419 -> We see that B do not have any unvisited neighbor.
280.04 -> We therefore pop B from the stack.
284.33 -> Now we are left with A.
286.31 -> The two neighbors of A are visited and therefore
we have no go
291.22 -> and will pop A from the stack.
296.06 -> We now see that our stack is empty.
299.039 -> This will signal our algorithm to stop.
303.56 -> We now take a pause and see that how all nodes
are visited and also printed.
310.68 -> We also see that the traversing is done in
a depth wise fashion.
317.43 -> Now think of how to implement it !
320.789 -> A hint could be that we are using stack.
325.05 -> Since we are using stack we can implement
it recursively or we can do iteratively using
332.15 -> a stack data structure.
335.379 -> This is an example code which is recursive
and same as that given on geeksforgeeks.
343.33 -> You can go through this code or implement
your own version for the same.
349.25 -> Lets quickly look at the complexity of the
code.
352.71 -> Depth-first search visits every vertex in
the graph and checks every edge for each node.
361.199 -> Therefore time complexity for depth first
search is O(V + E).
368.62 -> Here V are the vertex or nodes and E are edges.
374.319 -> We'll wrap this tutorial now.
377.689 -> For any queries or doubts please comment below.
381.05 -> Thanks for watching!
Source: https://www.youtube.com/watch?v=Y40bRyPQQr0