Derinlik İlk Arama Algoritması - bağlı bileşenlerin sayılması

Question

Merhabalar, sorularım var ve yardıma ihtiyacım var. Belki de bu konu kapalı olsa da, bunu Kod İnceleme'ye yazdım, ancak cevaplar verdim. Bunu sahte kod kullanarak yazdım ve sıkıştım.Konferanslı bir bileşendeki Vertis sayısı eşit olup olmadığını incelemeliyim. Benim fikrim, DFS'yi uygulamak ve bir sayaç koymak ve% 2 == 0 değerinin olup olmadığını kontrol etmek. Benim problemim nereye karşı koymak bilmiyorum. DFS: ana yöntem diyelim.

G = (V, E) V özet olarak, e-kenarları s başlangıç ​​noktası (tepe)

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)` 

Answer 1

Çok gibi DFS1 içindeki sayacı ilan edebilir Herşeyden DFS1 toplamı değerlerinin ise

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) 

Answer 2

Eğer True için Discovered[u] ayarlamak her zaman, ve zaten daha sonra True değil, Bağlantılı yeni bir köşe buldunuz ve sayacınızı arttırmalısınız.

DFS1 hiçbir zaman hiçbir şey döndürmediğinden, özellikle bu kapsamda bilmediğiniz bir değişkenle aradıktan sonra kontrol ettiğinizden ne döndüğünü kontrol etmenin ne kadar yararlı olacağından emin değilim.

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 

Ya da global kapsamda sayacı beyan ve sadece her DFS1 çağrı üzerine bir artıracaktır: