深度優先搜索算法 - 計數連接組件

嗨，大家好，我有問題，需要幫助。也許它是不重要的，但我已經將它發佈在Code Review上，但noones的答案。我使用僞代碼寫了這個，並且我被卡住了。我應該檢查一個連接組件中的頂點數是否是偶數。我的想法是實現DFS並將一個計數器，然後檢查計數器％2 == 0是否。我的問題是我不知道在哪裏放櫃檯。假設DFS：是主要的方法。深度優先搜索算法 - 計數連接組件

G =（V，E）V-頂點，E-邊緣 S-開始點（頂點）

DFS(G,s): 
boolean result <-- false 
Discovered[v] <-- false for all Vertices V(v) 
DFS1(G,s) 
if (DFS1(G,u) % 2==0) 
result <-- true 


DFS1(G,u): 
Discovered[u] <-- true 
// counter ++   But where I should initialize it?? 
foreach Edge (v,u) incident to u 
if !Discovered[v] 
DFS1(G,v)`

來源

2016-03-31 Buzz Black

在所有的DFS1和值遞歸調用DFS1並返回該值加上1 –

您能否詳細解釋一下我爲什麼值+1，以及我在哪裏初始化該總和？如果我把它放在那裏int sum = 0它將永遠是0，因爲遞歸方法。也許我不明白這一點，但會很感激，如果你能解釋我 –

你可以聲明櫃檯裏面DFS1，像這樣：

DFS1(G,u): 
    Discovered[u] = true 
    int counter = 1      // Count actual node   
    foreach Edge (v,u) incident to u 
     if !Discovered[v] 
      counter += DFS1(G,v)  // Count descendant nodes 
    return counter

還是在全球範圍內聲明的計數器，只是增加它在每個DFS1電話：

int counter = 0 

DFS(G,s): 
    boolean result = false 
    Discovered[v] = false for all Vertices V(v) 
    DFS1(G,s) 
    if (counter % 2 == 0) 
     result = true 

DFS1(G,u): 
    Discovered[u] = true 
    counter++ 
    foreach Edge (v,u) incident to u 
     if !Discovered[v] 
      DFS1(G,v)

來源

2016-03-31 18:55:12

非常感謝！ –

如果此解決方案可以幫助您，請將其標記爲已接受。謝謝 –

設置Discovered[u]到True任何時間，並且它尚未True，然後你找到了一個新的連接頂點，並且應該增加你的計數器。

由於DFS1永遠不會返回任何東西，我不確定檢查它返回的內容是多麼有用，特別是因爲您使用該範圍內的某個變量調用它後檢查。

來源

2016-03-31 18:55:04

謝謝你的答案。我想我可以像解釋之前的那個人那樣做。它應該工作，我想。 –

深度優先搜索算法 - 計數連接組件

回答

相關問題