rus*_*cle 6 language-agnostic algorithm graph-theory graph subgraph
我有一个包含以下属性的图表:
我正在寻找顶点的随机子集(至少2)之间的路径.路径应该是只经过任何顶点一次的简单路径.
我的最终目标是拥有一组路线,以便您可以从其中一个子集顶点开始并到达任何其他子集顶点.在跟踪路由时,不必通过所有子集节点.
我发现的所有算法(Dijkstra,Depth first search等)似乎都在处理两个顶点和最短路径之间的路径.
是否有一个已知的算法可以为我提供连接这些顶点子集的所有路径(我想这些是子图)？
编辑:
我创建了一个(警告!程序员艺术)动画gif来说明我想要实现的目标:http://imgur.com/mGVlX.gif
预处理和运行时分为两个阶段.
所以我的任务更多的是创建连接所有蓝色节点的所有子图(路由),而不是创建A-> B的路径.
有很多方法可以解决这个问题，为了不混淆事情，这里有一个单独的答案来解决您的核心问题的描述：
如果您一次只使用一个，那么找到连接蓝色顶点的所有可能的子图可能就太过分了。我宁愿使用一种随机找到单个算法的算法（所以不是任何最短路径算法等，因为它总是相同的）。
如果您想保存这些子图之一，您只需保存用于随机数生成器的种子，您就可以再次生成相同的子图。
此外，如果您确实想找到一堆子图，随机算法仍然是一个不错的选择，因为您可以使用不同的种子运行多次。
唯一真正的缺点是，您永远不会知道是否找到了每一个可能的子图，但这听起来并不是您的应用程序的要求。
因此，关于算法：根据图的属性，最佳算法可能会有所不同，但您始终可以从简单的随机游走开始，从一个蓝色节点开始，走到另一个蓝色节点（同时使确保你没有走自己的老路）。然后在该路径上选择一个随机节点，并开始从那里走到下一个蓝色节点，依此类推。
对于某些图表，这具有非常糟糕的最坏情况复杂性，但可能足以满足您的情况。当然有更智能的方法来查找随机路径，但我会从简单的开始，看看它是否足够好。正如他们所说，过早的优化是邪恶的；）
