是否可以使用遞歸實現BFS？

Question

這裏是我的僞代碼做了BFS算法。

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

} 

我正在努力實現這個使用遞歸。有小費嗎？

我嘗試：

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); 
    } 
} 

但是，這將失敗，因爲當一個頂點有沒有更多的邊緣，它應該回到第一邊緣不其最後？ 卡住了？

任何幫助表示讚賞。

Answer 1

你可以有bfs_recursion()也採取了頂點索引參數，用，比如說，-1表示「處理父母，而不是孩子」：

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); 
    }