[MUSIC] In the previous videos, we've talked about a breadth-first search traversal. And now, we want to dive in and actually do a different type of traversal, a depth-first traversal. In a breadth-first traversal, we identified all of our children nodes or nearby incident nodes first, and then we visited their children, or their incident nodes. In a depth-first traversal, we want to go very, very deep very quickly. In a BFS, we used the queue structure to maintain our data structure. Here, we're going to maintain our data structure using a stack structure. And to make this really, really easy, we already know recall stack frames when we call C++ code. So we won't even worry about the structure itself, instead, we're just going to visit every single node as we see them, as we move through our recursion. So this algorithm's going to be really, really quick to understand. So let's go ahead and start with node A and go through this just like we did before. Start with node A, I'm going to just start drawing a circle, as I want to visit every single node around node A. So I'm going to start here, and as soon as I cross an edge, have I seen this edge before? Have I visited D? No, so this is discovery edge, and now I've moved from A to D. So now at D, let's do the exact same thing. Let's start at D, let's start drawing my circle and I found a new edge, it's discovering something new. So let's keep going down, let's keep doing our depth-first traversal. We move to H, and then starting the circle from that same spot, and H goes to G, also we have a newly discovered vertex. Here at G, we're going to do the same thing and we're going to go ahead and start, and we got to J, do a discovery here on J. And now at J, the exact same thing. We're going to look at J, start looking at all of the edges we might visit, and we find that we have an edge from J to K. We've discovered a new node, and finally, at K, we can repeat this process for one last time, and see at K, we start here. And here we have an edge that no longer discovers something new, at this edge, from K to A, we already know about A. A's been discovered, so we're not going to mark this as a newly discovered edge. Instead, we want to mark the K edge as a back edge, it gets us somewhere further back in our process. So just like a cross edge inside of a BFS, a back edge is going to be an edge that's not a discovery edge in a DFS. So I'm going to label it with dots just as I did with the cross edges. So here adding dots, we now know that's a back edge, continuing on K, we find that K to E is a discovery edge, we discovered something new about E. And now at E, let's continue on and say, okay E, have you found, this is now a back edge because we've already seen the node D. So we don't want to do this as a new discovery edge. We've completely finished in E, visited all in edges. We go back to K, we completely finish, I is completely finished. And now, here we're back at G and in G we need to continue our circle. We find new edge here, it's already been labelled. So G, now we see a new edge C, C is a discovery edge, C has a back edge to D, it's already been discovered and it's coverage to B. Finally, F is discovered when we visit G and has a back edge to D. So notice we did this entire algorithm without ever thinking about a queue or stack data structure. We have an implicit stack going on based on the calling stack in our recursive algorithm. But here, we're able to build something up entirely by a really, really simple code. So you notice this has the same routes as a BFS algorithm. You can see we did the same process, we just had different ordering and visiting nodes. Let's see how this code differs. Here is a BFS code, all I need to do is remove everything that has to do with a queue, and I'm going to have a perfectly great call stack. So instead of going through and looking at element related to a queue, I remove all the queue lines, change the cross edges to discovery edges. And make sure that instead of enqueuing, I'm going to call a new version of my depth-first search algorithm with a graph on my new node. By making these changes all over, I can modify this code from BFS algorithm to DFS algorithm by simply removing a few lines of code related to the queue, calling DFS instead and labeling it as a back edge instead. So we now have the code that allows us to do a DFS traversal in the exact same ways as BFS traversal, but we visit our deep nodes extremely early in this process. So in the previous time, we did analysis of the actual code to understand how it worked. Here, I want to do a different form of analysis to see what the running time of BFS algorithm and DFS algorithms are. And you'll see this analysis works for both algorithms, and it's another way to compute the exact same running time. We know the only operations that we're going to perform on a data structure like this is going to be operations that involve labeling our nodes. So every time we do any operation, we're always going to do a labeling. So let's count how many labels that take place when we label all of our vertices and we query them to find out when the next one is. So when we label a vertex, we know that every single vertex we initially have undiscovered, and then we label as discovered at some point in time. So we do a total of 2 times n labeling, or o of n labels. We label every edge twice as well, so we do 2 times m labels in the edges or o of m labels. There are originally a undiscovered edge and then there're either a discovered edge or a back edge. Now when we query our data structure, we know that we're going around every single node. So we know that we're going through every single vertex exactly once, so we visit every vertex exactly one time, the Sullivan. When we look at a single vertex, we're going to visit every single one of those vertices' edges. So we know that potentially a vertex can have every single edge connected to it. But we have a mathematics to say is actual the degree of v for every single time. So we have degree of v for every single one of our vertices, we know we are going to visit every single one of our vertexes. So we know that this is the sum of all of degrees of v, sum of all degrees of v is equal to 2m which equal to o(m). So what we have is o(n) plus o(m) plus o(m) plus o(m), so total running time is o(n + m). This exact the same running time as doing a BFS traversal. So we can see by doing two different analysis, we have two different forms of doing a BFS and DFS traversal. Those two different forms of traversal are going to both run in n plus m time. And you'll notice that's the optimal running time for running this. Because we have to visit every single node exactly once and we have to visit every single edge exactly once. So there's no way we can do faster n plus m time, so both the BFS and DFS traversal are optimal traversal running optimal running times for a graph. And they give us some really interesting bits about the substructure, like this spanning tree we talked about in BFS. Next, we want to dive into actually understanding how we can do even more interesting data structures. And figure out how we can find out structures like spanning trees and cycles within our graph. So we'll dive into those thing in the next video, we'll talk more about spanning trees then. See you there.
