如果节点或顶点在 C++ 中编号为正,我们可以轻松实现广度优先搜索算法。
但是当节点或顶点编号为负时如何处理。
假设一个节点编号为 -200,如果我们分配bool visited[-200] = true or false
,那么它将产生运行时错误。
在这种情况下将采用什么方法?
如果节点或顶点在 C++ 中编号为正,我们可以轻松实现广度优先搜索算法。
但是当节点或顶点编号为负时如何处理。
假设一个节点编号为 -200,如果我们分配bool visited[-200] = true or false
,那么它将产生运行时错误。
在这种情况下将采用什么方法?
在处理图形标签时,似乎一种合理的方法是使用属性映射(例如,参见Boost Graph Library。基本思想是通过结构化方法访问节点属性,其中属性的细节实际上是访问的主题到正在使用的具体属性映射。
根据您所说的,您正在使用节点 ID 访问标签。根据 ID 的实际布局,有两种明显不同的方法:
label[nodeID - minNodeID]
.如果您可以控制节点表示的布局,您可能应该考虑将标签存储在节点中,尤其是在节点 ID 是随机分布的情况下。
“如果节点编号为负数” ~> 如果您需要每个节点都有一个唯一标识符,该标识符将用于访问某些容器中的这些节点,那么您没有理由允许此类标识符的值为负数。
就像你指出的那样:visited[-200] = true;
没有意义。如果您需要每个节点都有一个唯一的id
/index
这种类型,无论存储在其中的值如何,都可以这样做,即:
struct Node {
unsigned int id;
int value;
...
};