c++ - 在负数节点上实现 bfs

Question

如果节点或顶点在 C++ 中编号为正，我们可以轻松实现广度优先搜索算法。

但是当节点或顶点编号为负时如何处理。

假设一个节点编号为 -200，如果我们分配bool visited[-200] = true or false，那么它将产生运行时错误。

在这种情况下将采用什么方法？

score 0 · Accepted Answer

在处理图形标签时，似乎一种合理的方法是使用属性映射（例如，参见Boost Graph Library。基本思想是通过结构化方法访问节点属性，其中属性的细节实际上是访问的主题到正在使用的具体属性映射。

根据您所说的，您正在使用节点 ID 访问标签。根据 ID 的实际布局，有两种明显不同的方法：

如果节点标签相对密集并且值节点 ID 的范围是已知的，则使用使用偏移量进行适当调整的数组是一种合理的方法。也就是说，您将使用像label[nodeID - minNodeID].
如果节点标签是随机分布的，您将使用一个关联容器，并将节点 ID 作为容器的键。

如果您可以控制节点表示的布局，您可能应该考虑将标签存储在节点中，尤其是在节点 ID 是随机分布的情况下。

score 0 · Accepted Answer

“如果节点编号为负数” ~> 如果您需要每个节点都有一个唯一标识符，该标识符将用于访问某些容器中的这些节点，那么您没有理由允许此类标识符的值为负数。

就像你指出的那样：visited[-200] = true;没有意义。如果您需要每个节点都有一个唯一的id/index这种类型，无论存储在其中的值如何，都可以这样做，即：

struct Node {
    unsigned int id;
    int value;
    ...
};

2 回答 2