时间戳

首页 > 解决方案 > 我正在尝试使用 STL 堆栈执行 DFS，但它给出了意想不到的结果

c++ - 我正在尝试使用 STL 堆栈执行 DFS，但它给出了意想不到的结果

问题描述

这是我的 DFS 代码，它应该提供如下输出：

以下是深度优先遍历：0 1 3 2 4

但它给出了输出：

以下是深度优先遍历：0 2 3 4 1 1 1

我没有再次访问访问过的元素，但它仍然无法正常工作。

#include<bits/stdc++.h>
using namespace std;

void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void DFS(vector<int> adj[], int V, int s)
{
    stack<int> st;
    bool visited[V];
    for(int i=0; i<V;i++)
        visited[i] = false;

    visited[s] = true;
    st.push(s);
    while(st.empty()==false)
    {
        int n=st.top();
        st.pop();
        visited[n] =true;
        cout<<n<<" ";
        for(int v:adj[n])
        {
            if(visited[v]==false)
                 st.push(v);
        }
    }
}

int main()
{
    int V=5;
    vector<int> adj[V];
    addEdge(adj,0,1); 
    addEdge(adj,0,2); 
    addEdge(adj,2,3); 
    addEdge(adj,1,3); 
    addEdge(adj,1,4);
    addEdge(adj,3,4);

    cout << "Following is Depth First Traversal: "<< endl; 
    DFS(adj,V,0); 

    return 0; 
}

标签： c++algorithmgraphdepth-first-search

解决方案

除非有充分的理由使用显式堆栈，否则我建议使用递归（隐式堆栈）。但是，我将修复它，对您的代码进行最少的更改。

有 3 件事要解决，我在下面留下了评论。

void DFS(vector<int> adj[], int V, int s)
{
    stack<int> st;
    vector<bool> visited(V, false); // 1. Don't use VLA as it is not standard

    // 2. Remove redundant first element visit marking
    st.push(s);
    while(st.empty()==false)
    {
        int n=st.top();
        st.pop();
        // 2. Check if visited since some elements may have added multiple times
        //    (Some are pushed in the stack many times but not never visited yet)
        if (visited[n]) 
            continue;
        visited[n] =true;
        cout<<n<<" ";
        // 3. Reverse the order of iteration
        for(auto v = adj[n].rbegin(); v != adj[n].rend(); ++v)
        {
            if(visited[*v]==false)
                 st.push(*v);
        }
    }
}

https://godbolt.org/z/Kz16GT

添加更多关于否的信息。3 - 实际上0 2 3 4 1也是一个有效的 DFS 订单。但adj[n]由于 Stack 的性质，它从相反的顺序遍历。所以反向迭代会使迭代结果为0 1 3 2 4。

推荐阅读