Is is possible to implement BFS using recursion?

Question

Here is my algorithm for doing a BFS in pseudo code.

public void bfs_usingQueue() {
    Queue<Vertex> queue = ...
    // 1. visit root node
    ...
    // 2. Put root vertex on queue
    ...
    while(!queue.isEmpty()) {
        // 3. Get the vertex at top of cue 
        // 4. For this vertex, get next unvisited vertex 
        // 5. Is there is an unvisited node for this vertex?
             // 5a. Yes.
             // 5b. Visit it.
             // 5c. Now add it to que. 
        // 6. No there is not one unvisited node for this vertex.
             // 6a. Pop current node from que as it has no other unvisited nodes.
    }

}

I am struggling to implement this using recursion. Any tips?

I try:

private void bfs_recursion() {
    // begin with first vertex
    bfs_recursion(vertexes[0]);
}


private void bfs_recursion(Vertex vertex) {
    // visit first
    visitVertex(vertex);

    // get next unvisitedVertex 
    Vertex unvisitedVertex = ...
    if (unvisitedVertex != null) {
        visitVertex(unvisitedVertex);
        bfs_recursion(vertex);
    } else {
        bfs_recursion(unvisitedVertex);
    }
}

But this will fail as when a vertex has no more edges, it should go back to first edge not its last? Stuck?

Any help appreciated.

score 0 · Answer 1 · answered Mar 30 '13 at 03:11

You could have bfs_recursion() also take the vertex index parameter, with, say, -1 indicating "process the parent, not a child":

private void bfs_recursion(Vertex vertex, int index) {
   if (index==-1) {
      visitVertex(vertex);
      bfs_recursion(vertex, 1);
   } else {
      visitVertex(getChild(index));
      bfs_recursion(vertex+1);
   }

Is is possible to implement BFS using recursion?

1 Answers1