c++ - 使用迭代深度优先搜索算法的未加权图的最短路径

Question

我已经设法使用递归 dfs 找到未加权图的最短路径。这是这样的尝试。

void dfsHelper(graph*& g, int start,int end, bool*& visited, int& min, int i) {
    visited[start] = true;
    i = i + 1;
    if (start == end) {
        if (i<=min) { min = i; }
    }
    node* current = g->adj[start];
    while (current != NULL) {
        if (!visited[current->dest]) {
            dfsHelper(g, current->dest,end, visited,min,i);
        }
        current = current->next;
    }
    visited[start] = false;
}

但是对于像这样的 dfs 迭代算法，我应该如何处理。

void dfsItr(graph*& g, int start, int end) {
    bool* isVisited = new bool[g->numVertex];
    for (int i = 0; i < g->numVertex; ++i) {
        isVisited[i] = false;
    }
    stack<int> st;
    isVisited[start] = true;
    st.push(start);

    while (!st.empty()) {
        start = st.top();
        cout << start << " ";
        st.pop();
        node* current = g->adj[start];
        while (current != NULL) {
            if (!isVisited[current->dest]) {
                isVisited[current->dest] = true;
                st.push(current->dest);
                if (current->dest == end) {
                    cout << current->dest << endl; 
                }
            }
            current = current->next;
        }

    }
}

是否有任何算法详细说明要遵循的过程。我很清楚使用给定的 BFS 算法找到最短路径 here或按照建议here .对于为什么这种想法适用于 BFS，我最初的直觉是遍历是逐层发生的，多个子节点在每一层中共享相同的父节点，因此只需跟随父节点就可以轻松回溯。在迭代 dfs 中，情况并非如此。有人可以阐明如何进行。是否有任何经过验证的算法来解决这种情况。谢谢。

Answer 1

我不太清楚你在问什么......

如果您询问如何优化 DFS 的迭代实现，我在这里要做的一件事是不使用 stack，而是编写自己的具有 LIFO 接口(interface)但进行内存预分配的集合。
其他优化空间是不使用流运算符，因为它们比 printf 慢得多。查看this关于性能的回答部分。另外，一直打印到 STDOUT 真的有意义吗？如果性能是关键，这可能每几次迭代完成一次，因为 IO 操作真的很慢。

如果您要问哪种算法比 DFS 方法更好，那很难回答，因为它总是取决于给定的问题。如果您想找到节点之间的最佳路径，请选择基于 BFS 的路径(例如 Dijkstra algorithm )，因为与 DFS 相比，它在未加权的图形中表现最佳(顺便说一句。A* 不会在这里解决问题，因为没有权重并且没有花哨的启发式算法，它只会崩溃为 DFS)。如果您对此主题更感兴趣，您可以在 this 中找到更多关于优化寻路技巧的信息。丛书。

最后但同样重要的是，给一些heuristics也试试也许没有必要进行详尽的搜索来找到解决问题的方法。