查找 N 个任意顶点之间的所有路径的图算法
我有一个具有以下属性的图：
- 无向
- 未加权
- 每个顶点至少有 2 个、最多 6 个连接到它的边。
- 顶点数将< 100
- 图是静态的，不能添加/删除或编辑任何顶点/边。
我正在寻找顶点的随机子集（至少 2 个）之间的路径。路径应该是只经过任何顶点一次的简单路径。
我的最终目标是拥有一组路线，以便您可以从一个子集顶点开始并到达任何其他子集顶点。沿着一条路线时，不必经过所有子集节点。
我发现的所有算法（Dijkstra、深度优先搜索等）似乎都在处理两个顶点之间的路径和最短路径。
是否有一种已知的算法可以为我提供连接这些顶点子集的所有路径（我想这些是子图）？
编辑：
我创建了一个（警告！程序员艺术）动画 gif 来说明我想要实现的目标： https://i.sstatic.net/O228a.gif
有两个阶段：预处理和运行时。
预处理
- 我有一个图和顶点的子集（蓝色节点）
- 我生成连接所有蓝色节点的所有可能路线
运行时
- 我可以从任何蓝色节点开始 选择任何生成的路线并沿着它行驶以到达我的目的地蓝色节点。
所以我的任务更多的是创建连接所有蓝色节点的所有子图（路线），而不是创建从 A->B 的路径。
I have an graph with the following attributes:
- Undirected
- Not weighted
- Each vertex has a minimum of 2 and maximum of 6 edges connected to it.
- Vertex count will be < 100
- Graph is static and no vertices/edges can be added/removed or edited.
I'm looking for paths between a random subset of the vertices (at least 2). The paths should simple paths that only go through any vertex once.
My end goal is to have a set of routes so that you can start at one of the subset vertices and reach any of the other subset vertices. Its not necessary to pass through all the subset nodes when following a route.
All of the algorithms I've found (Dijkstra,Depth first search etc.) seem to be dealing with paths between two vertices and shortest paths.
Is there a known algorithm that will give me all the paths (I suppose these are subgraphs) that connect these subset of vertices?
edit:
I've created a (warning! programmer art) animated gif to illustrate what i'm trying to achieve: https://i.sstatic.net/O228a.gif
There are two stages pre-process and runtime.
pre-process
- I have a graph and a subset of the vertices (blue nodes)
- I generate all the possible routes that connect all the blue nodes
runtime
- I can start at any blue node select any of the generated routes and travel along it to reach my destination blue node.
So my task is more about creating all of the subgraphs (routes) that connect all blue nodes, rather than creating a path from A->B.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
有很多方法可以解决这个问题，为了不混淆事情，这里有一个单独的答案，它解决了您的核心问题的描述：
如果您只想在以下位置使用一个，那么找到连接蓝色顶点的所有可能的子图可能有点过大无论如何。我宁愿使用一种随机找到单个算法的算法（所以不是任何最短路径算法等，因为它总是相同的）。
如果您想保存这些子图之一，您只需保存用于随机数生成器的种子，就可以再次生成相同的子图。
另外，如果您确实想找到一堆子图，随机算法仍然是一个不错的选择，因为您可以使用不同的种子运行多次。
唯一真正的缺点是，您永远不会知道是否找到了每一个可能的子图，但这听起来并不是您的应用程序的要求。
因此，关于算法：根据图的属性，最佳算法可能会有所不同，但您始终可以从简单的随机游走开始，从一个蓝色节点开始，走到另一个蓝色节点（同时使确保您没有走自己的老路）。然后在该路径上选择一个随机节点，并开始从那里走到下一个蓝色节点，依此类推。
对于某些图表，这具有非常糟糕的最坏情况复杂性，但可能足以满足您的情况。当然有更智能的方法来查找随机路径，但我会从简单的开始，看看它是否足够好。正如他们所说，过早的优化是邪恶的；）
There are so many ways to approach this and in order not confuse things, here's a separate answer that's addressing the description of your core problem:
Finding ALL possible subgraphs that connect your blue vertices is probably overkill if you're only going to use one at a time anyway. I would rather use an algorithm that finds a single one, but randomly (so not any shortest path algorithm or such, since it will always be the same).
If you want to save one of these subgraphs, you simply have to save the seed you used for the random number generator and you'll be able to produce the same subgraph again.
Also, if you really want to find a bunch of subgraphs, a randomized algorithm is still a good choice since you can run it several times with different seeds.
The only real downside is that you will never know if you've found every single one of the possible subgraphs, but it doesn't really sound like that's a requirement for your application.
So, on to the algorithm: Depending on the properties of your graph(s), the optimal algorithm might vary, but you could always start of with a simple random walk, starting from one blue node, walking to another blue one (while making sure you're not walking in your own old footsteps). Then choose a random node on that path and start walking to the next blue from there, and so on.
For certain graphs, this has very bad worst-case complexity but might suffice for your case. There are of course more intelligent ways to find random paths, but I'd start out easy and see if it's good enough. As they say, premature optimization is evil ;)
一个简单的广度优先搜索将为您提供从一个源顶点到所有顶点的最短路径其他顶点。因此，您可以从您感兴趣的子集中的每个顶点开始执行 BFS，以获得到所有其他顶点的距离。
请注意，在某些地方，BFS 将被描述为给出一对顶点之间的路径，但这不是必需的：您可以继续运行它，直到它访问了图中的所有节点。
该算法类似于 Johnson 算法，但大大简化了，因为您的图表是未加权的。
时间复杂度：由于每个顶点的边数是恒定的，因此每个 BFS 将花费 O(n)，总共将花费 O(kn)，其中 n 是顶点数，k 是子集的大小。作为比较，Floyd-Warshall 算法将花费 O(n^3)。
A simple breadth-first search will give you the shortest paths from one source vertex to all other vertices. So you can perform a BFS starting from each vertex in the subset you're interested in, to get the distances to all other vertices.
Note that in some places, BFS will be described as giving the path between a pair of vertices, but this is not necessary: You can keep running it until it has visited all nodes in the graph.
This algorithm is similar to Johnson's algorithm, but greatly simplified thanks to the fact that your graph is unweighted.
Time complexity: Since there is a constant number of edges per vertex, each BFS will take O(n), and the total will take O(kn), where n is the number of vertices and k is the size of the subset. As a comparison, the Floyd-Warshall algorithm will take O(n^3).
您正在搜索的（如果我理解正确的话）并不是所有路径，而是所有生成树。请阅读此处有关生成树的维基百科文章，以确定这些是否是您要查找的内容。如果是，您可能想阅读一篇论文：
Gabow ，哈罗德·N.；尤金·W·迈尔斯 (1978)。 “查找有向图和无向图的所有生成树”。暹罗 J. 计算机。 7 (280)。
What you're searching for is (if I understand it correctly) not really all paths, but rather all spanning trees. Read the wikipedia article about spanning trees here to determine if those are what you're looking for. If it is, there is a paper you would probably want to read:
Gabow, Harold N.; Myers, Eugene W. (1978). "Finding All Spanning Trees of Directed and Undirected Graphs". SIAM J. Comput. 7 (280).