Depth First Search (DFS) Graph Traversal in Data Structures

Summary

This video introduces Depth First Search (DFS), a method for graph traversal. It contrasts DFS with Breadth First Search (BFS), explaining how DFS explores nodes deeply before backtracking. The speaker outlines the procedure, starting from a node and using a stack to keep track of visited nodes. As the traversal progresses, the video illustrates how to add connected vertices to the stack and visit them sequentially. The speaker emphasizes the simplicity of DFS while hinting at a forthcoming detailed coding tutorial in C. Overall, the video provides a clear and engaging explanation of DFS.

Takeaways

• 😀 Depth First Search (DFS) is a method for traversing graphs, just like Breadth First Search (BFS).
• 🌐 In DFS, you start at a node and explore its connected vertices, going as deep as possible before backtracking.
• 🔄 If you reach a dead end while traversing, you backtrack to the last visited node to explore other paths.
• 📊 DFS and BFS are two major graph traversal techniques, each with different approaches.
• 📚 The procedure for DFS involves using a stack to keep track of the nodes to visit.
• ✅ When implementing DFS, nodes are marked as visited to avoid revisiting them.
• 🗂️ The stack in DFS is crucial, as it follows the Last In, First Out (LIFO) principle.
• 💻 The programming implementation of DFS can be done in languages like C, utilizing function call stacks.
• 🔍 The traversal order in DFS can vary based on the order nodes are pushed onto the stack.
• 📝 Pseudocode for DFS is provided to assist with coding the algorithm in the next video.

Q & A

What is Depth First Search (DFS) and how is it different from Breadth First Search (BFS)?

Depth First Search (DFS) is a graph traversal method where you start at a node and explore as deeply as possible along each branch before backtracking. In contrast, Breadth First Search (BFS) explores all neighboring nodes at the current level before moving on to nodes at the next level.

How does DFS explore a graph?

In DFS, the exploration starts from a node, and the algorithm moves to its connected vertices, going deeper into the graph. When a dead end is reached, it backtracks and explores other suspended paths. This continues until all nodes are visited.

What is the role of a stack in DFS?

A stack is used in DFS to manage the nodes to be visited. It follows the Last In, First Out (LIFO) principle, where the last node added to the stack is the first one to be visited. This structure helps DFS explore deeper nodes before backtracking.

Can DFS be implemented without a stack?

While DFS can be conceptually described without a stack, in computer programming, a stack is essential to manage the traversal process efficiently. The stack ensures that DFS explores nodes correctly and backtracks when necessary.

What happens when DFS encounters a dead end?

When DFS encounters a dead end, meaning a node has no unvisited neighbors, it backtracks by popping the last node from the stack and continues exploring from there.

How does DFS work programmatically?

Programmatically, DFS begins by pushing the starting node onto a stack. Then, nodes are popped from the stack, visited, and any unvisited connected nodes are pushed onto the stack. This process continues until all nodes are visited.

Why does the speaker mention that DFS is simple in layman terms?

The speaker mentions that DFS is simple in layman terms to emphasize the straightforward nature of the algorithm. It involves going deep into a graph and backtracking when necessary, which is easy to grasp without technical details.

What is the key difference between how DFS is described informally and how it is implemented in programming?

Informally, DFS is described as a process of exploring a graph deeply before backtracking. In programming, DFS is implemented using a stack to track nodes to be visited and manage backtracking efficiently.

What does the pseudocode provided in the video illustrate?

The pseudocode provided in the video illustrates the step-by-step procedure for implementing DFS in a programming language, showing how nodes are added to the stack, popped from it, and visited until all nodes are explored.

How does DFS compare to BFS in terms of traversal order?

DFS explores a graph by going deep along one branch before backtracking, whereas BFS explores nodes level by level, visiting all neighboring nodes before moving deeper. DFS can lead to a different traversal order compared to BFS, depending on the graph structure and node connections.

Outlines

00:00

🧩 Understanding Depth First Search (DFS)

