Now that you have an understanding of how to actually implement a graph inside a C++, let's talk about doing things with that graph. One of the first things we're going to want to do is we're going to want to do a traversal of this graph. Traversals are something we've already talked about. You've traversed trees and talk about many different algorithms for traversing a tree. Now, we want to apply the same idea of a traversal to a graph. We're going to see it's somewhat similar but also very different. Just like a tree, a traversal is going to visit every single node exactly once. But what's different about a traversal is that we absolutely have some problems that we need to deal with when we have a graph as opposed to a tree. Let's look at some of those. So, a traversal is going to help us find interesting substructures. Inside of a tree, we know that the tree is ordered. We know that there's a root node and we can go down from the left and the right child. There's an obvious start to the tree traversal. Then, in addition to that, there's a notion of completeness. We know when a tree is finally finished because we get to say we've visited every leaf node. We've talked about how you can do any order traversal and you know exactly when you're done. A graph has a lot of weird properties that trees don't necessarily have. So, here, in a graph, we don't know a natural ordering of all these nodes, so they're not ordered. A second thing is there's no obvious start. Where would you start on this graph right here? Would you start at the middle node? Would you start at the top? Would you start at the left? All of these could have valid arguments on where to start. There's no obvious place to start. There's no notion of completeness built into a graph. That is, a graph's not necessarily going to be entirely complete, that that graph is going to be possibly looping around a whole bunch. We're going to have to maintain some data structure to ensure that we're not stepping on a node for a second time. Because remember, traversal needs to visit every single node exactly once. One of the first traversals we want to talk about is the breadth-first search traversal. This traversal is going to do the exact same thing as when we did our breadth-first search traversal in a tree. Specifically, we're going to visit all of her children nodes before we visit any grandchild. So that means, we're going to visit all over adjacent nodes before we visit any of their adjacent nodes. So, if we do that, we're going to use the same data structure we used before. We're going to maintain a queue, and this queue is going to help us organize our traversal through a graph. Let's take a look. So here, at vertex A, I'm going to go ahead and start by maintaining a data structure that's going to help us with this traversal. So, at A, we have A, B, C, D, E, F, G, and H, as all of our different nodes. A has nodes B, C, and D incident to it. B has nodes A, C and E. C has node A, B, D, E and F. D has nodes A, C, F, H. E has nodes B, C and G. F has nodes C, D, G. G has nodes E, F, H. H, finally, has nodes D, G. This is a list of different of all of the instant vertices off of every single vertex. This is something that's maintained as part of our graph data structure itself. Now we can think about BFS traversal. I'm going to start with A, but I could start anywhere. At A to my queue, and A is going to also be the first thing that's been removed from my queue. When I remove A from my queue, I can mark it as visited. So, A has been visited, and we can queue up all of its incident edges or incident nodes, B, C and D. So now, here in my queue, I can go ahead, and now that I visit A, look at my next node in the top of my queue; it's B. Mark B as being visited. Now in queue all the vertices in B that haven't been already visited. So, A already added. A is already been visited, B's already been visited. C has already been added. E has not been added, so we now add it to the end of the queue. Okay, next visit we notice is C. C we mark it as visited. Mark C as visited. Go through all of Cs incident edges. A and Bs are already been added. D is added. E is added. F gets added to the queue now, as the next node to get visited. We repeat this process. D now gets visited. D gets visited a new node on D as F is already here. H gets added. After visiting D, we visit E, and this process continues. Notice this path that we're making. This is the first node to be visited. Then, all of her children, then all of their children, and only then are we visiting H. Then, the very last node to visit is G because it's going to be a distance of three away from any single route. This process of doing breadth-first search traversal using a queue is a key idea of going through a graph and diving into those structures. So here is a finished version of this. You'll notice that I did a slightly different breath-first search traversal here based on how I did the ordering of my incident nodes. Here, I ordered the incident edges, adjacent edges or incident nodes off of A as CBD instead of BCD. Because of that, our structure looks slightly different as C gets visited first, then B, then D. In both cases, you see all of her children are visited. All of the incident nodes are visited before any of their incident nodes or the grandchildren in my root node are visited. This property is going to hold for all implementations of a breadth-first search traversal. I've provided you guys the code for this so that you can actually dive in and see this traversal really happened. I always spend just a second and talk about a few of these elements. The first thing is, is in a breadth-first search traversal, we have our input graph, and then we're going to go ahead and label these as two different types of edges. I'm going to label these as a cross edge and discovery edge so we can talk about interesting properties of this traversal. So, what we're doing here is when we have an edge that's between a node that already exists or a node that's never been seen before and a node that already exists, so when A first see B, C, and D, we're going to say that that edge when we first see that particular node is known as discovery edge. That discovers something new, we're going to make that edge bold and dark in our graph. So, we can map all of these discovery edges when we first discover that new node. If we've already discovered that node, because it's been discovered by a previous time, we'll call this a cross edge, and I'll just represent this cross edge with dots. So, what we have at the end of a BFS is we have the traversal of visits to every single node, and we have this interesting structure of how these nodes were discovered. So, part of this algorithm, I'm not just going to give you a traversal, I'm going to also give you this interesting substructure that we'll talk more about. We have this idea of the labeling of nodes as discovered in cross edges. We initially visit every node is unexplored and every edge is unexplored, we go through our graph, look in every single one. We either mark every single one is a discovery edge or a cross edge. You have access to this code through the Git repository associated with this course, so you can dive into that and see how this code actually works. In the next video, we're going to talk about what this substructure that we just created using a BFS traversal does. What it means to have a bunch of discovery edges, and what the substructure of our graph can tell us about the structure of the graph as a whole. So, I'll see you then.
