According to the first picture of the yellow circle algorithm, the third picture of the low (including low [4]) should be full of 1 (my train of thought process in the third picture below), but in accordance with the procedures on the second picture, low [4] 3, trouble once studied under the great god answers in this book

CodePudding user response:

Didn't see LZ's question?
Is low, the number of the current node is accessed, the smallest number of child nodes referred to, the parent node is accessed the lowest value of the number of three
Low [4] (E) at least in the traversal (node B) 1 and 3 (D) were visited, traverse to ourselves (that is, recursive to DFSArticul (G, 4)), the count global variables can't be 1, so how can reach 1?
This kind of recursion, you want to print some more information tracking can you analysis understanding,
Refer to the following post, code detailed annotated
https://blog.csdn.net/weixin_39956356/article/details/80514672

CodePudding user response:

reference 1st floor qybao response:

didn't see LZ's question?
Is low, the number of the current node is accessed, the smallest number of child nodes referred to, the parent node is accessed the lowest value of the number of three
Low [4] (E) at least in the traversal (node B) 1 and 3 (D) were visited, traverse to ourselves (that is, recursive to DFSArticul (G, 4)), the count global variables can't be 1, so how can reach 1?
This kind of recursion, you want to print some more information tracking can you analysis understanding,
Refer to the following post, code detailed annotated
https://blog.csdn.net/weixin_39956356/article/details/80514672

Why is low, visited

CodePudding user response:

Visted/where v0=min=+ + count;//visit count count is visted increases with the count, explain visted on behalf of the node number of visits; And is low in these visted take minimum, it is also visited?

CodePudding user response:

Correction, the number is order
This recursive logic, for example to illustrate how is better, such as a node v, it is the access sequence of visted [v]=3, its parent node the access sequence of k is visted [k]=2 k (parent node adjacency point is v), and use it to search for the child nodes of the w all adjacent points (including the adjacency point of adjacency point - recursion), find all adjacent points minimum number low [w]=m, if the m>=3, w child node adjacency point maximum adjacency to v, v adjacency is less than the parent node k, then there is no access to k v subtree w path, so v is key points; On the other hand, if m<3, such as m=2, w child nodes of the adjacent point to the parent node k to v (visted [k]==2 m), namely v subtree w have the parent node to v (or the ancestor nodes) path, so delete v is ok also, so v is not the key, and then from the visted [v]=3, visted [k]=2, low [w]=m of the youngest, is set to low [v] (in this example in the case of the minimum is 2),
In this case, you less because the book to the relationship between adjacency list (know) from the previous section, so you may order is wrong, according from A root node visted [A]=1, adjacency point L - & gt; Recursive M - & gt; J - & gt; The adjacency point B (B H - & gt; Recursive KGI, adjacency point D - & gt; "E" is for vertex 4 E), and the visted [E]=11, the parent node visted [D]=10, then find the adjacency point E w, D, has been visited, so E all adjacent points, the minimum order is visted [D]=10 (there is only one adjacent point w D), so low [w]=10, namely node visted E itself [E]=11, the parent node visted [D]=10, low [w]=10, taking minimum too low [E]=10, so low, [4]=10, not 1,
LZ can you deduce the low [4]=1 the process of sorting list to see again, I think it is in your hand painted the picture of the adjacency relations, according to should also won't draw 1, because access to 4 nodes, visited 3 nodes, so here not recursive find 1 3 node (i.e., not into visted [w]==0 if the branch called recursion), so low, [4] is either min=+ + count the current order, or the order of the parent node 3, or the order of the adjacent point 3 or 5, none of this should be 1,

CodePudding user response:

In DFSArticul function, assuming that the last vertex v is 3, he's only an adjacency point which is the parent node 2 has been visited, at that time because 2 has been visited, so the content of the execution else if min=visited [w] (=2), and then into the last line of code generation low (v)=min (=2)
By analogy, low value to maximize the originally its corresponding visited value, now turned into a maximum its parent node visited value, some low value (no back side or is that part of the key points) less than the original one,
How to solve?

CodePudding user response:

Else if (G - & gt; Adjmulist [w]. Visit & lt; Min) {
Min=G - & gt; Adjmulist [w]. Visit;
}
That is to say, when access to its parent node w vertex v, w as the parent node must be visited, and execute the statement above, at the same time, if there is no back side, that his parent node must be less than min, so low [v]=min=visited [w]

CodePudding user response:

Said before, this kind of recursion, you want to print information tracking analysis, or manually draw inference
As you hand painted the graph example

First FindArticul set visited [1]=1, then the adjacent point for adjacency point 2, call DFSArticul (G, 2)

DFSArticul (G, 2)
- & gt; Visited [2]=min2=2, adjacent points 1 and 3, assuming that traverse the first 1, visit,
Enter the else if set min2=1 (visited [1]=1 & lt; Min2=2),
Then traverse 3, recursive

- & gt; DFSArticul (G, 3)
- & gt; Visited [3]=min3=3, adjacency point 2 and 4, assuming that traverse the first 2, visited,
Enter the else if set min3=2 (visited [2]=2 & lt; Min3=3),
Then traverse 4, recursive

- & gt; DFSArticul (G, 4)
- & gt; Visited [4]=min4=4, adjacency point 3 and 5, assuming that traverse the first 3, visited,
Enter the else if set min4=3 (visited [3]=3 & lt; Min4=4),
Then traverse 5, recursive

- & gt; DFSArticul (G, 5)
- & gt; Visited [5]=min5=5, the adjacent points 3 and 4, assuming that traverse the first 3, visited,
Enter the else if set min5=3 (visited [3]=3 & lt; Min5=5),
Through 4, visited, not enter else if (because visited [4]=4 & gt; Min5=3)
End of the while loop, set low [5]=min5=3, the end of the recursive

- & gt; Back to DFSArticul (G, 4), low [5] Low [5]=min4=3, so min4 constant
End of the while loop, set low [4]=min4=3, the end of the recursive

- & gt; Back to DFSArticul (G, 3), low [4]==visted [3], so 3 is a joint point
Low [4]=3 & lt; Min3=2, so min3 unchanged=2
End of the while loop, set low [3]=min3=2, end recursive

Back to DFSArticul (G, 2), low [3]=2 & gt; Min2=1, 2 is the key
Unchanged min2=1
End of the while loop, set low [2]=min2=1, the end of the recursive

After returning to FindArticul, not analysis,

From the above analysis, in addition to low [2] is 1, low (three, four, five) are not 1

CodePudding user response:

DFSArticul min is from
Visited [v] and
Low [w] [w haven't visited, said child nodes, if visited [w]==0 points) and
Visited [w] [w visited, said the parent node else if branch, equivalent to visited [k])
Three to take take minimum
Then assigned to low [v]=min
This is the book called the definition of a low [v] mean

CodePudding user response:

Need to know some here is visited [w] does not necessarily equal to low [w], such as the low analysis above [3]=2, visited [3]=3, estimates that you are the two mixed up, will only feel low [3] should be equal to low [2] should be equal to 1, so for node 4, if the minimum is the parent node, it would only be take visited [3], rather than take a low, [3], so it wouldn't have 1 (because visited [3]=3)

CodePudding user response:

You can go to caion.com.cn to find the answer