我有一个具有以下属性的图表：
我正在寻找顶点的随机子集（至少 2 个）之间的路径。路径应该是只经过任何顶点一次的简单路径。
我的最终目标是拥有一组路线，以便您可以从一个子集顶点开始并到达任何其他子集顶点。跟随路线时不必通过所有子集节点。
我发现的所有算法（Dijkstra、深度优先搜索等）似乎都在处理两个顶点之间的路径和最短路径。
是否有一种已知的算法可以为我提供连接这些顶点子集的所有路径（我想这些是子图）？
编辑：
我创建了一个（警告！程序员艺术）动画 gif 来说明我想要实现的目标：http: //imgur.com/mGVlX.gif
有两个阶段预处理和运行时。
所以我的任务更多是关于创建连接所有蓝色节点的所有子图（路由），而不是创建从 A->B 的路径。
简单的广度优先搜索将为您提供从一个源顶点到所有其他顶点的最短路径。因此，您可以从您感兴趣的子集中的每个顶点开始执行 BFS，以获取到所有其他顶点的距离。
请注意，在某些地方，BFS 将被描述为给出一对顶点之间的路径，但这不是必需的：您可以继续运行它，直到它访问了图中的所有节点。
该算法类似于Johnson 的算法，但由于您的图形未加权这一事实而大大简化。
时间复杂度：由于每个顶点的边数是恒定的，每个 BFS 将花费 O(n)，而总数将花费 O(kn)，其中 n 是顶点数，k 是子集的大小。作为比较，Floyd-Warshall算法将采用 O(n^3)。
您正在寻找的是（如果我理解正确的话）并不是所有的路径，而是所有的生成树。在此处阅读有关生成树的维基百科文章，以确定这些是否是您要查找的内容。如果是，那么您可能想阅读一篇论文：
哈罗德·N·加博；迈尔斯，尤金 W. (1978)。“查找有向图和无向图的所有生成树”。暹罗学家计算机。7 (280)。
有很多方法可以解决这个问题，为了不混淆，这里有一个单独的答案，用于解决您的核心问题的描述：
如果您一次只使用一个，那么查找所有可能连接您的蓝色顶点的子图可能是多余的。我宁愿使用一种能找到单个但随机的算法（所以不是任何最短路径算法等，因为它总是相同的）。
如果要保存这些子图之一，只需保存用于随机数生成器的种子，就可以再次生成相同的子图。
此外，如果您真的想找到一堆子图，随机算法仍然是一个不错的选择，因为您可以使用不同的种子多次运行它。
唯一真正的缺点是你永远不会知道你是否找到了每一个可能的子图，但这听起来并不是你的应用程序的要求。
所以，关于算法：根据你的图的属性，最佳算法可能会有所不同，但你总是可以从一个简单的随机游走开始，从一个蓝色节点开始，走到另一个蓝色节点（同时使确保您没有走自己的旧脚步）。然后在该路径上选择一个随机节点并开始从那里走到下一个蓝色，依此类推。
对于某些图表，这具有非常糟糕的最坏情况复杂性，但可能足以满足您的情况。当然有更智能的方法可以找到随机路径，但我会从简单开始，看看它是否足够好。正如他们所说，过早的优化是邪恶的；）
