In the last video, you learned how to implement a BFS algorithm and you learned what a BFS structure looks like. Here, today, we want to do a little bit of analysis on what we did and what things we found out through running this algorithm. So, one of the first questions we can ask is whether or not the algorithm that we ran is able to detect different components in our graph. Let's look at the code. Here in the code, we can see that at lines 10 to 12, we actually did something that I didn't really explain earlier, but you can see it's clever. We looked at every single node and we marked it as unexplored initially. Here this for-loop, we'd go through every node. If it's still unexplored, we traveled through the BFS algorithm. So, if we think about a graph that has two components, we can see only when we visit one component, do we explore all three of these nodes and mark them as explored. Then here, when we have those two nodes, those nodes will be unexplored in the other component. Because only once we actually visit the nodes in the BFS algorithm, do we marked them as explored. So, because of that, we can simply cycle through. When we see another unexplored node, we have a new component. Can we count components? Absolutely. By adding line 13 here, we can count the number of components by simply adding component plus plus for every time we call the BFS algorithm. This is fantastic. So, does our implementation handle disjoint graphs? Yes. What code handles this? This is the line 10 through 13. How do we count components? We add on line 13, a component plus plus counter. Second question is, does our implementation detect a cycle? If we think about what a tree looks like, a tree is going to be a series of nodes that are everything is going to be a discovery edge, because we're always discovering something beneath us, because we're always going down. As soon as we traveled to a node on the same level, we know that we could take that cycle and completely, we follow it again and again and again to have a cycle in our graph. Because of this, we know that the existence of a cross edge, means that there's a cycle. So, this algorithm detect cycles? Absolutely, yes. How do we update our code? Well, let see exactly where we look at cross edges. So here, we see that in lines 26 to 27, this is when we see that a CROSS edge is labeled. So, if we simply say, cycle is equal to true, we're marking the fact the cycle has been detected in our graph. So, by adding a line 28 to denote that a cycle has been found, were updating our algorithm to not just do a traversal, but also count the number of components and determine whether or not there is a cycle. Therefore, does our implementation detect a cycle? Yes. How do we update the code to detect that cycle? We added the line 28 to mark that a cycle is found on our graph. What is the running time of this algorithm? Well, to do that, let's go ahead and analyze this algorithm and dive into it. Let's do this analysis. We're going to look at two different lines of code. We're going to look at line 19 and line 21. Because those are the two looping structures, and that's going to determine the number of times our code actually runs. So here, the "while" loop at line 19. The "while" at line 19 says, "while the q is not empty." So, thinking about what's going to be in the q? The q is going to contain every single node in the tree. Because when we discover it for the first time, we mark a discovery edge, and we add that to our q. So, the entirety of all of the runs of this algorithm is eventually going to run a total of n times for every single vertex in our graph. So, "while-loop" at line 19 runs any times. Let's think about line 21. So, line 21, says that "for every vertex inside of the list of adjacent vertices." Set means that could be potentially every single other node in our graph if we are a fully connected graph. So, here, we can potentially be up to n, but we also learned some property about our graph. We learned that in our graph, we know the sum of all of the degrees of all the vertexes for every vertex in our graph. But that sum, when we account for all n of them is going to be equal to two m. So, one way of looking at an algorithm is it's going to be n times in algorithm. That for every single vertex, we're going to have a series of potentially every other vertex connected to it. Or we can say in totality in the entire graph, there's exactly 2m of these vertices. So, what we can do is we can either do the analysis that says that n times n, or n squared running time, or we can say, it's n time here, and independently, we have to add up all of the possible edges here, so that's 2m. So, we can either do n times n to get an n squared running time, or more precisely, we can say it's n plus 2m, which is going to be equal to a running time of O of n plus m. So, notice that m could be in squared. So, if we have a fully connected graph, the number of edges in our graph is going to be n times n minus one over two. So, that's going to be n squared edges in our graph. So, m may be n squared, but for a graph, it's only partially connected, or a graph that is partially connected. We can see, m is going to be a number closure n. So, when m is closure n, this algorithm runs actually proportional to n because it's simply linear time based on the nodes or the edges. So, the most accurate thing we can say is n plus m, knowing the m maybe n squared. So, the best running time we can say for a BFS traversal is an n plus m running time. The last thing I wanted to talk about is talk about a few different properties of the tree we actually create when we create this tree of all the discovery edges. So, one thing we can talk about is what is the shortest path from A to H? So, looking at this tree, we notice this is a tree structure indeed. That starting with a node we started our BFS traverse line, we can simply follow discovery edges. Those discovery edges are going to lead us down a path that gets to H. Specifically, these discovery edges, we usually encode as a predecessor vertex. So, if we look at H, H is predecessor is going to be D. D's predecessor is A, A has itself as the predecessor. So, we know the shortest path from D to H is the path among discovery edges, so that's going to be A, D, H. On the other hand, we may need to talk about what the shortest path is from E to H to different vertices. Unfortunately, BFS only gives us the shortest path from our starting vertex. So, we don't know, it is not possible to know the shortest path from E to H with only a BFS algorithm. We always must look at only the starting vertex. If we need to know the shortest path, we need to start our BFS algorithm E, or explore another algorithm to give us the shortest paths, which we'll talk about in the future. Third question. How does any cross edge relate to the distance that I have between my starting vertex and my current location? If we think about this, the cross edge is always going to be an edge that's going to get us somewhere nearby where we've been. So, if the edge is going to explore a new structure, it would have been a discovery edge. Because the discovery edge is going to be the first time we see this structure. So, when we have a cross edge, we know that somebody else has explored it already. So, that means, either one of our siblings or whenever our parents have already seen this edge before. So that means a single cross edge is always going to be nearby our existing edges. In fact, by following a cross edge, we will never get one more than one further from our root. We'll never get more than one further from our start. So, knowing that we're never getting one further than our start, we know that across edges are always going to leave us in the same nearby neighborhood relative to our starting location. So, this is like key idea that allows us to know that far and cross edges and didn't do anything crazy. It's going to get us to a different part of the tree, but it's still going to be about the same depth from my starting point. The very last question is, what's the structure made by A by this series of discovery edges? I mentioned before that it's a tree, they are always seem the shape going down away from the root, and I'm going to argue that this tree is not just an ordinary tree. That this is a substructure called a spanning tree. A spanning tree is a structure that spans every single vertex in our graph. That means from every vertex here, we can travel along our discovery edges to visit any other vertex. This idea is that it spans the entire graph in a single tree. We're going to dive into what that means and do some more analysis on traversals and spanning trees in the next few lectures. I'll see you then.
