我担心这可能会解决NP-Complete问题。我希望有人可以给我一个答案，答案是否正确。我正在寻找的答案不仅仅是"is"或“不是”。我想知道为什么。如果您可以说:“这基本上是/不是NP完全的问题'x'。(维基百科链接)”
(不，这不是作业)
有没有一种方法可以确定两个点是否连接在任意非有向图上。例如，以下
Well
|
|
A
|
+--B--+--C--+--D--+
| | | |
| | | |
E F G H
| | | |
| | | |
+--J--+--K--+--L--+
|
|
M
|
|
House
点A到M(没有“I”)是可以打开或关闭的控制点(例如天然气管道中的阀门)。 “+”是节点(如管道T)，我想“井”和“房屋”也是节点。
我想知道是否关闭任意控制点(例如C)，井和房屋是否仍处于连接状态(其他控制点也可能关闭)。例如，如果B，K和D关闭，那么我们仍然有一条通过A-E-J-F-C-G-L-M的路径，而关闭C将断开水井和房屋的连接。当然;如果只是关闭D，则仅关闭C不会断开房屋。
另一种表达方式是C是桥/切边/地峡吗？
我可以将每个控制点都视为图表上的权重(打开时为0或关闭时为1)；然后找到Well和House之间的最短路径(结果> = 1表示它们已断开连接。我也可以通过多种方法来短路用于查找最短路径的算法(例如，一旦路径到达1，则丢弃该路径，然后停止一旦我们有了连接井和房屋等的任何路径，就可以进行搜索。)当然，我也可以对放弃之前要检查的跃点数设置一些人为的限制。
以前一定有人对这种问题进行过分类，我只是想念这个名字。
最佳答案
有关所有与图形相关的问题，请参见http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm，您的一站式服务。我相信您的问题实际上可以在二次时间内解决。
关于graph-theory - 如何确定两个节点是否连接？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/354330/