我正在为使用递归的图形的 DFS 遍历编写一个简单的代码。这有什么问题？ [关闭]

Question

我的代码是这样的。我将输入作为其中有边的节点。它是无向图。我将图存储为邻接表并使用访问过的地图来映射已访问过的节点

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

class Graph
{

public:
    map<int, list<int>> adj;

    void addEdge(int u, int v)
    {

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void DFS(int node)
    {

        map<int, bool> visited;
        cout << node;
        visited[node] = true;
        for (auto i : adj[node])
        {
            if (!visited[i])
            {
                DFS(i);
            }
        }
    }
};
int main()
{
    Graph g;

    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(2, 5);
    g.addEdge(3, 5);
    g.addEdge(4, 3);
    g.addEdge(5, 4);

    g.DFS(1);
    return 0;
}

当我编译这个时，它给出了 121212 的递归输出......

Answer 1

您需要跟踪已访问但尚未探索所有外边的节点。最好使用堆栈来完成。

这里是算法：

            1 Start by putting one of the graph's vertices on top of a stack.
            2 Take the top vertex of the stack and add it to the visited list.
            3 Add adjacent vertices which aren't in the visited list to the top of the stack.
            4 Keep repeating steps 2 and 3 until the stack is empty.
 

---

附加说明：您跟踪访问节点的代码可以正常工作，但对于这项工作来说太复杂了。你所需要的只是一个向量：

std::vector<bool> visited( adj.size(), false );

访问节点 i

visited[i] = false;

检查J是否被访问过

if( visited[j] ) ...
 

无论图中有多少节点，这都在恒定时间内工作，并且比通过数千个节点的映射进行二进制搜索要快得多。