Okay. So, while I'm assuming your homework problem that's Dijkstra's shortest path algorithm, I'm gonna show you some processing of handling the is connected problem, they're related. To some extent, you could in fact use shortest path algorithm and it's in one form to find whether a graft is connected or not. But the simpler one should give you ideas about how to do the Dijkstra's algorithm. And this goes back to my own work back in 1968 when I was a research graduate student research assistant at the, Stanford Linear Accelerator Center, and I was being asked to use this very new programming language called PL1 which is, more or less, out of favor now but still available. And the interesting thing about PL1 was, it was an attempt to get a universal programming language. PL1 was supposed to be IBM's ability to having to do away with special purpose languages, and IBM was finding that it wanted to be a hardware company, not a software company. It wanted to sell big machines which generally filled up lots of space and cost lots of money. And software was an irritating expense, and so the fact that they had to provide machine language compilers, macro pre processors, COBOL compilers, Fortran compilers, sometimes ALGOL compilers. That was just a lot of different software they were supporting, and they just felt, well, why can't we get a universal language? And that will simplify our task. And they tried. And the way they tried was unfortunately what I call the kitchen sink approach. They took everything they had in all these different languages, threw them all together, and it was a lot of redundancy in this language. You could do things in a COBOL manner, or a FORTRAN manner There wasn't an obvious P01 manner to do things. And that's in a way why P01 didn't survive the object revolution. Object orientation allows you to have a much simpler idea of what occurred in languages, in our case, C and then, expand it by letting the programmer add classes. Whenever they need it, yet a new domain, a new set of which it's to work with. Now, the algorithm I'm gonna describe goes back to work that I did and was documented in some reports at SLAC. But later it was generalized in a very important way by Tarjan and Hopcroft. And it's a foundational algorithm called breadth first search. And you can certainly read about that. So this is also a vital algorithm that you should be familiar with. Breadth first search, and you can find it in the Wikipedia. And what we're going to do in trying to find out whether a graph is connected is we're gonna start arbitrarily with some node. And since everything in C starts at 0, and we'll probably use a labeling system that says we'll have node 0 up to node m- 1, or up to node size -1. We will assume that no 0, think of our map before San Fransisco if I'm sitting in San Fransisco I've reached San Fransisco. So San Fransisco is automatically connected to San Fransisco, so we're going to have this. Initial set, and in that initial set, we'll put the node 0. Then, we will look from San Francisco and see where are the adjacent cities we can reach? And this will be what I will call a closed set, and then what I'm going to call an open set I'm going to put nodes reachable from San Francisco. So if I could reach node 3 and node 7 those will be nodes in the open set. Now, what if there was no way out of San Francisco? Maybe there's been a huge earthquake, and all roads have been busted? What does that mean? It means the graph is disconnected. I can't get from San Francisco to San Diego. I could stop. So if I have a closed set automatically with a starting node, and if there's no edges out, well, then the algorithm would stop and report that the graph is not connected. However, if there are ways to get out of San Francisco, namely I can go to Los Angeles or San Jose, as was in that early map I showed you, those nodes with their names would go into the open set. And then, each time I would go to the open set and pick off the next node. Maybe in my algorithm I picked the node with the lowest number. Take that node and drag it over. Place it in the closed set. And look again for what places I can go from node three. Maybe I can go to node four. In node two, and they would become new entries in the open set. So the open set would contain nodes that can be reached from what was put in the closed set. With the proviso that I don't need to go back to something in the closed set if there's another way to get back to San Fransisco that's not of interest. So, the open set will only have- nodes that are not in the closed set. The calculation will stop when one of two things happen. Either, this is not talking about german there, further. Either I can't reach all the nodes, in which case the open set is exhausted, the closed set has yet to contain size n nodes, all the nodes on the map. So I'm not connected. Or all the nodes, the set of nodes that are now in the closed set are, in fact, there are size of them. And then we can stop. And the graph. Is connected. So that's our algorithm, that's what we're gonna implement. We go back and we have our matrix representation of the graph. We have it as a Boolean matrix representation. We have the size of the graph. And we're gonna keep track of. Close and open. And here is where open Of 0 is true. That's like saying San Francisco is originally in the open set, and since it'll be the only thing in the open set, It'll get automatically selected, placed in the closed set. So at this point the open set has node 0 on it. It could work if any other node is placed in it. There's nothing special about 0 to determine whether the graph is connected or not. Nothing is yet in the closed set, each iteration will add one node to the closed set, and possible many nodes to the open set. Or maybe not. The open set doesn't get added to, but is still going to the open set each time as there are entries in the open set. And we've yet not worked out whether the graph is connected. So, add to close while I'm keeping track of C size. It's the size of the closed set. The whole size is the C size we then place something in the close set. Meaning that one element is placed in the close set. So we auto increment it. The close set has that element being true. And then we go and look for things in the open set. And we gotta put into the open set anything that's already in the open set, that stays in the open set, or anything that's nearly reachable. Recall, This is just our note. This is true. If- and edge (I,J) in the graph and this is just logical or so this is the logical or operation so open is true. If open is already true or there is now a new edge that previously couldn't reach J but now reaches J. We're done if we have all the nodes in a close set or if no nodes are available in open set, if all the. Here connected, we're connected. Here, we're unconnected. These are our termination cases. And keep in mind, how many iterations are we gonna do? We're gonna do no more iterations than size. Cuz in size we either get a new node or we fail. And if we fail before then we failed before size. And if we keep getting a new node, We get everything up to San Diego and we're finished, so we only have to do this the size of the graph. So fairly straight forward algorithm Okay. So I'm going to explain a lot more about dexterous algorithm, how to implement it, how to do your homework and that'll be in our next lecture.