In this part, the speaker introduces Depth First Search (DFS), explaining it as a method for traversing graphs, akin to Breadth First Search (BFS). DFS begins with a starting node, exploring its connected vertices deeply before backtracking. The speaker illustrates the procedure of DFS, noting that it involves placing the starting vertex on a stack and visiting connected nodes. When a dead end is reached, the algorithm backtracks to previously visited nodes, continuing until all nodes are traversed. A clear comparison is made between DFS and BFS, emphasizing their different approaches to graph traversal. The speaker outlines the algorithm's steps and mentions that pseudocode for DFS will be provided in future content, preparing viewers for coding in C language.

Keywords

💡Depth First Search (DFS)

Depth First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at a given node and explores as far down a branch as possible before backtracking. The video illustrates DFS by explaining that it can go deep into a graph until a dead end is reached, at which point it backtracks to explore other unvisited paths.

💡Breadth First Search (BFS)

Breadth First Search (BFS) is another graph traversal method, which explores all the neighbor nodes at the present depth before moving on to nodes at the next depth level. In the video, BFS is compared with DFS to highlight their differences, with BFS visiting all connected nodes of a starting point before going deeper, making it useful for finding the shortest path in unweighted graphs.

💡Graph

A graph is a collection of nodes (or vertices) connected by edges. In the context of the video, graphs are the primary data structure used for implementing DFS and BFS algorithms. The narrator illustrates graph traversal by visualizing connections between nodes, which serve as the basis for both DFS and BFS.

💡Node

A node is an individual element within a graph that can represent a data point or object. In the video, the narrator refers to nodes when explaining how DFS and BFS traverse through the graph, emphasizing that traversal begins at a specific node and explores its connections.

💡Stack

A stack is a data structure that follows the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. The video discusses how a stack is essential for implementing DFS programmatically, allowing the algorithm to backtrack effectively when reaching dead ends in the graph.

💡Visited List

A visited list is an array or data structure used to keep track of which nodes have been explored during the traversal process. In the video, the narrator mentions creating a visited list to ensure that nodes are not revisited, thus preventing infinite loops and improving the efficiency of the traversal.

💡Backtracking

Backtracking refers to the process of returning to a previous node after reaching a dead end in a graph traversal. In the context of the video, backtracking is a critical aspect of DFS, allowing the algorithm to explore all possible paths in the graph by returning to earlier nodes when no further moves are possible.

💡Dead End

A dead end in graph traversal is a situation where a node has no unvisited connected vertices. The video explains that when DFS reaches a dead end, it must backtrack to explore other paths. This concept is essential for understanding how DFS efficiently covers all nodes in a graph.

💡Traversal

Traversal refers to the process of visiting all the nodes in a graph or tree structure systematically. The video focuses on how both DFS and BFS serve as methods for traversal, each with distinct strategies for exploring nodes, thereby highlighting the importance of understanding different traversal techniques in computer science.

💡Pseudocode

Pseudocode is a simplified, informal way of describing an algorithm using structured but human-readable notation. The video concludes by mentioning that pseudocode for DFS will be provided in the next installment, indicating that it will help viewers translate the DFS concept into actual programming code more easily.

Highlights

Depth First Search (DFS) is a method of traversing a graph, akin to Breadth First Search (BFS).

DFS involves starting at a node and exploring its connected vertices deeply.

When a dead end is reached in DFS, the algorithm backtracks to explore other paths.

DFS and BFS are the two primary ways to perform graph traversal.

DFS uses a stack to manage the nodes that need to be visited.

The traversal process in DFS involves visiting nodes and marking them as explored.

DFS is particularly useful in scenarios requiring exploration of all possible paths.

The traversal order in DFS can vary based on the graph's structure and the exploration order.

DFS can be implemented programmatically, taking advantage of the call stack.

An initial node is placed on top of a stack to begin the DFS process.

After visiting a node, its unvisited neighbors are pushed onto the stack.

Pseudocode for DFS outlines the recursive nature of the algorithm.

The algorithm backtracks through the stack when no unvisited neighbors remain.

DFS is effective for searching paths in complex graphs, including trees.

The next session will cover coding DFS in the C programming language.

