这是问题所在:
假设有两个人在社交网站上注册,如何决定他们是否有联系？
我的分析(在阅读更多之后):实际上,问题是寻找 - 图中从A到B的最短路径.我认为BFS和Dijkstra的算法在这里工作,时间复杂度完全相同(O(V + E)),因为它是一个未加权的图,所以我们不能利用优先级队列.因此,一个简单的队列可以解决问题.但是,它们都没有解决这个问题:找到它们之间的路径.
此时Bidrectrol应该是更好的解决方案.
注意：答案已编辑。
任何方法最终都可能非常慢。如果您需要重复执行此操作，最好找到图的连接组件，之后任务就变成了一个简单的 O(1) 操作：如果两个人位于同一组件中，则他们是连接的。
请注意，第一次查找连接的组件可能会很慢，但随着新的边/节点添加到图中而保持它们更新的速度很快。
有多种方法可以找到连通分量。
一种方法是构造图的拉普拉斯算子，并查看其特征值/特征向量。零特征值的数量给出了连接分量的数量。相应特征向量的非零元素给出属于各个分量的节点。
另一种方法是沿着以下路线：
创建节点转换表。n数组的元素包含节点转换n到的节点的索引。
循环遍历图中的所有边（表示和(i,j)之间的连接）：ij
i。让我们用和 来j表示结果。更新条目以使其转换为. 更新条目并指向。klklijl再次循环该表，并更新每个条目以直接指向它递归转换到的节点。
现在，同一连接组件中的节点将在转换表中具有相同的条目。因此，要检查两个节点是否连接，只需检查它们是否转换为相同的值即可。
每次向图中添加新的节点或边时，都需要更新转换表，但这种更新会比表的原始计算快得多。