如何确定两个节点是否连接？

Question

我担心这可能会影响NP-Complete问题.我希望有人可以给我一个答案,不管它是否存在.而且我正在寻找更多的答案,而不仅仅是是或否.我想知道为什么.如果你可以说,"这基本上是这个问题'x',它不是NP-Complete.(维基百科链接)"

(不,这不是作业)

有没有办法确定两个点是否连接在任意非有向图上.例如,以下

Well
  |
  |
  A
  |
  +--B--+--C--+--D--+
  |     |     |     |
  |     |     |     |
  E     F     G     H
  |     |     |     |
  |     |     |     |
  +--J--+--K--+--L--+
                    |
                    |
                    M
                    |
                    |
                  House

点A到M(没有'I')是控制点(如天然气管道中的阀门),可以是打开的或关闭的.'+'是节点(比如管道T),我猜Well和House也是节点.

我想知道我是否关闭了一个任意控制点(例如C)井和房子是否仍然连接(其他控制点也可以关闭).例如,如果B,K和D关闭,我们仍然有一条通过AEJFCGLM的路径,关闭C将断开Well和House.当然; 如果只是D被关闭,只关闭C不会断开众议院.

另一种说法是C桥/切边/地峡？

我可以将每个控制点视为图形上的权重(0表示打开,1表示关闭); 然后找到Well和House之间的最短路径(结果> = 1表示它们已断开连接.我可以通过各种方法将算法短路以找到最短路径(例如,一旦达到1就丢弃路径,停止搜索一旦我们有任何连接井和房子的路径等等.当然,我也可以在放弃之前对要检查的跳数进行一些人为的限制.

有人必须先把这类问题归类,我才错过这个名字.

Answer 1

您的描述似乎表明您只关心两个节点是否已连接,而不是找到最短路径.

查找是否连接了两个节点相对简单:

Create two sets of nodes:  toDoSet and doneSet
Add the source node to the toDoSet 
while (toDoSet is not empty) {
  Remove the first element from toDoSet
  Add it to doneSet
  foreach (node reachable from the removed node) {
    if (the node equals the destination node) {
       return success
    }
    if (the node is not in doneSet) {
       add it to toDoSet 
    }
  }
}

return failure.

如果你对toDoSet和doneSet使用哈希表或类似的东西,我相信这是一个线性算法.

请注意,此算法基本上是标记和清除垃圾回收的标记部分.

Answer 2

请参阅http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm,了解所有与图形相关的问题.我相信你的问题实际上可以在二次时间内解决.

Answer 3

你不需要Dijkstra算法来解决这个问题,因为它使用了一个不需要的堆,并为你的复杂性引入了log(N)因子.这只是广度优先搜索 - 不包括封闭边缘作为边缘.