java - 再帰を使用して 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);
   }