Search code examples
javaalgorithmbreadth-first-searchdirected-graphadjacency-matrix

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


enter image description here enter image description here

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)


Solution

  • 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).