DFS遍历时在每个节点上调用自定义函数

Question

我想知道编写可适用于解决不同问题（在 C++ 中）的 DFS 遍历的最优雅方法是什么。

我想传递一个函数指针和一个 void * 到我的函数，让用户传递一个将在每个节点上使用的回调。

这是我的：

traversals.hpp

typedef std::shared_ptr<struct Node> NodePtr;
typedef std::vector<NodePtr> NodeVector;

struct Node {
    int id{0};
    NodeVector children;
};

bool NodeIsInVector(NodePtr node, NodeVector node_vector);

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata)=nullptr, void * userdata=nullptr);

traversals.cpp

bool NodeIsInVector(NodePtr node, NodeVector node_vector){
    auto result = std::find(node_vector.begin(), node_vector.end(), node);
    return result != node_vector.end();
}

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata), void * userdata){
    static NodeVector visited;

    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        if (callback){
            callback(node, userdata);
        }
    }

    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            DFS(n, callback, userdata);
        }
    }
}

Driver代码

这里的回调只计算节点和增量以及整数。假设 root 是一个 Node 指针，并且定义了一棵树。树有7个节点，所以遍历后count的值预计为7

int count = 0;
DFS(root, [](NodePtr node, void * count){ ++*(int*)count; }, (void*) &count);
std::cout << "DFS count: there are " << count << " nodes.\n";

但是输出是： DFS count: there are 0 nodes. 回调被调用（通过输出到 stdout 进行验证）。问题是 userdata 变量没有得到更新。

我的问题是：

这是实现我想要的目标的有效方法吗？有没有更好的方法？
我会犯什么错误？

Answer 1

我认为您的代码的问题在于您 return 如果节点在调用回调之前没有子节点。这将导致只有父节点调用回调。

我会完全删除 is children empty 检查。如果一个节点没有子节点，for循环将不会执行。

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata), void * userdata){
    static NodeVector visited;

    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        if (callback){
            callback(node, userdata);
        }
    }

    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            DFS(n, callback, userdata);
        }
    }
}

Answer 2

如果我错了请纠正我，但我怀疑问题是由于 DFS 中定义的 static 变量引起的。

我在问题中没有提及 DFS 是使用不同的回调调用的，该回调在使用增加的回调调用之前没有增加计数变量。我虽然这与我的问题无关。

在函数中声明静态变量会不会导致回调函数在第二次调用时不被替换？

以下版本按预期运行。我还用 std::function 替换了函数指针，反映了评论中提出的一些建议，但更重要的是，我创建了一个包装器来声明 visited NodeVector，这使我可以没有任何 static 声明。

void DFS(NodePtr &node, std::function<void(NodePtr)> callback){
    NodeVector visited;
    _DFS(node, callback, visited);
}

void _DFS(NodePtr &node, std::function<void(NodePtr)> callback, NodeVector& visited){
    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        callback(node);
    } else {
        for(auto item : visited){
            std::cout<<item->id << " ";
        }
        std::cout << "\n";
    }
    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            _DFS(n, callback, visited);
        }
    }
}

和驱动代码：

int count = 0;
DFS(root, [&count](NodePtr node) mutable { ++count; });
std::cout << "DFS count: there are " << count << " nodes.\n";

产生：

DFS count: there are 7 nodes

请注意，使用 static NodeVector visited; 而不是包装器策略的相同功能无法按预期工作。我仍然不是 100% 清楚为什么。

DFS遍历时在每个节点上调用自定义函数

Calling a custom function on each node during DFS traversal

c++

graph

depth-first-search

traversal

traversals.hpp

traversals.cpp

Driver代码