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

Question

我正在尝试找到一种方法countVertices()该方法需要使用DFS返回给定顶点的同一连接组件中的顶点数。

我

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

我的方法代码如下所示：

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();
}