Counting vertices in a graph through a recursive method, returning an integer in the end

user_18929997 0
Viewed 101

I'm currently doing an assignment in which I need to use a graph with connected vertices in an array.

I need to count each node in the graph, and have attempted to do it recursively.

public int getAmountOfNodes(Node node, int countFrom){
    for (Node n : node.children) {
        if (n != null) {
            countFrom++;
            getAmountOfNodes(n, countFrom);
        }
    }
    return countFrom;
}

This is what I've attempted so far, but it's not quite working out the way I was hoping. I've attempted to debug the code, and it seems the counting works the way it's supposed to (counting each node that isn't null).

Problem seems to be that when the recursive stack ends, say that countFrom has hit 5, and the method returns 5, the next recursive call in the stack doesn't "remember this", and returns the amount it had counted up to before, say 4. This means that the final returned integer is only the amount that the first recursive call had counted to, that is, the amount of children the very first node has.

I've been trying to google around and haven't been able to find an answer I could use. I'm still learning recursion, so please excuse any dumb mistakes that might be right in front of me.

depth-first-search graph recursion algorithm java
3 Answers

the next recursive call in the stack doesn't "remember this", and returns the amount it had counted up to before

Because you are not using the value returned by the call:

getAmountOfNodes(n, countFrom);

Each call creates a new branch of recursion, but the value returned from the method remains unaffected.

There's a few more minor issues:

  • You don't need the second argument int countFrom, simply return the accumulated value instead of maintaining a redundant parameter.
  • The way how you are addressing counting for each "parent" node (line countFrom++;) isn't self-explanatory and can be done in a more clear and intuitive way. Also, your approach implies that with a very first call you have to pass the value of 1, which can lead to mistake if you forget it.
  • A good practice is to disallow nullable values where it is possible, it makes your logic simple and life easier. You can't avoid null values when you're modeling such data structures as linked list, but in the graph a node should contain an empty collection instead if it has no children, but not a collection of null values. It's justifiable only if nullable values are a part of your assignment.
  • This approach is only sufficient for traversing the graph represented by a so-called N-ary tree. But it isn't suitable for cyclic graphs and disjointed graphs. In both cases, you will need to maintain a HashSet of visited nodes, which you can pass to the method as a parameter and update with each explored node.

That's how your method could be reimplemented in a cleaner way:

public int getAmountOfNodes(Node node) {
    if (child == null) return 0; // base case - no node, therefore return value is 0

    int count = 1; // we sould count THIS node
    for (Node child : node.children) {
        count += getAmountOfNodes(child); // adding the count for every child
    }
    return count;
}
user_179499450

In your code, you're simply passing the countFrom primitive int to every call and never bother to updated its value from the last call. This is why your last iteration doesn't make it to the final result and this explains why in your example you get 4 instead of 5.

When designing recursive methods, you should always consider all your base cases and recursive cases. In this example, your base case (a scenario which ends your recursive iteration) could be n == null while your recursive steps (actions that make you progress towards your goal) are the increment of your count variable and its update after the recursive calls.

Your code should look like something like this.

public int getAmountOfNodes(Node n, int countFrom){
    
    //Checking whether n actually represents a node or not; if it's not then the number of nodes stays the same
    if (n == null){
        return countFrom;
    }

    //If n represents a node then the numer of nodes must be incremented
    countFrom++;

    //Aplying the previous logic to each children of n
    for (Node child: n.children) {
        //Doesn't matter whether child is null or not; if child is null then countFrom stays the same 
        //otherwise it's incremented according to the number of nodes met by the recursive call
        countFrom = getAmountOfNodes(child, countFrom);
    }

    return countFrom;
}
user_44156250

You can use breadth first search, which is implemented without recursive calls. Each child node n of a current node is added to a FIFO queue if it is being visited for the first time. After the current node’s children have been examined, another current node is removed from the queue.

user_78365590
Related