如何在图表中搜索路径？
假设我有一个边列表，每个边包含两个节点（往返）。 找到两个给定节点的边缘的最佳方法是什么？ 请注意，边缘中的节点可能会重复。
说我有这种格式的优势：
1 – – > 5
3 7
5 6
2 6
然后查询如1 5将返回true 。
然后查询如5 2将返回true，因为5连接6和6连接到2。
然后查询如1 7将返回false 。
然后查询如7 4将返回false，因为4不存在，这意味着它是无边节点。
听起来像你只是在询问无向图中两个顶点之间是否存在路径，但不一定是该路径可能是什么。 这与询问两个顶点是否在图的相同连接组件中相同。
如果你真的只需要知道两个顶点是否在同一个连通组件中，那么就有一个使用Disjoint-set数据结构的简单而有效的算法。
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 _ random _ hacker提到的，Floyd-Warshall是O（n ^ 3）时间和O（n ^ 2）存储，无论你是否只计算传递闭包，并且使用Dijkstra算法需要O（n * log） （n））每个查询的计算。
您基本上期待测试给定的节点对是否在它们之间有路径。 这是最短路径问题的一般情况。 但是，请注意，如果我们可以找到所讨论的节点对之间的最短路径就足够了。 使用适合您的任何表示（邻接矩阵，邻接列表，边集，联合查找…），并为所有节点对继续使用BFS / Djikstra实现。 这只是服务查询的问题。 或者，您可以在惰性基础上运行Djikstra / BFS（并以增量方式缓存过去的计算）。
查看JGraphT库，它专注于图形算法，并满足您的需求。
您可能需要一些Floyd算法的变体来寻找所有图形椎体之间的最短路径。 据我所知，您只需要传递关闭无向图。 这是伪代码：
for k = 1 to n for i = 1 to n for j = 1 to n W[i][j] = W[i][j] or (W[i][k] and W[k][j])
运行此代码之前的W应该是图形的二元邻接矩阵（ W[i][j] == 1 <->从i到j的边缘）。 之后它将是一个传递性的封闭。 即，当且仅当j可从i到达时， W[i][j]将等于1 。