Need help getting to nth level of an adjacency matrix (graph) using a breadth-first search (Java)

Question

public int bfs(int maxDepth){
        int src = 2;
        int dest = 2;
        int i;
        int depth = 0;
        int countPaths = 0;
        int element;

        queue.add(src);

        while(!queue.isEmpty() && depth <= maxDepth)
        {   
            element = queue.remove();
            i = 0;

            while(i < 5) 
            {   
                if(arr[element][i] > 0)
                {
                    queue.add(i);

                    if(i == dest)
                        countPaths++;
                }       
                i++;
            }
        }

        queue.clear();
        return countPaths;
    }

Hello!! Given a source and a destination, I need to find a path. My BFS algorithm is working fine as far as traversing the graph goes. My problem is getting it to stop when I want it to. I took out where I was incrementing depth so I don't look like a complete idiot. I hope someone can help. Essentially I want to know how I can keep track of the current depth. Thank you!

Example:

Find the # of paths from C to C with a maximum number of 3 stops. The answer is two paths:

C -> D -> C (2 stops)

C -> E -> B -> C (3 stops)

Example 2: Find the # of paths from A to C with a maximum number of 3 stops. The answer is three paths.

A -> B -> C (2 stops)

A -> D -> C (2 stops)

A -> E -> B -> C -> (3 stops)

Liber

Hi, it does not look like you could just use one variable depth to measure how deep you are going. Have you considered using another queue to keep track of depth? let's call it depth_queue. Each element in depth_queue is the depth of an element in queue. The way I see it, there are two strategies to detect when to terminate: (1) the head of depth_queue is more than maxDepth (not sure if this is the case, you need to think on it) (2) this is more assuring: go through the entire depth_queue if every element is more than maxDepth, then you can terminate – Hershelhershell

Answer 1

Q: Essentially I want to know how I can keep track of the current depth.

One solution is to create a wrapper class with an additional field, depth, as @svs explained in his answer. But, there is a neat trick which avoids creating a wrapper class and it is quite simpler:

queue.add(src);
while(!queue.isEmpty())
{
     int size = queue.size();
     for(int i=0; i<size; i++)
     {
     .. //do processing for the current depth
     }
}

In the for loop do whatever you intend to do with nodes of that level, including putting new elements in a queue (that would be nodes with depth equal current_depth + 1). Iterating only queue.size() times in for loop will guarantee that you process only the nodes of the current level, and while loop will guarantee that all levels will be processed (or just some of them, if you extend the condition for stopping the loop).

Inness

Answer 2

Since every node should be associated with its depth when you perform the bfs you could create a class in which you store the node and the depth (and the parent if you want to print the path):

package stackoverflow;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class BFSTest {
    public static class BFSNode {
        public int node, depth;
        public BFSNode parent;

        public BFSNode(int node) {
            this.node = node;
            this.depth = 0;
            this.parent = null;
        }

        public BFSNode(int node, BFSNode parent) {
            this.node = node;
            this.depth = parent.depth+1;
            this.parent = parent;
        }
    }

    ArrayDeque<BFSNode> queue;
    int[][] arr;

    public BFSTest() {
        queue = new ArrayDeque<BFSNode>();
        arr = new int[5][5];
        arr[0][1] = arr[0][3] = arr[0][4] = 1;
        arr[1][2] = 1;
        arr[2][3] = arr[2][4] = 1;
        arr[3][2] = arr[3][4] = 1;
        arr[4][1] = 1;
    }

    public int bfs(int src, int dest, int maxDepth){
        int i;
        int countPaths = 0;
        BFSNode element;

        queue.add(new BFSNode(src));

        while(!queue.isEmpty())
        {   
            element = queue.poll();
            if (element.depth > maxDepth)
                break;
            i = 0;

            while(i < 5) 
            {   
                if(arr[element.node][i] > 0)
                {
                    if(i == dest && element.depth +1 <= maxDepth) {
                        BFSNode tmp = element;
                        List<Integer> path = new ArrayList<Integer>();
                        path.add(dest);
                        while (tmp != null) {
                            path.add(tmp.node);
                            tmp = tmp.parent;
                        }
                        for (int j = path.size() - 1; j >= 0; j--) {
                            System.out.print(path.get(j) + " ");
                        }
                        System.out.println();
                        countPaths++;
                    }

                    queue.add(new BFSNode(i, element));

                }       
                i++;
            }
        }

        queue.clear();
        return countPaths;
    }

    public static void main(String[] args) {
        BFSTest test = new BFSTest();
        System.out.println(test.bfs(2, 2, 3));
        System.out.println(test.bfs(0, 2, 3));
    }

}

You get

//src = 2, dest=2
2 3 2   //path 1
2 4 1 2 //path 2
2       //total
//src=0. dest=2
0 1 2   //path 1
0 3 2   //path 2
0 4 1 2 //path 3
3       //total

Jillene