递归深度优先搜索功能不起作用

Question

这是我试过的代码。

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);
}

只是访问node1的adj向量中的节点。我不明白为什么要这样做。我得到的输出是 A、B、C、D，这意味着 DFS(node2) 应该被调用但它没有访问它的 adj 向量中的节点。如果我从 main() 调用 DFS(node2)，它会将 D E F 作为输出。你能解释一下为什么这段代码不起作用以及我该如何修复它吗？

Answer 1

如果调试代码，您会发现node2 和node4 的adj 值不正确。因为您以错误的顺序分配了它们。最好为 adj 向量使用指针或引用，这样顺序就不再重要了。

Answer 2

已经建议您应该在节点的邻接向量中使用指向节点的指针，但是您必须维护图外节点的生命周期，并且您可以预期图外节点的变化.

您也可以保持节点不变，然后直接在图中的节点上工作。

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);

递归深度优先搜索功能不起作用

Recursive depth first search function is not working

c++

depth-first-search