深度优先搜索算法 - 计算连通分量

Question

大家好，我有问题需要 help.Maybe 它是题外话，但我已经将其发布在代码审查中，但没有人回答。我使用伪代码编写了此代码，我 stuck.I 应该检查一个连接组件中的顶点数是否为偶数。我的想法是实现 DFS 并放置一个计数器，然后检查 counter%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)`

Answer 1

任何时候你将 Discovered[u] 设置为 True，但它还没有 True，那么你已经找到了一个新的连接顶点，并且应该增加你的计数器。

因为 DFS1 从来没有 returns 任何东西，我不确定检查它 returns 会有多大帮助，特别是因为你在用一个不知道的变量调用它之后检查那个范围。

Answer 2

您可以在 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)

深度优先搜索算法 - 计算连通分量

Depth First Search Algorithm - counting connected components

algorithm

depth-first-search