How to determine if two nodes are connected?

问题:

I'm concerned that this might be working on an NP-Complete problem. I'm hoping someone can give me an answer as to whether it is or not. And I'm looking for more of an answer than just yes or no. I'd like to know why. If you can say,"This is basically this problem 'x' which is/is not NP-Complete. (wikipedia link)"

(No this is not homework)

Is there a way to determine if two points are connected on an arbitrary non-directed graph. e.g., the following

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

Points A though M (no 'I') are control points (like a valve in a natural gas pipe) that can be either open or closed. The '+'s are nodes (like pipe T's), and I guess the Well and the House are also nodes as well.

I'd like to know if I shut an arbitrary control point (e.g., C) whether the Well and House are still connected (other control points may also be closed). E.g., if B, K and D are closed, we still have a path through A-E-J-F-C-G-L-M, and closing C will disconnect the Well and the House. Of course; if just D was closed, closing only C does not disconnect the House.

Another way of putting this, is C a bridge/cut edge/isthmus?

I could treat each control point as a weight on the graph (either 0 for open or 1 for closed); and then find the shortest path between Well and House (a result >= 1 would indicate that they were disconnected. There's various ways I can short circuit the algorithm for finding the shortest path too (e.g., discard a path once it reaches 1, stop searching once we have ANY path that connects the Well and the House, etc.). And of course, I can also put in some artificial limit on how many hops to check before giving up.

Someone must have classified this kind of problem before, I'm just missing the name.

回答1:

See http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm , your one stop shop for all graph related problems. I believe your problem is in fact solvable in quadratic time.

回答2:

Your description seems to indicate that you are just interested in whether two nodes are connected, not finding the shortest path.

Finding if two nodes are connected is relatively easy:

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.

If you use a hash table or something similar for toDoSet and doneSet, I believe this is a linear algorithm.

Note that this algorithm is basically the mark portion of mark-and-sweep garbage collection.

回答3:

You don't need Dijkstra's algorithm for this problem, as it uses a Heap which isn't needed and introduces a factor of log(N) to your complexity. This is just breadth first search - don't include the closed edges as edges.

回答4:

The problem of finding the shortest path isn't NP-complete. It's called the Shortest Path Problem (originally enough) and there are algorithms for solving many different variations of it.

The problem of determining if two nodes are connected isn't NP-complete either. You can use a depth first search starting at either node to determine if it is connected to the other node.

回答5:

not NP-complete, solved with a well-known solution - Dijkstra's Algorithm

回答6:

To me it seems like you are on to a solution, but it's possible I misunderstood the problem. If you do like you say, and give the closed edges 1 as weight, you can just apply Dijkstra's algorithm, http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. This should solve your problem in O(E*lg(V))

回答7:

Assuming that you have an adjacency matrix:

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

Where bool[i,j] = true if there is an open path between i and j and bool[i,i] = false.

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

Here is a recursive version of the algorithm above (written in 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

回答8:

If all you need is to determine if 2 nodes are connected you can use sets instead, which is faster than graph algorithms.

1. Split your entire graph into edges. Add each edge to a set.
2. On next iteration, draw edges between the 2 outer nodes of the edge you made in step 2. This means adding new nodes (with their corresponding sets) to the set the original edge was from. (basically set merging)
3. Repeat 2 until the 2 nodes you're looking for are in the same set. You will also need to do a check after step 1 (just in case the 2 nodes are adjacent).

At first your nodes will be each in its set,

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

As the algorithm progresses and merges the sets, it relatively halves the input.

In the example above I was looking to see if there was a path between o1 and o2. I found this path only at the end after merging all edges. Some graphs may have separate components (disconnected) which entails that you will not be able to have one set at the end. In such a case you can use this algorithm to test for connectedness and even count the number of components in a graph. The number of components is the number of sets you are able to get when the algorithm finishes.

A possible graph (for the tree above):

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

回答9:

Dijkstra's is overkill!! Just use breadth first search from A to search for the node you want to reach. If you can't find it, it's not connected. Complexity is O(nm) for each search, which is less then Dijkstra.

Somewhat related is the max-flow/min-cut problem. Look it up, it might be relevant to your problem.

回答10:

I see you have got your answer that it's definitely not NP-Complete and this is a very old question as well.

However, I'll just propose another approach to look at the problem. You could use disjoint sets for this. In most cases, for the given scenario, the approach will result in better time than doing a graph traversal (That includes constant time for a large chunk of tests). However, building the graph might take good amount of time, if union by rank or path compression is used.

You can read about the Data Structure here.

回答11:

Any graph shortest path algorithm will be overkill if all you need is to find if a node is connected to another. A good Java library that accomplishes that is JGraphT. It's usage is quite simple, here's an example of an Integer graph:

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

This lib also offers all the shortest paths algorithms as well.