0

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

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

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

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

4

2 回答 2

0

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

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

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

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

于 2013-09-26T13:56:10.683 回答
0

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

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

struct Node {
    unsigned int id;
    int value;
    ...
};
于 2013-09-26T13:53:05.300 回答