诱导子图；两个节点之间存在路径
抱歉，文字墙很长，我已经尽力简洁了！
我有一个非常大的有向图 G 和 G 中的顶点子集 S。我想要做的是找到由 S 引起的 G 的子图，另外还要考虑顶点之间是否存在某些路径p 和 G 中的顶点 q，则导出子图中这两个顶点之间存在边。这是关键； （我认为）它比通常的诱导子图问题更复杂一些。
我能想到的解决问题的最基本方法如下（我意识到这可能不是最有效的，如果您有其他实施起来不太复杂的建议，请告诉我）：对于 S 中的每一对顶点，测试 G 中它们之间是否存在路径。如果存在这样的路径，则在导出子图中的 p 和 q 之间插入一条边。就我的目的而言，n^2 次并没有那么糟糕。
所以，我想我有两个问题： 1）确定两个顶点之间是否存在路径的最快方法是什么？我不需要知道路径，只需要知道它是否存在。此外，如果我可以对整个图进行一些预处理以使计算速度更快，那么它可能是什么，因为我必须在每对顶点之间执行此计算？
2）是否有比我建议的方法更快的方法来查找我描述的诱导子图的类型？
非常感谢您的帮助！
Sorry for the wall of text, its as concise as I could make it!
I've got one very large directed graph, G, and subset of vertices, S, from within G. What I want to do is find the subgraph of G induced by S, with the additional consideration that if some path exists between a vertex p and a vertex q in G, that an edge exists between these two vertices in the induced subgraph. This is key; its a little more complicated (I think) than the usual induced subgraph problem.
The most rudimentary way I can think of to solve the problem is the following (I realize its probably not the most efficient, let me know if you have other suggestions that aren't too complicated to implement): For every pair of vertices within S, test for the existence of a path between them in G. If such a path exists, insert an edge between p and q in the induced subgraph. For my purposes, an n^2 time isn't that bad.
So, I suppose I have two questions:
1) What is the fastest way to determine whether or not a path EXISTS between two vertices? I don't need to know the path, just whether or not it exists. Furthermore, if there is some preprocessing I can do to the whole graph to make this calculation faster, what might it be, since I have to perform this calculation between each pair of vertices?
2) Is there a faster way than the one I suggested to find the type of induced subgraph I described?
Thanks so much for the help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
寻找两个顶点之间是否存在路径的问题称为传递闭包问题，一般情况下它与矩阵乘法一样困难。我将首先在您的图上运行强连接组件算法，以将循环压缩到单个节点并形成有向图。如果你幸运的话，你会遇到一些大循环，这将使后续的传递问题变得容易。然后我会在该图上运行 Floyd Warshall 所有对最短路径算法来计算传递闭包，因为它的编码非常简单。也许基于 o(n^3) 矩阵乘法的算法之一会更快，但我怀疑它会快得多，因为常数太低了 Floyd Warhsall。
这是强连接组件的快速算法。
这包含了矩阵乘法和传递闭包的等价性证明.
我不确定是否有任何好的方法可以绕过计算传递闭包来解决您的原始问题。我怀疑不会，但另一方面，有时聪明的人会想出一些很棒的东西。
The problem of finding whether a path exists between two vertices is called the transitive closure problem, and it's as hard as matrix multiplication in the general case. I would first run a strongly connected components algorithm on your graph to compress cycles into a single node and form a directed graph. If you are lucky, you'll have some big cycles and that will make the subsequent transitive problem easy. Then I'd run the Floyd Warshall all pairs shortest paths algorithm on that graph to compute the transitive closure because it's incredibly simple to code. Maybe one of the o(n^3) matrix multiplication based algorithm will be faster, but I doubt it will be that much faster because the constant is so low Floyd Warhsall.
Here is a fast algorithm for strongly connected components.
And this contains a proof of the equivalence of matrix multiplication and transitive closure.
I am not sure if there is any good way to get around computing the transitive closure to solve your original problem. I suspect not, but on the other hand, sometimes clever people come up with something great.