为什么我使用 DFS 得到的连接组件比我的图形的实际连接组件少？

Question

我正在尝试找到一种方法 countVertices()，它需要使用 DFS returns 给定顶点的同一连通分量中的顶点数。

我无法理解为什么当我的图形有 3 个连接组件（包括父组件）时我总是得到 2。我试过的所有测试都出错了

我的方法代码如下所示：

public static int countVertices(Graph g, Graph.Vertex v) {
    Set<Graph.Vertex> known = new HashSet<>();
    int num = 0;

    if(g == null || v == null)
        return 0;

    for(Graph.Vertex u : g.getAllVertices()) {
        if(!known.contains(u)) {
            num++;
            DFS(g, u, known);
        }
    }

    return num;
}

public static void DFS(Graph g, Graph.Vertex v, Set<Graph.Vertex> known) {
    known.add(v);

    for(Graph.Vertex vertex : g.getNeighbours(v)) {
        if(!known.contains(vertex))
            DFS(g, vertex, known);
    }
}

我在 main() 方法中尝试了以下方法：

 public static void main(String[] args){
     Graph g = new Graph();
     Graph.Vertex v = new Graph.Vertex(1);
     Graph.Vertex w = new Graph.Vertex(2);
     Graph.Vertex x = new Graph.Vertex(3);
     Graph.Vertex y = new Graph.Vertex(4);

     g.addVertex(v);
     g.addVertex(w);
     g.addVertex(x);
     g.addVertex(y);
     g.addEdge(v, w);
     g.addEdge(w, y);

     System.out.println(countVertices(g, v)); // this outputs 2, it should be 3
     System.out.println(countVertices(g, x)); // this outputs 2, it should be 1
}

我不知道我做错了什么？如果有任何帮助，我将不胜感激。

编辑：

public static int countVertices(Graph g, Graph.Vertex v) {
    Set<Graph.Vertex> known = new HashSet<>();
    int num = 1;

    if(g == null || v == null)
        return 0;

    //for(Graph.Vertex u : g.getNeighbours(v)) {
        if(!known.contains(v)) {
    num++;
    DFS(g, v, known);
        }
    //}

    return num;
}

Answer 1

v-w 和 w-y 是属于同一组件的 2 条边。 x 是唯一孤立的顶点。因此，正确的输出是 2 个连通分量而不是 3 个。

编辑：如果删除 v-w 或 w-y 之间的边，您将有 3 个连通分量。

我最近使用的一种方法是检查两个顶点是否具有相同的根。在您的情况下，如果我们将 v 作为根，则 w 是 v 的子节点，y 是 w 的子节点 => y 是 v 的子节点，因此是一个组件。 x 是没有子节点的根顶点，因此是另一个组件。我希望这能提供一些关于连接组件的见解。

至于顶点数，你的int num = 0应该是int num = 1吧。这是因为如果图不为空，则图有至少个顶点。

// after a short discussion, we found the solution
// return the size of HashSet known
public static int countVertices(Graph g, Graph.Vertex v) {
    Set<Graph.Vertex> known = new HashSet<>();
    int num = 0;

    if(g == null || v == null)
        return 0;

    // no loop, call DFS method and it will call itself recursively
    // and it will call the get neighbors()    
    if(!known.contains(v)) {
        num++;
        DFS(g, v, known);
    }
    return known.size();
}

为什么我使用 DFS 得到的连接组件比我的图形的实际连接组件少？

Why am I getting lesser connected components than actual for my graph using DFS?

java

algorithm

graph

depth-first-search