Depth First Search Algorithm - counting connected components

Question

Hi guys I have question and need help.Maybe it's offtopic but I've already posted it on Code Review but noones answers. I've written this using pseudocode, and I am stuck.I should examine if number of Vertices in one conected component is even. My idea is to implement DFS and to put one counter and then to check whether counter%2==0 is or not. My problem is I don't know where to put counter. Let's say DFS: is main method.

G = (V,E) V- vertices, E-edges s-start point(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)`

In DFS1 sum values of all recursive calls to DFS1 and returns that value plus 1 — Arturo Menchaca
– Arturo Menchaca, Commented Mar 31, 2016 at 18:40
Can you please explain me little bit more in detail, why value +1, and where do I initialize that sum? if i put it there int sum = 0 it will always be 0, because of recursive method. Maybe I don't understand this, but would appreciate if u could explain me — Buzz Black
– Buzz Black, Commented Mar 31, 2016 at 18:45

Arturo Menchaca · Accepted Answer · 2016-03-31 18:55:12Z

4

You can declare counter inside DFS1, like 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

Or declare the counter in a global scope and just increment it on each DFS1 call:

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)

answered Mar 31, 2016 at 18:55

Arturo Menchaca

16.1k1 gold badge32 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Scott Hunter · Accepted Answer · 2016-03-31 18:55:04Z

0

Any time you set Discovered[u] to True, and it isn't already True, then you have found a new connected vertex, and should increment your counter.

Since DFS1 never returns anything, I'm not sure how helpful checking what it returns will be, especially since you check after calling it with a variable not know in that scope.

answered Mar 31, 2016 at 18:55

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

1 Comment

Buzz Black Over a year ago

Thank you for the answer. I think I could do it like the guy before explained. it should work, i think.

Collectives™ on Stack Overflow

Depth First Search Algorithm - counting connected components

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related