Depth First Search Algorithm - Zähle verbundene Komponenten

Question

Hallo Leute, ich habe Fragen und brauche Hilfe. Vielleicht ist es offtopic, aber ich habe es bereits auf Code Review geschrieben, aber noones Antworten. Ich habe dies mit Pseudocode geschrieben, und ich bin steckengeblieben. Ich sollte prüfen, ob die Anzahl der Vertices in einer Komponente gerade ist. Meine Idee ist, DFS zu implementieren und einen Zähler zu setzen und dann zu überprüfen, ob der Zähler% 2 == 0 ist oder nicht. Mein Problem ist, ich weiß nicht, wo ich den Schalter stellen soll. Sagen wir DFS: ist die Hauptmethode.

G = (V, E) V- Ecken, E-Kanten s-Startpunkt (Vertex)

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

können Sie erklären Zähler innerhalb DFS1, etwa so:

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 

Oder den Zähler in einem globalen Rahmen erklären und es nur DFS1 Anruf auf jeden Schritt:

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

Jedes Mal, wenn Discovered[u] zu True gesetzt, und es ist nicht schon True, dann Sie haben einen neuen verbundenen Knoten gefunden und sollten Ihren Zähler erhöhen.

Da DFS1 nie etwas zurückgibt, bin ich mir nicht sicher, wie hilfreich es ist zu überprüfen, was es zurückgibt, vor allem, da Sie nach dem Aufruf mit einer Variablen in diesem Bereich nicht überprüfen.