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

问题描述 投票:1回答:2

我设法使用递归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;
        }

    }
}

是否有任何算法详细说明要遵循的程序。我很清楚使用给定的here或建议的here的BFS算法找到最短路径。我最初对这种想法为何适用于BFS的直觉是,遍历是逐层进行的,每个子层中有多个子代共享同一父代,因此仅通过跟随父代节点就很容易回溯。在迭代dfs中,情况并非如此。有人可以阐明如何进行吗?有没有经过验证的算法可以解决这种情况。谢谢。

c++ graph depth-first-search breadth-first-search
2个回答
0
投票

对我来说,你要问的是什么还不是很清楚...

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

如果您询问哪种算法比DFS方法更好,则很难回答,因为它始终取决于给定的问题。如果您想找到节点之间的最佳路径,请选择基于BFS的路径(例如Dijkstra algorithm),因为与DFS相比,它在未加权图中的效果最佳(顺便说一句,A *不会成功,因为没有权重)而且没有花哨的试探法,它只会崩溃为DFS)。如果您对该主题更感兴趣,则可以在this丛书系列中找到有关可以采取哪些技巧来优化寻路的更多信息。

最后但并非最不重要的一点,也尝试一下heuristics。也许无需进行详尽的搜索即可找到问题的解决方案。


0
投票

这里是一个示例,说明即使进行了一些优化,深度优先搜索也可能不是一个好主意。 (这几乎总是一个坏主意,但是插图并没有那么做。)

© www.soinside.com 2019 - 2024. All rights reserved.