使用迭代 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;
}

我这里使用的是邻接矩阵。

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

此外，获取与递归顺序相同的路径我将子项按 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 应该注册从当前元素到其父元素的路径。通过在遇到尚未访问的新路径时覆盖现有地图元素，您可以获得所需的数据。

visited 集合应包含您已经处理的元素。如果您在内部 for 循环中将子项添加到 visited，则当它们仅 enqueued 以便在将来的某个时间点进行处理时，您将它们标记为已处理。对不履行合同的集合进行操作几乎总是一个坏主意。

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

The first DFS path using a itertaive DFS rather than a recursive one

c++

graph

path-finding

depth-first-search

undirected-graph