Recursive depth first search function is not working

Question

Here is the code that I tried.

class Node 
{
    public:
        char value;
        bool visited;
        vector<Node> adj;
        Node(char v)
        {
            value = v;
            visited = false;
        }
};
void DFS(Node node)
{
    node.visited = true;
    cout << node.value << endl;
    int i;
    for(auto i=node.adj.begin(); i != node.adj.end(); ++i)
    {
        if(!(*i).visited)
        {
            DFS(*i);
        }
    }
}
int main()
{
    Node node1('A');
    Node node2('B');
    Node node3('C');
    Node node4('D');
    Node node5('E');
    Node node6('F');
    Node node7('G');
    node1.adj.push_back(node2);
    node1.adj.push_back(node3);
    node1.adj.push_back(node4);
    node2.adj.push_back(node5);
    node2.adj.push_back(node6);
    node4.adj.push_back(node7);
    DFS(node1);
}

It is only visiting the nodes in the adj vector of node1. I don't understand why it is doing so. The output I am getting is A,B,C,D which means that DFS(node2) should've been called but it is not visiting the nodes in it's adj vector. If I call DFS(node2) from main() it is giving D E F as output. Can you explain why this code is not working and how I could fix it?

Answer 1

It is already suggested that you should use pointers to nodes in the adjacency vector of the node, but then you have to maintain the lifetime of the nodes outside of your graph and you can expect changes on the nodes outside the graph.

You can also keep your node as it is and then work directly on the nodes in the graph.

Node node1('A');
node1.adj.push_back(Node('B'));
node1.adj.push_back(Node('C'));
node1.adj.push_back(Node('D'));
node1.adj.push_back(node4);
Node& node2 = node1.adj.front();
node2.adj.push_back(Node('E'));
node2.adj.push_back(Node('F'));
Node& node4 = node1.adj.back();
node4.adj.push_back(Node('G'));
DFS(node1);