algorithm - 确定是否存在从每个顶点到其他顶点的路径

Question

我正在寻找一种算法来确定图中的每个顶点 v 是否有一条从 v 到最多 20 个其他顶点的路径。！

Answer 1

您所要做的就是找到图表的连接组件。基数至少 20 的连通分量中的顶点是您要查找的顶点。

您可以直接使用不相交集数据结构来获得真正有效的算法。

1. 从自己集合中的每个顶点开始。
2. 对于每条边 e = { u, v }，合并包含 u 和 v 的集合。
3. 之后，这些集合对应于连接的组件。