C ++ Depth First Search (DFS) показывает неверный результат

Question

Я пытаюсь реализовать поиск в глубину (DFS) в C ++, но он не показывает правильный вывод.Уже посещенные узлы не должны появляться снова, но они появляются, и не раз, я действительно не понимаю, почему это происходит.

Код:

#include <iostream>
#include <vector>

using namespace std;

struct Node{
    int id;
    vector<Node> adj;
    bool visited;
};

struct Graph{
    vector<Node> nodes;
};

void addEdge(Graph& g,int ida,int idb){
    g.nodes[ida].adj.push_back(g.nodes[idb]);
    g.nodes[idb].adj.push_back(g.nodes[ida]);
}

void dfs(Graph& g,Node& n){
    n.visited = true;
    cout << n.id << endl;
    for (int i = 0;i < n.adj.size();i++)
        if (!n.adj[i].visited)
            dfs(g,n.adj[i]);
}

void init(Graph& g,int n){
    g.nodes.clear();
    for (int i = 0;i < n;i++){
        Node v;
        v.id = i;
        v.visited = false;
        g.nodes.push_back(v);
    }
}

int main()
{
    Graph g;
    init(g,5);
    addEdge(g,1,3);
    addEdge(g,0,4);
    addEdge(g,1,4);
    addEdge(g,2,1);
    for (int i = 0;i < g.nodes.size();i++)
        dfs(g,g.nodes[i]);
    return 0;
}

То, что я думаю, должно бытьвыход

0 4 1 3 2

Фактический выход

0 4 1 3 4 0 4 2 1 3 4 0 4 2 1 3 4 0 4 3 1 3 4 0 4 1 3 4 0 4

Answer 1

Вам нужно только вызвать dfs один раз, чтобы получить желаемый результат, по длине.Вы называете это 5x, поэтому вывод такой длинный.

Answer 2

Вы сохраняете свой список смежности с Node вместо указателей на узлы.

vector<Node*> adj;

g.nodes[ida].adj.push_back(&(g.nodes[idb]));
g.nodes[idb].adj.push_back(&(g.nodes[ida]));

Конечно, это работает, только если вы выполняете смежность после нажатия всех узлов на графике.

Когда вы проверяете флаг в списке смежности !n.adj[i].visited, это делается на копии узла, а не того, который вы уже посетили.

Кроме того, вы должны правильно инициализировать visited.