使用迭代DFS而不是递归DFS的第一个DFS路径。

Question

我试图实现一个简单的Dfs路径查找问题，在这个问题中，我必须打印我遇到的第一条路径，如果没有找到路径，则什么也不打印。我能够用递归完成这个任务，但是迭代版本有问题。

这是我的代码：

#include <iostream>
#include <stack>
#include <map>
using namespace std;

void PrintDFSpath(int **a, int *visited, int start, int end, int v)
{
    map<int, int> parentMap;
    stack<int> s;
    s.push(start);

    while (!s.empty())
    {
        int currEle = s.top();
        visited[currEle]=1;
        s.pop();
        if (currEle == end)
        {
            break;
        }

        for (int i = v - 1; i >= 0; i--)
        {
            if (a[currEle][i] == 1 && !visited[i] && i != currEle)
            {
                if( !parentMap.count(i) )
                    parentMap[i] = currEle;
                s.push(i);
                visited[i] = 1;
            }
        }
        if (s.empty())
        {
            return;
        }
    }
    int i = end;
    cout<<end<<" ";
    while (i != start)
    {
        cout<<parentMap[i]<<" ";
        i = parentMap[i];
    }
}

int main()
{
    int v, e;
    cin >> v >> e;
    int **a = new int *[v];

    for (int i = 0; i < v; i++)
    {
        a[i] = new int[v];
        for (int j = 0; j < v; j++)
            a[i][j] = 0;
    }
    int x, y;
    for (int i = 0; i < e; i++)
    {
        cin >> x >> y;
        a[x][y] = 1;
        a[y][x] = 1;
    }

    int v1, v2;
    cin >> v1 >> v2;

    int *visited = new int[v];
    for (int j = 0; j < v; j++)
        visited[j] = 0;

    PrintDFSpath(a, visited, v1, v2, v);
    return 0;
}

我这里用的是邻接矩阵。

我已经实现了一些我在StackOverflow上找到的东西，比如地图

此外，获取的路径与递归顺序的路径相同，我是按rev顺序将子级插入堆栈。

下面是问题语句

给出了一个无向图G(V，E)和两个顶点v1和v2(作为整数)，

查找并打印从v1到v2的路径(如果存在的话)。

如果v1和v2之间没有路径，则不打印任何内容。

使用DFS查找路径并打印遇到的第一个路径。

V是图G中存在的顶点数，顶点数从0到V-1。

E是图G中的边数。

按反向顺序打印路径。即，首先打印v2，然后打印中间顶点和v1。

输入模式：

第1行:两个整数V和E(用空间分隔)

接下来的E行:两个整数a和b，表示顶点a和顶点b之间存在一条边(用空间分隔)。

行(E+2)：两个整数v1和v2 (用空格分隔)

我认为这个问题来自以下声明。

if (currEle == end)
{
    break;
}

但我想不出怎么纠正它。请给我点建议

测试用例：

7 8

0 1

1 2

4 5

6 5

1 6

1 2

2 3

0 3

0 3

产出:3 2 1 0

Answer 1

基本上，通过从内部for循环中删除以下代码行，可以得到解决测试用例示例的代码：

if( !parentMap.count(i) )

和

visited[i] = 1;

在您的代码中，parentMap注册从当前处理的元素到其子元素的路径的第一次出现。为了模仿递归的DFS行为，parentMap应该注册从当前元素到其父元素的路径。通过在遇到尚未被访问的新路径时重写现有的map元素，可以获得所需的数据。

visited集合应该包含已经处理过的元素。如果在内部visited循环中将子元素添加到for中，则将它们标记为已处理，当它们只是在将来某个时候被排队的处理时。在不履行合同的集合上操作几乎总是一个坏主意。