Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to use Tarjan algorithm to solve strongly connected components". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Algorithm framework

Let's consider a question: what is the core principle of the algorithm for strongly connected component decomposition?

If you have read our previous article, then this question should not be difficult for you to answer. Since it is a strongly connected component, it means that every point in the component can be connected to each other. So it's easy to think that we can start from a point and find a loop to get it back to its starting point. In this way, the points passed along the way are all part of the strongly connected component.

However, there will be a problem, that is, we need to ensure that every point in the strongly connected components is traversed, and there can be no omissions. To solve this problem, we can also think of a solution, for example, we can use a search algorithm to search all its reachable points and all paths. But in this way, we will encounter another problem. This problem is the connectivity between strongly connected components.

Let's look at an example:

In the picture above, if we start from point 1, we can reach every point in the picture. But we will find that 1, 2, 3 is a strongly connected component, and 4, 5, 6 is another. When we look for the strongly connected component in which 1 is located, we are likely to bring in the three dots: 4, 5, 5, 6. But the problem is that they are self-contained and should not be counted among the strongly connected components of 1.

If we sort out the above analysis and ideas, we can find that the core of the strongly connected component decomposition algorithm is to solve these two problems, that is, the completeness problem. Completeness means no omission, redundancy and error. After we want to understand the core problem, it is easy to build a thinking framework, and then we will look at the description of the algorithm will be much easier to understand.

Algorithm details

The first mechanism of the Tarjan algorithm is the timestamp, which is to put a value on each traversal point as it traverses. This value indicates how many elements are traversed.

This should be easy to understand. We just need to maintain a global variable and let it increment itself when traversing. Let's write down the Python code to show you:

Stamp = 0 stamp_dict = {} def dfs (u): stamp_ [u] = stamp stamp + = 1 for v in Graph [u]: dfs (v)

Through the timestamp, we can know the order in which each point is visited, which is a positive order. For example, suppose u and v are two points, and the timestamp of u is smaller than v. Then there are only two possibilities for the relationship between them. the first is that u can be connected to v, indicating that the link from u to v can be opened. The second is that u cannot be connected to v, which is irrespective of whether the reverse from v to u is connected or not, because they must not be connected to each other.

So if we want to find the connected path, we also need to find the reverse path. In the Kosaraju algorithm, we use the reverse graph to achieve. In Tarjan, a different approach is taken. Because we already know the timestamp of each point, we can find the reverse path through the timestamp. What do you mean? In fact, it is very simple that when we traverse u, if we encounter a v with a smaller timestamp than u, then there is a reverse path from u to v. If v is not out of stack at this time, which means that v is upstream of u, then there is a path from v to u. This shows that u and v can be connected to each other.

Now that we have found a pair of interconnected u and v, we need to record them. But the question is, how do we know when the record ends? Where is this boundary? the Tarjan algorithm designs another ingenious mechanism to solve this problem.

This mechanism is the low mechanism, and low [u] represents the minimum timestamp of all points to which u can be connected. The smaller the timestamp, the higher the position in the search tree, and it can also be understood as the highest point in the search tree to which u can connect. So it is obvious that this point is the root of a subtree of the search tree where the strongly connected component of the u point is located.

There may be a little twist here. Let's take another look at the picture:

The sequence number of the nodes in the graph is the time stamp of recursive traversal, and we can find that their low value is 1 for each point on the graph. It is obvious that 1 this point in the search tree is the ancestor of these three points. That is to say, the traversal of this strongly connected component begins at the point 1. When 1 hits the stack, it means that the subtree with a 1-bit root has been traversed, and all possible strongly connected components have been found.

This leads to another problem. Let's assume that the current point is u. How do we know if the point u is the root of the tree like figure 1? Is there any way to mark it?

Of course there are, and one feature of such dots is that their timestamps are equal to their low. So we can use an array to maintain the strongly connected components found, and empty the array when the tree roots to which these strongly connected components can be traversed are off the stack.

Let's sort out the above logic and write the code:

Scc = [] stack = [] def tarjan (u): dfn [u], low [u] = stamp, stamp stamp + = 1 stack.append (u) for v in Graph [u]: if not dfn [v]: tarjan (v) low [u] = min (low [u], low [v]) elif v in stack: low [u] = min Dfn [v]) if dfn [u] = = low [u]: cur = [] # the element after u in the stack is a complete strongly connected component while True: cur.append (stack [- 1]) stack.pop () if cur [- 1] = u: break scc.append (cur)

Finally, let's take a look at the classic example we talked about earlier:

First of all, we start at 1 o'clock and search until the end of 6. When traversing to 6, DFN [6] = 4 focus low [6] = 4. When 6 leaves the stack, the condition is satisfied, and 6 is called a strongly connected component independently.

Similarly, when 5 exits, the condition is also satisfied, and we get the second strongly connected component.

Then we go back to node 3, which can also traverse to node 4 and connect to 1. Since 1 point is already in the stack, it will not continue recursive 1 point, but will only update low [4] = 1. Similarly, when 4 exits, it will update 3 so that low [3] = 1.

Finally, we return to node 1 and traverse through node 1 to node 2. The 4 points that can be connected are already in the stack, and DFN [4] > DFN [2], so the 2 points will not be updated. After returning to 1: 00 again, there is no other point to connect at 1: 00, so quit. When you exit, you find that low [1] = DFN [1], and the remaining four elements in the stack are all strongly connected components.

This is the end of the content of "how to use Tarjan algorithm to solve strongly connected components". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.