c++ - 为图中的节点定义 "visited"变量

Question

我已经编写了图表代码，您可以在以下链接中看到。

Calculating outdegree of a node in Graph

现在，我需要为其编写 BFS 和 DFS。为此，我需要有一个变量“visited”来定义节点是否被访问。我意识到我必须将这个变量包含在

class Graph{

vector<pair<pair<**bool**,T>, list<T2> > > node;

}

这里bool是节点是否被访问的条件。为此，我必须对整个代码进行更改。有没有其他方法，我可以在不对代码做太多修改的情况下包含变量？

好的，我知道了。它很简单。不好意思问这样的问题。我可以定义另一个

vector<bool> visited 

在 BFS 函数中。我将在编写函数后更新代码。再次抱歉。

Answer 1

在类内部放置访问标记不是个好主意 - 因为你只能做一次 - 之后你必须在第二次开始算法之前重置所有内容。作为替代方案，您有 2 个选择:

• 使用一些数字代替 bool - 唯一标识应用算法的数量，因此在测试是否访问节点之前，您必须增加全局应用计数器并检查节点版本是否严格小于全局应用计数器。

• 您可以声明跟踪节点 ID 的散列映射(对于 c++11，请使用 unordered_map )(作为一个不好但可行的示例，使用指向节点的指针)。因此，如果节点的 id 存在于 hash-map 中，则节点已被访问。应用算法后，只需销毁 map

我更喜欢第二种情况。

附注是的，@a_guest 的评论 - 是正确的 - 创建你的类节点