使用 vecS 在 adjacency_list 上的 `boost::edge()` 的运行时复杂度是多少？

Question

我有一个无向 adjacency_list 图定义如下：

typedef boost::adjacency_list<
               boost::vecS,
               boost::vecS, boost::undirectedS,
               boost::no_property,
               boost::property<
                 boost::edge_weight_t, int, EdgeInfo> 
            > weighted_graph;

对于我的算法class，我的程序太慢了，在速度方面只通过了四个测试集之一。然后我做了一个小改动，使我的程序通过了所有时间限制测试：我停止使用 weightmap[boost::edge(u, v, G).first].

相反，我在所有边上循环一次，并将每个边的权重存储在二维向量中两次，这样我就可以用 weightvec[u][v] 来查找它。

我找不到任何关于 boost::edge() 的运行时复杂性的文档。我预计它会保持不变，但似乎并非如此。图中的边数和顶点数的复杂度是多少？

我考虑过这是否可能是由于访问了权重属性图，但如果我仍然使用权重图并存储边缘描述符，我仍然会看到加速。

Answer 1

edge(v,u) 搜索边。你为什么要这样做？如果既然²你知道边缘无论如何都存在，你应该：

改用邻接矩阵
或者已经掌握了您已知存在的边的边描述符（而不是搜索它）

Q. I was not able to find any documentation on the runtime complexity of boost::edge().

我猜这是邻接表的概念所隐含的（见下文）。此外，由于影响此的许多泛型类型参数，制定起来会很棘手。

Q. I expected it to be constant, but it seems like that's not true.

所以，让我们看看。邻接列表是...邻接列表。对于一个图，它将是一个顶点列表，每个顶点都有一个“邻接”列表 - 即“边”，由它们的目标顶点表示（数据结构已经隐含了源）。

通过 (v,u) 个顶点端点在图 g 中查找边需要：

在主列表中搜索 (v)
在本地邻接集上搜索 (u)

既然你选择了vecS/vecS，两者都可以是线性搜索。

幸运的是，因为顶点的 vecS 是随机访问的并且元素索引是 by definition the vertex_index 它将是 O(1)。（其中 n 是 num_vertices(g)）和第二个 O(m)（其中 m 是顶点的平均出度）。

Q. I considered if it might be due to the access to the weight property map instead, but if I still use the weightmap and store the edge descriptors, I still see that speedup.

是的，属性地图没有进行搜索：

结论

有一些时间可以争取，可能，例如。使用其他容器选择器。但是，根据直觉，我猜你真的在寻找 adjacency matrix or even implicit graphs (more).

¹ 在这种情况下。在定向情况下，您会说出边。 Boost 还有一个“双向”表示，其中每个列表条目都包含一个冗余传入边列表，以针对某些算法进行优化

² 这可以从您无条件地使用 .first 而不检查搜索结果这一事实推断出来。在不存在的边上这样做可能是 UB

使用 vecS 在 adjacency_list 上的 `boost::edge()` 的运行时复杂度是多少？

What is the runtime complexity of `boost::edge()` on an adjacency_list with vecS?

c++

boost

boost-graph

结论