如何修改 DFS 算法，让它找到每条路径，而不是只找到 1 条路径

Question

我有一个适当的迭代 DFS 搜索来查找迷宫中两个块之间的路径。然而，我的目标是找到它们之间的每条简单路线（没有重复的块）。我怎样才能实现这个目标？我提供的解决方案仅找到一条路线。 我的要求是：

1. 我不能使用任何外部库或相关函数中的任何容器，我应该自己实现它
2. 我的解决方案必须使用DFS并且它必须是非递归的

Stack* paths = new Stack[1000]; //Array of Stacks to Store the Founded paths, Assuming there are no more than 1000 Paths
    int pathCount = 0;

    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++ ){
            blockArr[col*i+j]->visited= false;
        }
    }
    Block* start = blockArr[col*startRow+startCol];
    Block* end = blockArr[col*endRow+endCol];
    Stack pathStack;
    pathStack.push(start);
    start->visited = true;

    while(!pathStack.isEmpty()){
        Block* curr = pathStack.peek();
        int currnotvisited = 0;
        for(int i = 0; i < curr->adjCount; i++){
            if(!curr->adj[i]->visited){
                currnotvisited++;
            }
        }
        if(currnotvisited == 0){
            pathStack.pop();
        }
        else{
            for(int i = 0; i < curr->adjCount; i++){
                if(!curr->adj[i]->visited){
                    pathStack.push(curr->adj[i]);
                    curr->adj[i]->visited = true;
                    break;
                }
            }
        }
        if(pathStack.peek() == end){
            paths[pathCount] = pathStack;
            pathCount++;
            pathStack.pop();
        }
    }

我正在考虑返回，同时使他们访问的内容为假，但是我如何确保它不会以同样的方式进行？

Answer 1

思考一下基本算法。

算法跟踪图中的节点，直到发生以下情况之一：

1. 找到目标
2. 找到已经接触过的节点或叶节点
3. 耗尽了可跟随的节点

通常如果找到目标就完成了。该函数终止并返回用于查找目标的节点列表。如果节点用完，也会完成。只有条件 2 才会启动回溯以继续 DFS 搜索。

但是要求你找到每个可以找到目标的节点列表。

您已经怀疑您需要多个列表——每条通往目标的路径都需要一个列表。你可以这样想：

• 该函数有它在搜索时创建的列表
• 每次找到目标时，您都需要函数列表的副本

现在您需要考虑在找到目标时如何修改上述行为。如果您找到了目标，您想要：

• 将通向目标的节点列表的副本追加到列表列表中
• 继续DFS搜索，就好像你没有找到目标一样（你可以像找到叶子节点一样对待它）

换句话说，您已将函数的终止条件更改为仅条件 3 — 耗尽节点。