Welcome back. My name is William. Today we're going to talk about how to develop an algorithm to find bridges and articulation points in an undirected graph from a computer science perspective. For starters, let's talk about what a bridge is a graph. bridges are sometimes also called cut edges. Essentially, if you have a graph, which is a connected component, a bridge is an edge, which if removed increases the number of connected components in the graph.

The name bridge makes sense because if you think about connected components as islands, than a bridge is what separates them. So for example, in this graph below, there would be three possible bridges, which are those edges in pink, because if you remove any of them, the graph is divided into two components and articulate Point, also called a cut vertex is very similar to a bridge, in that the criteria for being an articulation point is that it needs to be any node whose removal will increase the number of connected components. As an example, on this graph, there would be three articulation points, since removing any of these vertices will divide the graph in tip. As we start to think more about bridges and articulation points, we realize how important they are in graph theory. In a real world situations, bridges and articulation points often hint at bottlenecks or vulnerabilities or weak points in the graph.

Therefore, it's important to be able to quickly find and detect where these occur. We'll begin by investigating how to find bridges and then slightly modify that algorithm to also find articulation points. In the simplest way I can explain it. This is the algorithm we'll be following. To find bridges in an undirected graph. First, start at any node in the graph and begin doing a depth first search traversal labeling nodes with an increasing ID as you encounter them.

During the traversal, you will need to keep track of two variables. The first is the nodes ID, which I just mentioned and the other is the nodes low link value. During the depth first search bridges will be found where the idea of the node your edge is coming from is less than the low link value of the node. The edges going to. The old value of a node is defined as the smallest node ID reached From the node you're currently at when doing the depth first search, including the ID of the node itself. This is an interesting concept we'll get back to later.

For now let's look at an example. Suppose we have the following graph we've been looking at, and we want to find out where all the bridges are. Let's begin our depth first search on the node at the top left corner. As we do our depth first search, we're going to label each node with a unique ID, which I will place inside the node. I will also mark nodes which are visited as yellow and the nodes which are blue as unvisited. So let's finish off our depth first search.

So explore all nodes transforming on directed edges into directed ones and marking off edges are nodes rather, as visited. So that would conclude our depth first search, I want to take a moment to think about what all the low link values would be for these notes. As a reminder, the low link value of a node is defined as the smallest ID reachable from that node. For now initial is all allowing values to be equal to each nodes ID. I placed the low link value of each node on the exterior of that node. If you inspect node one, you will notice that in slow link value should be zero because there exists a path of edges going from node one to node zero and node zero has an ID of zero.

So we can update node one's low link value to zero. Similarly, node two's low link value should also be zero, because node two to node zero there exists a path. However, nodes three, four and five are already at their optimal low link value because there's no other node they can reach with a lower ID. However, node sixes low link value can be updated to five since there is a path from node six to node five via these sequence of edges. And we can also update node seven at a low link value by the same logic. So in general when we look at all the directed edges, So we have traversed, the ones which form bridges in our graph are the ones where the ID of the node you started that is less than the low link value of the node, you're going to take a moment to think about why this is true.

Let's go where these bridges actually occur. In each instance, the idea of the node with a directed edge started at is less than the loading value of the node, it's going to rephrasing that in another way, it means there was no edge connecting back to the startup component, which is really the definition of what a bridge is. Otherwise, if there was an edge connecting backwards to the start of the component, the low link value of where the edge is pointing to would be at least as low as the ID of the node you started that because it would be reachable. For example, if I have an edge from node eight to node two, suddenly the edge from node two to node five is no longer a bridge, because the loading value on node five got updated to two, and our bridge property highlighted in teal no longer holds.

Let's take an aside and think of the time complexity of the algorithm I just presented. Right now we're doing a depth first search to label all the nodes plus v more depth first searches to find all the low link values for roughly v times v plus e in the worst case, if you're really pessimistic and careless about your programming. Luckily, however, we can do much better than this and instead update all the local investors in one pass for a linear time complexity. Let's look at some pseudocode. on how to do this in linear time. I'll show you some actual code in the video that follows.

But let's get started. In the global or class scope, I defined three variables. The first is ID, which I use to label each node with a unique ID number, then I have an undirected graph G. The last is n, which is the number of nodes in the graph. Following the top level variables are three arrays, which track information about each node in the graph. index i in each of these arrays represents node i in the graph. So the first array tracks the ID of note I.

The second array tracks the Loading value of node and the visitor rate keeps track of whether or not we have visited node. Moving on the Find bridges function is what actually finds the bridges. In the method I iterate over all the nodes which have not yet been visited by our depth first search. This is to ensure that we find other bridges in our graph even if our graph consists of multiple connected components. Let's dive into the depth first search method which is where the real work is happening. The first argument is the current node you're at which is node odd, then is the parent node which I set to minus one because there is no previous node and last is the bridges array which we are populating.

