下面是一个python实现:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

def bfs(paths, goal):
    if not paths:
        raise StopIteration

    new_paths = []
    for path in paths:
        if path[-1] == goal:
            yield path

        last = path[-1]
        for neighbor in graph[last]:
            if neighbor not in path:
                new_paths.append(path + [neighbor])
    yield from bfs(new_paths, goal)


for path in bfs([['A']], 'D'):
    print(path)

我认为这可以使用指针来完成，而不使用任何队列。

基本上我们在任何地方都维护两个指针，一个指向父结点，另一个指向待处理的子结点(链接列表指向所有已处理的子结点)

现在你只需分配子进程的指针&当父进程处理完成时，你只需让子进程成为父进程进行下一层的处理

以下是我的代码:

//Tree Node
struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
    

/ / Algorightm:

    void LevelTraverse(Node* parent,Node* chidstart,Node* childend ){
        if(!parent && !chidstart) return;  // we processed everything
        
        if(!parent && chidstart){ //finished processing last level
            parent=chidstart;chidstart=childend=NULL; // assgin child to parent for processing next level
            LevelTraverse(parent,chidstart,childend);
        }else if(parent && !chidstart){ // This is new level first node tobe processed
            Node* temp=parent; parent=parent->next;
            if(temp->left) { childend=chidstart=temp->left; }
            if(chidstart){
                if(temp->right) { childend->next=temp->right; childend=temp->right; }
            }else{
                if(temp->right) { childend=chidstart=temp->right; }
            }
            LevelTraverse(parent,chidstart,childend);
        }else if(parent && chidstart){ //we are in mid of some level processing
            Node* temp=parent; parent=parent->next;
            if(temp->left) { childend->next=temp->left; childend=temp->left; }
            if(temp->right) { childend->next=temp->right; childend=temp->right; }
            LevelTraverse(parent,chidstart,childend);
        }
    }

//驱动代码:

    Node* connect(Node* root) {
        if(!root) return NULL;
        Node* parent; Node* childs, *childe; parent=childs=childe=NULL;
        parent=root;
        LevelTraverse(parent, childs, childe);
        return root;
    }

下面的方法使用DFS算法来获取特定深度的所有节点——这与对该级别进行BFS相同。如果您找到树的深度，并对所有级别执行此操作，结果将与BFS相同。

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

找到树的深度是小菜一碟:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

下面使用Haskell对我来说似乎很自然。在树的各个层次上递归迭代(这里我将名字收集到一个大的有序字符串中，以显示树的路径):

data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
    where levelRecurser level = if length level == 0
                                then ""
                                else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])

以下是我的完全递归实现的双向图的广度优先搜索的代码，而不使用循环和队列。

public class Graph { public int V; public LinkedList<Integer> adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList<>(); } void addEdge(int v,int w) { adj[v].add(w); adj[w].add(v); } public LinkedList<Integer> getAdjVerted(int vertex) { return adj[vertex]; } public String toString() { String s = ""; for (int i=0;i<adj.length;i++) { s = s +"\n"+i +"-->"+ adj[i] ; } return s; } } //BFS IMPLEMENTATION public static void recursiveBFS(Graph graph, int vertex,boolean visited[], boolean isAdjPrinted[]) { if (!visited[vertex]) { System.out.print(vertex +" "); visited[vertex] = true; } if(!isAdjPrinted[vertex]) { isAdjPrinted[vertex] = true; List<Integer> adjList = graph.getAdjVerted(vertex); printAdjecent(graph, adjList, visited, 0,isAdjPrinted); } } public static void recursiveBFS(Graph graph, List<Integer> vertexList, boolean visited[], int i, boolean isAdjPrinted[]) { if (i < vertexList.size()) { recursiveBFS(graph, vertexList.get(i), visited, isAdjPrinted); recursiveBFS(graph, vertexList, visited, i+1, isAdjPrinted); } } public static void printAdjecent(Graph graph, List<Integer> list, boolean visited[], int i, boolean isAdjPrinted[]) { if (i < list.size()) { if (!visited[list.get(i)]) { System.out.print(list.get(i)+" "); visited[list.get(i)] = true; } printAdjecent(graph, list, visited, i+1, isAdjPrinted); } else { recursiveBFS(graph, list, visited, 0, isAdjPrinted); } }

我已经用c++做了一个程序，它是在联合和不联合图工作。

    #include <queue>
#include "iostream"
#include "vector"
#include "queue"

using namespace std;

struct Edge {
    int source,destination;
};

class Graph{
    int V;
    vector<vector<int>> adjList;
public:

    Graph(vector<Edge> edges,int V){
        this->V = V;
        adjList.resize(V);
        for(auto i : edges){
            adjList[i.source].push_back(i.destination);
            //     adjList[i.destination].push_back(i.source);
        }
    }
    void BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q);
    void BFSRecursivelyJointandDisjointGraph(int s);
    void printGraph();


};

void Graph :: printGraph()
{
    for (int i = 0; i < this->adjList.size(); i++)
    {
        cout << i << " -- ";
        for (int v : this->adjList[i])
            cout <<"->"<< v << " ";
        cout << endl;
    }
}


void Graph ::BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q) {
    if (q.empty())
        return;
    int v = q.front();
    q.pop();
    cout << v <<" ";
    for (int u : this->adjList[v])
    {
        if (!discovered[u])
        {
            discovered[u] = true;
            q.push(u);
        }
    }
    BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);

}

void Graph ::BFSRecursivelyJointandDisjointGraph(int s) {
    vector<bool> discovered(V, false);
    queue<int> q;

    for (int i = s; i < V; i++) {
        if (discovered[i] == false)
        {
            discovered[i] = true;
            q.push(i);
            BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);
        }
    }
}

int main()
{

    vector<Edge> edges =
            {
                    {0, 1}, {0, 2}, {1, 2}, {2, 0}, {2,3},{3,3}
            };

    int V = 4;
    Graph graph(edges, V);
 //   graph.printGraph();
    graph.BFSRecursivelyJointandDisjointGraph(2);
    cout << "\n";




    edges = {
            {0,4},{1,2},{1,3},{1,4},{2,3},{3,4}
    };

    Graph graph2(edges,5);

    graph2.BFSRecursivelyJointandDisjointGraph(0);
    return 0;
}