c++ - 关于在系统中表示路径的数据结构的建议

Question

我有一个系统，我需要在其中表示类似于 Path 的东西，路径只是提供到达特定节点的路线。可以有多个路径可用于到达同一节点。

我目前正在使用节点 vector 表示路径，我需要执行诸如 replaceSubpath、containsNode、containsSubPath、appendNode、getRootNode、getLeafNode 之类的操作(与对字符串所做的操作非常相似)。所有这些操作都可以在 vector 上完成，但大路径的性能可能很差。

我正在考虑使用 boost::graph 但没有使用它的经验，我想知道使用 boost::graph 对于这些和类似的操作是否是正确/良好的数据结构？

任何关于使用其他数据结构的建议也会有所帮助，我知道我可以通过将节点的(多)映射保留到迭代器等来优化我的 vector 解决方案。

Answer 1

本质上，类 adjacency_list<>来自 Boost.Graph 的是一个顶点 vector 。顶点描述符是该 vector 中的整数索引。

通常，一棵树或一条路径(路径是树的特例，对吧？)被表示为一个前置映射(比如从叶到根或从目标到源)。在整数顶点描述符的情况下，这样的前置映射就是vector<int> .我认为您无法以更紧凑的方式表示路径或树。

当然，这种前辈的vector可以代入字符串操作，esp。来自 Boost.String_Algo 的那些，http://www.boost.org/doc/libs/1_55_0/doc/html/string_algo.html