Understanding DFS enhances problem-solving skills in graph-related challenges.

Transcripts

Today we'll see about Depth First Search.

In previous video we saw about breadth first search.

Firstly I'll talk about what is Depth First Search.

So Depth First Search is not a big thing.

It is just a way to traverse a graph.

As we saw that Breadth First Search is a way to traverse graph,

in the same way this is also a way to traverse graph, nothing else.

So when we do graph traversal,

we have Depth First Search and Breadth First Search,

which are the two major ways to do it,

to do traversal.

So here we have already seen BFS.

Now we'll see DFS.

So these things you already know, I know that.

So in DFS what we do ? In DFS we start with,

a node and explore its connected vertices.

And try to go deep in it.

So we go deep and deep and deep,

and finally a time comes when we,

get a node which is already explored.

So we come back and,

the traversals which we have suspended,

we do them again.

Now many people will think what am I talking about.

But, let me tell you here,

I'll compare DFS and BFS.

Firstly I'll compare this with BFS.

BFS. Suppose this is a graph.

I am making some nodes.

It is not necessary to mark these nodes which I am making,

or to write something in it.

But let us assume that this a graph.

So if I am doing BFS, than what I'll do is,

if I start with this node.

So firstly I'll visit its all collected vertex, which means

I'll visit this, and this, and this.

But if I am doing DFS than what I'll do is,

I'll start from here and than I'll go there, there and there.

So I came to the dead end, now I'll go back again and again.

And I'll go here, and here, and here and likewise whole graph will be traverse.

I know at this point, some people must get this confusing.

Lets go further, and I guarantee you will get this very clearly.

So lets understand the procedure first.

I'll directly come to the point, as it's not a big thing.

It is a way to do traverse.

I'll talk to the point, let me directly come to the point.

Let's see what we have to do.

So we have to start by putting any one of the graph's vertices

on top of a stack.

Before we talk about stack and programmatic procedure,

let me tell you a very simple procedure

that how DFS works.

Suppose I start here from 0.

I'll make a visited array here, so I am writing visited.

So in this visited list or say array

I'll start with a node, suppose I am starting with 0.

So I am starting from 0, so I am writing here 0.

Starting from 0, I'll go towards 1.

And I'll write 1.

Than from 1 I'll go towards 2 and I'll write 2.

From 2 I can go to 3 or 4, its up to me. But I'll go to 3.

So I'll go towards 3.

From 3 where I can go ? I can go towards 4. So I'll go to 4.

From 4 I can go towards 5, so I'll go to 5.

But when I'll go to 5, I'll realise that I can't go ahead.

So I'll go back one step in the same direction from where I came.

I'll go back in that same direction.

And I'll come back to 4.

On 4 I realise that I can go on 6, so I'll go to 6.

Like this I'll go to 6.

But when I am on 6, I'll realise that I can't go ahead.

As this is a type of dead end.

So I'll go back in the same direction from which I came.

Not like you'll go to 0 from 6.

So I will go back in same direction to 4.

In the same direction I came to 4.

When I came to 4 I realised that I can go to 2.

And when I came to 2,

than I realised that I can't go anywhere, its a dead end.

So I'll come back again and again from the path.

And I"ll come back here and DFS will be completed.

As we have visited all the nodes.

So this is our layman terms procedure of how DFS works.

But when you give command to a computer,

if you want computer to do DFS than this will not be the approch.

Than what will be the approch there ?

If you want that computer do DFS than there you will use stack.

And the good thing is that, when in computer

we write code in C language for DFS,

than by default we get stack there, and its really amazing.

And you must be also enjoying this,

that wow we already get stack in DFS.

And how all this happens that I'll tell you.

Functions already uses stack, this I have already told you.

By using that only we will write the procedure of DFS.

But now lets understand the programmatic procedure of DFS.

So the 1st point is,

start by putting any one of the graph's vertices on top of a stack.

Procedure says that take a stack.

And what is a stack ? It is a bucket.

And start keeping things in the bucket.

The thing which is kept at last, will come out first.

