通过无向图中的顶点查找边[C++BGL]

这取决于您的图形模型：https://valelab4.ucsf.edu/svn/3rdpartypublic/boost/libs/graph/doc/graph_concepts.html

AdjacencyMatrix具有您直接想要的功能：

autoe=boost:：edge（v，u，图形）；

（其中e、v和u是描述符）

假设要通过“邻接列表”查看“非邻接列表”的源的“双向”实例：

使用Graph=boost:：邻接列表&lt&gt；；
使用V=Graph:：vertex\u描述符；
使用E=Graph:：edge\u描述符；
E我的查找边（V V，V u，图常数和g）
{
对于（自动e:boost:：生成迭代器范围（外边缘（v，g）））{
如果（目标（e，g）=u）
返回e；
}
抛出标准：：域错误（“我的查找边缘：未找到”）；
}

对于双向图，您可以选择从目标顶点开始

演示

在编译器资源管理器上实时运行

“包括”；boost/graph/adjacence_list.hpp“；
#包括&lt；boost/range/iterator_range.hpp&gt；
使用Graph=boost:：邻接列表&lt&gt；；
使用V=Graph:：vertex\u描述符；
使用E=Graph:：edge\u描述符；
E我的查找边（V V，V u，图常数和g）
{
对于（自动e:boost:：生成迭代器范围（外边缘（v，g）））{
如果（目标（e，g）=u）
返回e；
}
抛出标准：：域错误（“我的查找边缘：未找到”）；
}
#包括「；boost/graph/random.hpp“；
#包括&lt；随机&gt；
int main（）{
std:：mt19937 prng{std:：random_设备{}（）}；
用于（自动i=0；i&lt；10；++i）
试一试{
图g；
生成随机图（g，10，20，prng）；
E=我的查找边（7,2,g）；
std：：cout&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；&lt；发现；；
}捕获（标准：：异常常量和e）{
std：：cout&lt；&lt；e.what（）&lt；&lt；\n&quot；；
}
}

印刷品

我的查找边缘：未找到
我的查找边缘：未找到
发现：（7,2）
发现：（7,2）
我的查找边缘：未找到
我的查找边缘：未找到
我的查找边缘：未找到
我的查找边缘：未找到
我的查找边缘：未找到
发现：（7,2）

进一步优化

对于集合顶点选择器，您可以使用std:：binary_search和friends（std:：lower_bound、std:：upper_bound或std:：equal_range）进行优化

我会大量咨询我的分析器，看看这是否真的提高了性能。我有一种感觉，除非你有很高的学位，否则可能不会