增强图:测试两个顶点是否相邻

Question

我是新用的C++ boost库,尤其是boost图库,它需要尝试编码一些算法,我通常检查两个顶点的邻接并处理其他图形概念,如计算图形不变量.我所知道的是我们可以使用函数迭代相邻的顶点:adjacent_vertices(u, g)但是我正在寻找一种有效的方法来测试两个顶点u,v是否相邻而不进行线性搜索

Answer 1

在邻接矩阵的概念给出了一个复杂保证该edge()功能必须在固定的时间返回.

要检查是否两个顶点v和w在相邻的G,则写edge(v, w, G).second,因为该函数返回一个对,其中第二值指示如果边缘存在.

该edge()功能也用于其他图形表示.下面的图表显示了不同的表示与检查顶点邻接性能的比较:

以下是用于为此图生成数据的代码.每个数据点是100个中密度随机图,每个图有100个随机边缘检查.注意对数y轴.

什么是最佳选择最终取决于您的特定应用,因为对于其他操作,结构的速度顺序是不同的.换句话说,避免过早优化.