Hello, and welcome. My name is William and today we're moving on to talking about the depth first search algorithm, which plays a central role in several graph theory algorithms. So what is a depth first search? depth first search is a core algorithm in graph theory that allows you to explore nodes and edges of a graph. So it's a form of traversal algorithm. The nice thing about a depth first search is that it's really easy to code.

And it runs in a time complexity of big O of v plus e, that is vertices plus edges, which is directly proportional to the size of your graph. By itself. A depth first search isn't all that useful, but when argumented to perform other tasks, such as count connected components, determine connectivity between nodes or find bridges and articulation. points, the depth first search algorithm really shines. So let's look at an example. As the name suggests, a depth for search plunges depth first into a graph, without regard for which edge it selects next, until it cannot go any further at which point it backtracks and continues its exploration.

So a depth first search has to start on a node. And I'm going to start our depth first search on node zero. And now we arbitrarily pick a node to go to sum from node zero, we're going to go and no nine. Then from no nine, we only have one choice, which is to go to node eight. at node eight arbitrarily pick an edge. So we're going to go outwards to node seven, no seven, we have plenty of edges to choose from.

So let's go to node 10, node 10 to note 11 and 11 to seven So we don't want to revisit already visited nodes or nodes that are currently being visited. So we have to backtrack to indicate backtracking, I'm going to label edges and nodes as gray. So backtrack all the way back to node seven. So we're not finished exploring node seven, because there are still edges to be picked. So I'm going to go to node three, and node three, me and go node two. node two is a dead end.

So we backtrack, then go to node four, node four is also dead. And so backtrack from node four, back to node three. Then pick node threes last edge to go node five, five to six, and six, the seven can't go to seven because we're visiting seven currently. So backtrack all the way back to note eight. From note eight. We still need to visit its last edge which goes to node one, node one back to node zero, we can't go to node zero, because we're currently exploring it, then backtrack all the way to zero, which completes our depth first search traversal of this graph.

So this was one particular depth for search traversal. But as you saw, it could have gone a lot of different ways. So now let's look at some pseudocode. For this depth first search to get a deeper understanding of how it works. The first thing we need to do is initialize these three variables, which are n the number of nodes in our graph, g the adjacency list, representing the graph and visited a Boolean array containing true or false at index. Either depending on whether or not node II has been visited in the beginning this array should have all false values because we have not visited any nodes in the graph.

Once that is set up at the bottom I define our starting node to be node zero and then call the depth first search method to do the exploration. The depth first search itself has one argument. The current node we are at which I have conveniently named at this method is recursive. So I check the base case, which is whether we have already visited this node If so, we have no business here and can return otherwise, let's visit this node by marking it as true and exploring all of its neighbors to explore all the neighbors of the node. Reach into the adjacency list and pull out all the neighbors of this node and explore them depth first by looping over each And recursively calling the depth first search method. And that's all a depth first search really is.

In a nutshell, let's look at another simple use case. For a depth first search, I want to discuss finding connected components in a graph. First, let's understand what we mean by connected component. Sometimes the graph is split into multiple disjoint components, and it's useful to be able to identify and count these components. One way to identify these components might be to color them so we can tell them apart. But what does coloring nodes really mean to a computer coloring nodes is equivalent to labeling each node in a component with the same ID value.

For example, every node in the purple component gets an ID of one and every node in the green component gets an ID of three. We can use a depth first search to To identify components this way, first make sure all the nodes are labeled from zero to n non inclusive, where n is the number of nodes, the basic algorithm is to start a depth first search at every node, except if that node has already been visited, and mark all reachable nodes as being part of the same component using the same ID. So if we start at node zero, then we do a depth first search here and then every node in this component gets an ID of zero. So we go to eight, giving it an ID of zero, 14 gets zero 13 also label it with a zero then backtrack like you do a depth first search, then explore note for given an idea of zero, and then finish exploring that component and then move on to the next node in order so go to node one next than node one.

So depth for search there. So goodnotes, five, label it with a one, five goes to 17, label it with a one, backtrack, go to 16, also label it with a one, we're finished exploring this component, then we would go on to node two, wherever node two is, then explore that component, then node three, explore node three component unless node three has already been visited, and so on. So we do this for every component. And eventually, we get to label all the components. And we use a depth first search to do that. Awesome.

So that's how we find connected components using a depth first search. Now let's look at some pseudocode. For how we do this. First, we'll need a couple of things. We'll need everything from the previous code we looked at so and the number of nodes in our graph, G, our adjacency list and our visited array, but additionally, we'll also need a variable called count that tracks the number of connected components And components and integer array that holds the integer value of which component a node belongs to. Inside the find components method, we loop over every node and check if the current node has been visited or not and then execute some logic.

This depth first search variant differs slightly from the previous in that we execute a depth first search for every unvisited note, when we actually do the depth first search, we visit nodes and mark them as visited. So we never revisit the same node more than once we either skip over a node because it's been visited in this for loop or start a depth for a search there. If we start a new depth for search, we increment the count variable and keep track of how many depth for searches we have done. Inside the depth first search method itself. The two things we do are marked the current note as visited Set the current node to be part of the component equal to the value of count, and then simply iterate over every neighboring node that has not yet been visited, and call the depth for search method to explore them as well.

Back inside the find components method, simply return the number of components and the components array that contains the information about which component each node belongs to. So we've covered two of the things you can use the depth for search for doing a simple traversal and determining connected components, but we can augment a depth first search to do so much more, such as computer graphs, minimum spanning tree, detect and find cycles in the graph. Check if a graph is bipartite find strongly connected components topologically sort your graph, find bridges and articulation points find augmenting paths and a flow network generate mazes and many many more applications. So definitely Research is super versatile and can be extended to do a whole ton of things. Thank you for watching. Next video I should be talking about the breadth first search algorithm.

Stay tuned and subscribe for more mathematics and computer science videos. Cheers.