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