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

见 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm 一站式解决所有与图形相关的问题。我相信你的问题实际上是可以用二次时间来解决的。

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

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

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 toDoList
  Add it to doneList
  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使用哈希表或类似的方法,我相信这是一种线性算法。

请注意,此算法基本上是标记和扫描垃圾收集的标记部分。

对于这个问题,您不需要Dijkstra的算法,因为它使用了一个不需要的堆,并为您的复杂性引入了一个对数因子(n)。这只是宽度优先搜索——不要将闭合边作为边。

寻找最短路径的问题不是NP完全问题。这就是所谓的最短路径问题 algorithms 解决许多不同的变化。

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

非NP完全,用已知解求解- Dijkstra's Algorithm

对我来说,你似乎正在寻求解决办法,但我可能误解了这个问题。如果你按照你说的做,并且把闭合边1作为权重,你只需要应用Dijkstra的算法, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm . 这可以解决你在O(e*lg(v))中的问题。

假设你有一个邻接矩阵:

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

其中bool[i,j]=真,如果在i和j之间有一条开放的路径,bool[i,i]=假。

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

如果您只需要确定是否连接了两个节点,那么您可以使用集合,这比图形算法更快。

1. 将整个图形拆分为边。将每个边添加到集合中。
2. 在下一个迭代中,在步骤2中所做的边的两个外部节点之间绘制边。这意味着将新节点(及其相应的集)添加到原始边缘所在的集。(基本设置合并)
3. 重复2,直到您要查找的2个节点位于同一组中。您还需要在步骤1之后进行检查(以防两个节点相邻)。

首先,您的节点将是其集合中的每个节点,

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

Dijkstra太过分了!! 只需使用宽度优先搜索来搜索要到达的节点。如果你找不到它,它就没有连接。每个搜索的复杂性是O(nm),比dijkstra要小。

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

我知道你的答案是肯定不是NP完全,这也是一个很古老的问题。

不过,我将提出另一种方法来研究这个问题。你可以使用不相交的集合。在大多数情况下,对于给定的场景,该方法将比执行图形遍历(包括 固定时间 对于大量的测试)。但是,如果使用按列联合或按路径压缩,则构建图表可能需要很长的时间。

您可以阅读有关数据结构的信息 here .

如果你只需要找出一个节点是否连接到另一个节点上,那么任何图最短路径算法都将是多余的。一个很好的Java库 JGraphT . 它的用法非常简单,下面是一个整数图的示例:

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)));
}

这个lib还提供所有最短路径算法。