在我看来,您只是在询问无向图中两个顶点之间是否存在路径,但不一定是该路径可能是什么。这与询问两个顶点是否在图形的相同连接组件中相同。
如果您确实只需要知道两个顶点是否在相同的连接组件中,则可以使用不相交集数据结构来简单高效地执行算法。
initialize the disjoint set structure (DSS)
for each edge:
for each vertex in edge:
if the vertex does not exist in the DSS:
create a new subset in the DSS containing only the vertex
merge the subsets of the two vertices
要确定在处理完所有边后两个顶点之间是否存在路径,只需检查两个顶点是否在同一子集中。如果它们是,则它们之间存在一些路径。
使用DSS的有效实现,该算法的效果仅比线性时间差一点,即使使用简单的DSS链表实现,它的O(n *
log(n))也是如此。正如j_
随机_
黑客提到的那样,无论是否仅计算传递闭包,Floyd-Warshall的存储时间均为O(n ^ 3)和O(n ^ 2),并且使用Dijkstra的算法需要O(n *
log(n) )计算每个查询。