graph-theory - 如何判断两个节点是否相连？

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 不会断开 House。

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

我可以将每个控制点视为图表上的权重（0 表示打开或 1 表示关闭）；然后找到 Well 和 House 之间的最短路径（结果 >= 1 表示它们已断开连接。我也可以通过多种方法短路算法以找到最短路径（例如，一旦到达 1 就丢弃路径，停止搜索一旦我们有任何连接井和房子的路径等）。当然，我也可以人为地限制在放弃之前要检查多少跳。

以前一定有人分类过这种问题，我只是漏掉了名字。

score 38 · Accepted Answer

您的描述似乎表明您只对两个节点是否连接感兴趣，而不是找到最短路径。

查找两个节点是否连接相对容易：

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 使用哈希表或类似的东西，我相信这是一个线性算法。

请注意，此算法基本上是标记和清除垃圾收集的标记部分。

score 7 · Accepted Answer

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

score 5 · Accepted Answer

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

score 3 · Accepted Answer

找到最短路径的问题不是 NP 完全的。它被称为最短路径问题（本来就足够了），并且有一些算法可以解决它的许多不同变体。

确定两个节点是否连接的问题也不是 NP 完全的。您可以使用从任一节点开始的深度优先搜索来确定它是否连接到另一个节点。

score 2 · Accepted Answer

2

不是NP完全的，用一个众所周知的解决方案解决 - Dijkstra's Algorithm

于 2008-12-09T21:43:24.283 回答

score 2 · Accepted Answer

对我来说，您似乎正在寻找解决方案，但我可能误解了这个问题。如果您确实如您所说，并将闭合边 1 作为权重，则可以应用 Dijkstra 的算法http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。这应该可以解决您在 O(E*lg(V)) 中的问题

score 2 · Accepted Answer

假设您有一个邻接矩阵：

bool[,] adj = new bool[n, n];

如果 i 和 j 之间存在开放路径并且 bool[i,i] = false，则 bool[i,j] = true。

public bool pathExists(int[,] adj, int start, int end)
{
  List<int> visited = new List<int>();
  List<int> inprocess = new List<int>();
  inprocess.Add(start);

  while(inprocess.Count > 0)
  {
    int cur = inprocess[0];
    inprocess.RemoveAt(0);
    if(cur == end)
      return true;
    if(visited.Contains(cur))
      continue;
    visited.Add(cur);
    for(int i = 0; i < adj.Length; i++)
      if(adj[cur, i] && !visited.Contains(i) && !inprocess.Contains(i))
        inprocess.Add(i);
  }
  return false;
}

这是上述算法的递归版本（用 Ruby 编写）：

def connected? from, to, edges
  return true if from == to
  return true if edges.include?([from, to])
  return true if edges.include?([to, from])

  adjacent = edges.find_all { |e| e.include? from }
                  .flatten
                  .reject { |e| e == from }

  return adjacent.map do |a|
    connected? a, to, edges.reject { |e| e.include? from }
  end.any?
end

score 1 · Accepted Answer

如果您只需要确定是否连接了 2 个节点，则可以使用集合代替，这比图形算法更快。

将整个图形拆分为边。将每条边添加到集合中。
在下一次迭代中，在您在步骤 2 中创建的边的 2 个外部节点之间绘制边。这意味着将新节点（及其对应的集合）添加到原始边缘所在的集合中。（基本上设置合并）
重复 2 直到您要查找的 2 个节点在同一个集合中。您还需要在步骤 1 之后进行检查（以防 2 个节点相邻）。

起初，您的节点将在其集合中，

o   o1   o   o   o   o   o   o2
 \ /     \ /     \ /     \ /
 o o     o o     o o     o o
   \     /         \     /
   o o o o         o o o o 
      \               /
       o o1 o o o o o o2

随着算法的进展和合并集合，它相对地减半输入。

在上面的示例中，我正在查看 o1 和 o2 之间是否存在路径。在合并所有边缘后，我才在最后找到了这条路径。一些图表可能有单独的组件（断开连接），这意味着您将无法在最后拥有一组。在这种情况下，您可以使用此算法来测试连通性，甚至计算图中的组件数量。组件数是算法完成时您能够获得的集合数。

一个可能的图表（对于上面的树）：

o-o1-o-o-o2
  |    |
  o    o
       |
       o

score 0 · Accepted Answer

Dijkstra 是矫枉过正！！只需使用 A 中的广度优先搜索来搜索您想要到达的节点。如果找不到，则说明未连接。每次搜索的复杂度为 O(nm)，低于 Dijkstra。

有点相关的是最大流量/最小切割问题。查一下，可能和你的问题有关。

score 0 · Accepted Answer

我看到您已经得到答案，它绝对不是 NP-Complete，这也是一个非常古老的问题。

但是，我将提出另一种解决问题的方法。您可以为此使用不相交集。在大多数情况下，对于给定的场景，该方法将比进行图遍历（这包括大量测试的恒定时间）产生更好的时间。但是，如果使用按等级联合或路径压缩，则构建图可能需要大量时间。

您可以在此处阅读有关数据结构的信息。

score -1 · Accepted Answer

如果您只需要查找一个节点是否连接到另一个节点，那么任何图形最短路径算法都将是多余的。JGraphT是一个很好的 Java 库。它的用法很简单，下面是一个整数图的例子：

public void loadGraph() {
    // first we create a new undirected graph of Integers
    UndirectedGraph<Integer, DefaultEdge> graph = new SimpleGraph<>(DefaultEdge.class);

    // then we add some nodes
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addVertex(5);
    graph.addVertex(6);
    graph.addVertex(7);
    graph.addVertex(8);
    graph.addVertex(9);
    graph.addVertex(10);
    graph.addVertex(11);
    graph.addVertex(12);
    graph.addVertex(13);
    graph.addVertex(14);
    graph.addVertex(15);
    graph.addVertex(16);

    // then we connect the nodes
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(5, 6);
    graph.addEdge(6, 7);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.addEdge(9, 10);
    graph.addEdge(10, 11);
    graph.addEdge(11, 12);
    graph.addEdge(13, 14);
    graph.addEdge(14, 15);
    graph.addEdge(15, 16);

    // finally we use ConnectivityInspector to check nodes connectivity
    ConnectivityInspector<Integer, DefaultEdge> inspector = new ConnectivityInspector<>(graph);

    debug(inspector, 1, 2);
    debug(inspector, 1, 4);
    debug(inspector, 1, 3);
    debug(inspector, 1, 12);
    debug(inspector, 16, 5);
}

private void debug(ConnectivityInspector<Integer, DefaultEdge> inspector, Integer n1, Integer n2) {
    System.out.println(String.format("are [%s] and [%s] connected? [%s]", n1, n2, inspector.pathExists(n1, n2)));
}

该库还提供了所有最短路径算法。

graph-theory - 如何判断两个节点是否相连？

11 回答 11

Related

Reference