Hey guys, welcome back. In today's video, we're going to look at the algorithm to find articulation points in bridges, but this time with actual source code, make sure you watch the last video where I outline the details of how to actually find bridges and articulation points. Otherwise, you'll be a little bit confused in this video. As always, you can find the source code I present in this video@github.com slash William fuzzer slash algorithms. So let's dive right in. Alright, here we are in the source code, find bridges.

We'll look at the source code find articulation points shortly. So this source code is written in the Java programming language. And here I have a class which will find all the bridges in an undirected graph stored as an adjacency list. But before I get into the details of the code, I actually want to show you how the code works and how you're supposed to use it. So this is the main method that'll set up The graph. But before we even do that, I'm just going to scroll down here and look at some of the methods used to actually create the graph and make something useful.

So this first method will create a graph with n nodes. So I create a list of lists of type integer, which is basically an adjacency list with directed edges. So all I do is I create a new ArrayList and then fill that list of lists with empty lists, and then return the graph. That's our graph for now, and then later on, what we'll do is we'll call this add edges method to add directed edges into the graph. So you see, first we add an edge from a node to a node and then to that node, from that node. The naming is a little confusing from into I use from to me The the node the edge starts out and to be the node Yeah, just going to.

So in this example, I have a graph with nine nodes. So I initialize n to be nine. Then I create the graph and then add all my edges. You will notice that this graph is actually the graph from the slides in the last video. And then what we're going to do is we're going to pass this graph and the number of nodes into the class above, which is going to be our solver. And then the solver is going to be able to find all the bridges and return all the bridges as a list of integers.

Then once you have this list of bridges, bridges are going to be stored as pairs. So every two integers that are adjacent in, and pairs are going to be bridges. So I pull those out, and I print them. And this is the result you would expect for this graph. Alright, great. Now you're wondering how does the magic happening here.

So let's scroll up to the constructor. And actually, let's look at the instance variables. So we have n, which is the number of nodes in the graph, ID, which is that ID number to label each node. So we're going to give each node A unique ID. And we keep track of well what was the last ID then I have two arrays, which track information about the nodes. So low is for the low link values and IDs is to track the ID of each node we gave a node with the ID variable.

Then just a Boolean array to track whether or not node was visited. And finally the graph. So in the constructor, of course, give the graph and the number of nodes, it checks some conditions to make sure the graph is legit. Okay, so now we've constructed the object, or the solver object. And the method we're interested in is find the bridges. So the fine bridges just initializes all of our variables.

So set ID to be zero, initialize or allocate some memory for the low link values and the ID values and the visited array. It's good practice not to do this work into the constructor. Just because if you're just creating a bunch of these objects, but never use them, you might surprise the person initializing the object why they're having so much memory usage. Then initialize the bridges array to be initially empty and then we pass that into the depth first. search method, it gets populated and then returned afterwards. So for each node, or node ID right now, loop through all the nodes.

And if that node hasn't been visited yet start a depth first search on that node. And called depth first search method with eyes. The first arguments are the current node minus one for the parent, and then pass in the bridges array. So some housekeeping stuff, like any usual depth first search, visit the node. And then what we're going to do is we're going to initialize the loading value and the ID of that node to just be a unique ID which we increment. All right, then we visit from from the current node, all the nodes we can reach and skip, skip the node that we were just at So that is the parent node.

So we don't want to do our depth first search and then immediately return to the node we just visited. So continue on those cases. And we'll do this because we have an undirected graph, remember. So if you haven't visited the node yet, then recursively, call our depth first search method and keep probing. While if you have, if you're trying to visit a node you've already visited, then you want to take the minimum of the current link value and the ID of the node you're going to. Otherwise on the callback of depth first search method is the other low link command statement, which differs from this one slightly in that we have a we're taking the minimum now not have the idea of that node, but the load link of the other node.

And as you saw in the slides, the condition for bridge is if the idea of the node or app is less than the load link of the node or going to this means we have a bridge and removing that bridge will cause the number of connected components to increase. So append both act, and two, which are the note IDs of the bridge, and put them in the bridges array, and fill that up, and then eventually return that down here. So that is all for bridges. Now let's look at articulation points, which is really almost the same algorithm. So if we look at this, the only thing that's really different is we have a variable to track the number of outcoming edges from the start node or what I call the root node in this script. And other than that, differences are that we have another Boolean array called his articulation point instead of the bridges or a two track bridges and that We have to reset the number of upcoming edges for every depth first search we do that makes sense.

And what else is different? Oh yes, we have a less than or less than or equal to, as opposed to just less than two track cycles as well and mark off those as articulation points. And I think those are the major differences for didn't forget anything between articulation points and bridges. Oh, of course, we have to count the number of upcoming edges from the root. That's pretty important. And here's the same graph as before, but instead of printing bridges, it prints articulation points.

So some very subtle differences between finding articulation points and bridges, but still very important ones. Guys, thank you for watching and if you learn something, please like this video and subscribe for more mathematics and computer science videos. See you