After this, take the top item of stack and add it to visited list.

Firstly we have to put a node, so I kept 0.

So I kept 0.

I can put any node say 1 or 2.

Now it says that take out what you kept inside.

So lets take out what we kept.

And we took out 0.

So 0 came out of stack now.

We took 0 out and,

put all the vertices in the stack which are connected to 0.

In any order I'll put 1, 2 and 3.

Now 1, 2, 3 are inside our stack.

I can also put like 3, 2, 1 .

I can also put like this,

that at the end of stack its 3 then 2 and then 1.

In any order you can keep it, there is no hard and fast rule here.

But If you kept it once,

than you'll first remove the one which you kept at last.

So you'll remove 1 first.

And what will come in visited, so first 0 came.

Than which ever we are removing from stack, will come to visited.

Once you removed 1, it came to visited.

Now you removed 1, so you have to do this procedure again.

That you have to remove the top item of the stack

and add it to the visited list.

After that all the items which are connect to this,

and not visited, that you'll keep in stack.

So if we talk about 1,

0 and 2 are connected to 1.

So what we'll do here, as 0 is already in the visited list

but 2 is not in visited list, so we'll put it in the stack.

As 2 is already in the stack, we will pop it out.

And after that we will visit 2.

We will do same thing with 2.

Which are the connected vertices with 2,

for that we will use this same procedure.

And after that, If I

put the 1st step on the graph which you can see on right hand side.

So what I did is, I started with 0.

I kept 0 in stack.

As you can see 0 came in the stack.

Now I'll start putting any one of the graph vertices.

And after that my 2nd step is,

take the top item of the stack and add it to the visited list.

As you can see, 0 is also visited now.

This is done, now I'll put items in stack which are connected to 0.

And that are 1, 2 and 3.

As you see 1, 2 and 3 will go in the stack in any order.

Once I kept 1, 2 and 3 in stack in any order,

I'll pop out the top most element.

I'll pop out the top most element and put it in visited.

And I'll keep nodes in the stack, which are connected to it.

Also it must not be visited, as 0 is visited I'll not put it.

I'll keep 2 in stack.

So again I'll put 2 in the stack.

So after keeping it inside I'll pop out 2.

So this and this are visited.

2 will also be visited as I popped it out.

But which all should come in stack ?

0, 1, 3 and 4 .

As 0 and 1 are visited, 3 and 4 will come.

So I'll keep 3 and 4.

I'll pop out 4 from stack and put it to visited.

So I kept 4 in visited.

4 is visited now. What I'll keep in stack now ?

I should put 3, 5 and 6 as they are not yet visited.

So I'll keep 3, 5 and 6.

Now I'll pop out 6.

And I'll write 6 here, it is also visited now.

Is there any element connected to 6 but unvisited ? No.

There is no node connected to 6 which is unvisited.

So thats why what I'll do is,

I'll pop out the next one, which is 5.

Which one will I pop out ? The next one which is 5.

And I'll put it in the visited list.

And there is no node connect to it,

which is unvisited.

That's why now I'll pop out 3.

I'll put 3 in the visited list.

And there is no node connected to 3 which is unvisited.

Similarly, 3 and 3 is done.

As well as 2 is also done.

So I'll remove 2 also.

Finally our stack is empty.

So as you can see that,

our DFS traversal has been came.

Can this DFS traversal be done with the way which I showed you first ?

Yes.

So you start with 0.

Then go to 1 and then go towards 2.

From 2 go to 4.

From 4 you go to 6.

At 6 you got dead end, so come back.

So from 4 you have gone to 6,

and came back to 4.

After this you can go to 5.

From 5 you have to come back, and than you'll go to 3.

So a valid DFS traversal has been made.

I hope it is understood as its a really simple thing.

And to write this programmatically with stack makes it more easy.

On you screen,

It is Pseudocode of DFS which you can use,

if you want to code DFS in C language.

Or I am going to explain this in the next video.

We will see code for DFS in C language in detail.

That how we can code the DFS.

So for now thats it for this video.

Thank you so much for watching this video.

And I will see you next time.