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

Question

我正在尝试实现一个简单的Dfs路径查找问题，在该问题中，我必须打印遇到的第一个路径，如果找不到路径，则什么也不打印。
我能够使用Recursion做到这一点，但是在迭代版本上遇到了麻烦。
这是我的代码:

#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上发现的一些东西
如 map
另外，获得与递归顺序相同的路径。我以rev顺序将子级插入堆栈。
这是问题语句

Given an undirected graph G(V, E) and two vertices v1 and v2(as integers),
find and print the path from v1 to v2 (if exists).
Print nothing if there is no path between v1 and v2.
Find the path using DFS and print the first path that you encountered.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1.
E is the number of edges present in graph G.

Print the path in reverse order. That is, print v2 first, then intermediate vertices and v1 at last.

输入架构:

Line 1: Two Integers V and E (separated by space)
Next E lines: Two integers a and b, denoting that there exists an edge between vertex a and vertex b (separated by space)
Line (E+2): Two integers v1 and v2 (separated by space)

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

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中，则将它们标记为已处理，而将来只有它们将排入以便将来处理。对不履行契约(Contract)的收藏进行操作几乎总是一个坏主意。