按照第一張圖的黃色圈內的演算法，第三張圖的的low（包括low[4]）應該全為1（我的思路程序在第三張圖下方），但是按照第二張圖上的程式走，low【4】為3。麻煩曾經學過這本書的大神解答下
uj5u.com熱心網友回復：
沒看明白LZ的提問？low是取 當前節點被訪問的次數，子節點被訪問的最小次數，父節點被訪問的次數 三個中的最小值
low[4]（E節點）至少在遍歷1（B節點）和3（D節點）時都被訪問過，遍歷到自己的時候（也就是遞回到DFSArticul(G, 4)的時候），count全域變數不可能是1，所以怎么會得出1呢？
這種遞回，你要多列印一些資訊跟蹤你才能分析理解。
參考以下帖子，有代碼的詳細注釋說明
https://blog.csdn.net/weixin_39956356/article/details/80514672
uj5u.com熱心網友回復：
為什么low是訪問次數
uj5u.com熱心網友回復：
visted[v0]=min=++count;//count是訪問計數，visted隨count增加，說明visted代表節點的訪問次數；而low是在這些visted中取最小，那它是不是也是訪問次數？uj5u.com熱心網友回復：
糾正一下說法，次數是次序這種遞回的邏輯，舉個例子來說明比較好。比如某一個節點v，它的訪問次序是visted[v]=3，它的父節點k的訪問次序是visted[k]=2（父節點k的鄰接點是v），用它的子節點w去搜索各個鄰接點（包括鄰接點的鄰接點——遞回），找出所有鄰接點中最小的序號low[w]=m，如果這個m>=3，說明w子節點的鄰接點最多只能鄰接到v，鄰接不到v的父節點k，那就說明v的子樹w沒有通向k的路徑，所以v是關節點；反過來，如果m<3，比如m=2，說明w子節點的鄰接點能通往v的父節點k（visted[k]=2=m），即v的子樹w有通往v的父節點（或祖宗節點）的路徑，所以洗掉v也沒事，所以v不是關節點。然后從這visted[v]=3，visted[k]=2，low[w]=m中取最小，設為low[v]（在這個打比方的例子中最小是2）。
在你本例中，因為書上少給了鄰接表的關系（但從前面的章節可知），所以你推算的時候可能順序不對，從A根節點出發visted[A]=1, 鄰接點L->遞回M->J->B(B的鄰接點H->遞回KGI，鄰接點D->E)，E是頂點4，此時visted[E]=11，父節點visted[D]=10，然后找E的鄰接點w，是D，已經訪問過，所以E的所有鄰接點的最小次序就是visted[D]=10（只有唯一一個鄰接點w是D），所以low[w]=10，即E自身節點visted[E]=11，父節點visted[D]=10，low[w]=10，取最小得low[E]=10，所以low[4]=10，不是1。
LZ可以把你推匯出low[4]=1的程序整理再列出來看看，我覺得是按你手畫的那張圖的鄰接關系來推算，應該也不會得出1。因為訪問到4節點時，3節點訪問過了，所以3節點這里不會遞回找到1節點（即不會進入visted[w]==0這個if分支呼叫遞回），所以low[4]要么是min=++count當前次序，要么就是父節點3的次序，要么就是子鄰接點3或5的次序，這些都不應該是1。
uj5u.com熱心網友回復：
在DFSArticul函式中，假設說最后一個頂點v是3，他的唯一一個鄰接點也就是已經訪問過的父結點2。這時候因為2已經訪問過，所以執行else if的內容 min=visited[w](=2)，然后再代進最后一句代碼low(v)=min(=2)以此類推，low值取的最大值原本是它對應的visited值，現在變成了它最大值是父節點的visited值，部分low值（沒有回邊的或者是關節點的那部分）比原來少了1。
怎么解決？
uj5u.com熱心網友回復：
else if (G->adjmulist[w].visit < min) {min = G->adjmulist[w].visit;
}
就是說，當頂點v訪問到它的父節點w時，w作為父節點肯定訪問過了，于是執行上面的陳述句，同時，如果沒有回邊，那他的父節點肯定小于min，于是low[v]=min=visited[w]
uj5u.com熱心網友回復：
之前就說了，這種遞回，你要列印資訊跟蹤分析，或者自己手影片圖推演就按你手畫的圖為例子
首先FindArticul 設定 visited[1]=1, 然后鄰接點獲得鄰接點2，呼叫DFSArticul(G,2)
DFSArticul(G,2)
--> visited[2]=min2=2，鄰接點有1和3，假設先遍歷1，訪問過，
進入else if 設定min2=1(visited[1]=1<min2=2)，
然后遍歷3，遞回
-->DFSArticul(G,3)
-->visited[3]=min3=3, 鄰接點有2和4，假設先遍歷2，訪問過，
進入else if設定min3=2(visited[2]=2<min3=3)，
然后遍歷4，遞回
-->DFSArticul(G,4)
-->visited[4]=min4=4, 鄰接點有3和5，假設先遍歷3，訪問過，
進入else if設定min4=3(visited[3]=3<min4=4)，
然后遍歷5，遞回
-->DFSArticul(G,5)
-->visited[5]=min5=5，鄰接點有3和4，假設先遍歷3，訪問過，
進入else if設定min5=3(visited[3]=3<min5=5)，
遍歷4，訪問過，沒進入else if（因為visited[4]=4>min5=3）
while回圈結束， 設定low[5]=min5=3，結束遞回
-->回到DFSArticul(G,4)，low[5]<visited[4]，所以4不是關節點
low[5]=min4=3，所以min4不變
while回圈結束，設定low[4]=min4=3，結束遞回
-->回到DFSArticul(G,3)，low[4]==visted[3]，所以3是關節點
low[4]=3<min3=2，所以min3=2不變
while回圈結束，設定low[3]=min3=2，結束遞回
回到DFSArticul(G,2), low[3]=2>min2=1，所以2是關節點
min2=1不變
while回圈結束，設定low[2]=min2=1，結束遞回
回到FindArticul，之后就不分析了。
從上面的分析來看，除了low[2]是1，low[3,4,5]都不是1
uj5u.com熱心網友回復：
DFSArticul里的 min 就是從visited[v] 和
low[w](w沒訪問過，表示子節點， if visited[w]==0分之) 和
visited[w](w訪問過，表示父節點 else if分支，相當于visited[k])
三個中取取最小
然后賦值給low[v]=min
這也就是書里所謂的定義一個low[v]的意思
uj5u.com熱心網友回復：
這里需要知道的一點是 visited[w]不一定等于 low[w]，比如上面分析的low[3]=2, visited[3]=3, 估計你是把這兩個搞混了，才會覺得low[3]應該等于low[2]應該等于1，所以對于節點4來說，如果最小是父節點，也只會取visited[3]，而不是取low[3]，所以它怎么也不會1（因為visited[3]=3）uj5u.com熱心網友回復：
可以去caion.com.cn上面找答案的轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/119987.html
標籤：C++ 語言
上一篇：這是一個剛開始學C語言課程小白的求助，求大佬拯救一下失足少女吧qwq
下一篇：剛接觸C語言的小白，求個答案。