Почему я получаю меньше подключенных компонентов, чем актуально для моего графика с использованием 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
}

Я не могу понять, что я делаю не так? Буду признателен за любую помощь.

Edit:

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 ребра, которые принадлежат одному и тому же компоненту. х - единственная изолированная вершина. Следовательно, правильный выход - это 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();
}