在负编号节点上实现bfs

Question

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

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

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

在这种情况下会采取什么方法？

Answer 1

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

就像你指出的那样：visited[-200] = true;是没有意义的。如果你需要在每个节点有这种独特的id/index，做到这一点无论存储在其中的值，即：

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

Answer 2

当图形标签处理这似乎是一个合理的方法是使用属性映射（基于见，例如，Boost Graph Library。其基本思想是通过结构化的方法，其中属性的细节实际上是访问受所使用的具体属性映射到接入节点的属性。

什么你说你正在使用节点ID来访问标签，有两种明显的方法具有取决于ID的实际布局一些不同的特性：

1. 如果节点标签是相对致密的和值的节点ID的范围是已知的，使用具有合适的调整的阵列使用偏移是一种合理的方法。也就是说，你会使用像label[nodeID - minNodeID]这样的数组。
2. 如果节点标签是随机分布的，则需要使用一个节点ID作为容器密钥的关联容器。

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