So here we are in the depth research method itself, the arguments to the method or just as I described them to you The first variable is at, which is the current node ID, then comes parent, the previous node ID, and the array bridges, which stores pairs of nodes which form bridges in a flat array. In the first three lines of the method, I simply do some housekeeping stuff which is marked the current note as visited, increment the ID value variable and assign the current node to have a default ID and low link value. Then we get into the actual depth first search traversal bit. So we iterate over each edge from the node we're at and attempt to go to each node which I've labeled to. Since this is an undirected graph, there is bound to be an edge that directly returns to the node we were just previously at.

We Which is the parent node, which we want to avoid doing. So we continue on those cases. If the next node we're going to is not visited, then we recursively call the depth first search method. The two key lines in this method are the main functions which differ ever so slightly. The first one happens on the callback, and is what propagates the low link values. While the second one is when you try to visit an already visited node, which has a chance of having a lower ID, then your current link value.

Then the last bit just checks if our bridge condition is met, and appends a pair of node IDs to the bridges array. All right, now let's look at an example of all this in action. Suppose we have the following graph Again, and we start our depth first search somewhere. Let's start at node zero and explore from there. So now as the first instance of something interesting happening, we're trying to visit an already visited node. Since node two is able to reach node zero from where it is, we can update its low link value.

And that was the second main statement executing. Continuing on our depth first search, which takes us downward. And now we get to explore the other branch we have not visited. Again, we have in an edge which reaches out to find a node with the lower ID. So we need to update Our loading value for the current node, which is node eight. Now we can update node sevens loading value to five, on the callback of the depth first search method.

This is an instance of the first min function actually doing something just to put everything into context. The red box is a line which was just invoked. And now that statement we just saw it gets executed for every note on like, come back, all the way back to the root node. And now we have the same result as before, but we did it with just one pass. So again, here are all the bridges that we found. Perfect.

Now let's move away from bridges and start discussing how we can find articulation points by modifying the algorithm for bridges. A first simple observation we can make about articulation points is that on a connected component with three or more vertices if an edge UV is a bridge, then either u or V is an articulation point. This is a good starting point because it allows us to easily find where articulation points occur. For example, consider the following graph. You will notice that there is a bridge between nodes zero and one mean that either node zero or node one is an articulation point. Unfortunately, this condition is not sufficient to capture all articles.

Points. There exist cases where there is an articulation point, but there is no bridge nearby. For example, in the following graph, node two is an articulation point because its removal would cause the graph to split into two components. So the new question is, when do these cases occur? And the short answer is that it has to do with cycles in the graph. To understand why, let's look at an example.

Suppose you're traversing a graph, and eventually, you somehow arrive a node zero. Initially, suppose node zero has a low link value also zero. And, like in any depth for search, you would continue on to explore the graph. And eventually, if you ever really encountered the node that started the cycle with an edge, its ID gets propagated throughout the cycle. During the callbacks of the depth first search, this is the case because we're reassigning the new loading value to equal the min of the current loading value and the ID of the node we were just visiting. You see now that node five has a loading value of zero, acquired from the ID of node zero.

This gets spread or propagated as I like to say, throughout the cycle. Now, what you'll notice is that the ID of the node you started that is equal to the loading value of where it's going to this indicates that there is a cycle. What is key here is that the presence of a cycle implies that the node is an articulation point. This is because a cycle in a graph corresponds to a strongly connected component and removing the node which started the cycle, who is also connected to another component will sever the graph into. However, there's just one exception to this. And this is when the starting node you choose has either no outgoing edges, or as part of a cycle and only has one outgoing edge.

This is because either the node is a singleton, a standalone note. That is the case with zero outgoing edges, or the notice trapped in a cycle where it only has one outgoing edge. To be an articulation point, you need to have more than one outgoing edge. For example, in the graph on the right, we start a node zero the green node and is not an articulation point despite our condition of the ID equaling the loading value. However, as soon as we add another edge to our starting node, it becomes an articulation point. So this is something to watch out for and is unique to the starting note.

Let's now take a quick look at the changes we need to do to our finding bridges algorithm to find articulation points. To begin with, we'll need a way to track the number of outcoming edges. The starting node has so I define a new variable called out edge count. Next I define a Boolean array called is art, which has true or false depending on whether or not note AI is an articulation point. Ultimately, this will be the return value of the find art points function. In the body of the find art points function I reset the edge count variable for every connected component.

And after the depth research mark the starting node on as either an articulation point or not based on how many outcoming edges were found. Inside the depth first search method, all I added was an if statement to increment the number of outcoming edges from the starting node. Besides that, I added the equals case to track articulation points found via cycles and kept the less than keys to find articulation points found via bridges. In a real implementation, you can merge these two if statements into a single clause. However, I want to distinguish finding articulation points from bridges via those from cycles. And that is all for now.

In the next video, we'll be looking at some actual source code and not just some pseudocode guys if you enjoyed this video, please hit the like button and subscribe for more Computer Science and Mathematics videos. Thank you