title: Testing connectivity in undirected Graph (using DFS)
body: <p>I need to test which vertex is "important", where when a connected edge is removed, graph becomes disconnected. So my idea was try removing each edge then test the connectivity from 1 node to the other. </p>
  
  <p>Example: Remove edge connecting 2 - 5. Then test connectivity from 2 - 5: <code>isConnected(2,5)</code></p>
  
  <pre><code>  // DFS from node1 to node2
    boolean isConnected(int node1, int node2) {
      // keep track of (visited) status of nodes
      visited = new VertexState[V];
      for (int i = 0; i &lt; V; i++) 
        visited[i] = VertexState.NotVisited;
  
      // recursively test connectivity
      return _isConnected(node1, node2);
    }
  
    boolean _isConnected(int node1, int node2) {
      visited[node1] = VertexState.Visiting;
      if (node1 == node2) { // we found the node
        return true; 
      } else {
        for (int i = 0; i &lt; V; i++) { // for all children of node1
          if (AdjMatrix[node1][i] == 1 &amp;&amp; visited[i] == VertexState.NotVisited) {
            if (_isConnected(i, node2)) { // test if child can reach node2
              return true;
            }
          }
        }
        visited[node1] = VertexState.Visited;
      }
      return false;
    }
  </code></pre>
  
  <p>When I try it out with a simple graph, it works,but when I test it with a complex test case, it appears to produce wrong results. I have difficulties debugging as its a complex test case and can't draw it out.  </p>
  
  <hr>
  
  <p><strong>UPDATE</strong></p>
  
  <p>If it helps just the pseudocode: </p>
  
  <pre><code>isConnected(node1, node2) 
      visited = new VertexState[V]
      for each v in visited
          v = NotVisited
      return _isConnected(node1, node2); // the recursion
  
  _isConnected(node1, node2) 
      visited[node1] = Visiting
      if (node1 == node2) 
          return true // we found the node
      else 
          for each neighbour of node1
              if visited[neighbour] == NotVisited
                  if_isConnected(neighbour, node2) 
                      return true
          visited[node1] = Visited
      return false
  </code></pre>
  
  <p><strong>UPDATE 2</strong></p>
  
  <p>Full source <strong><a href="https://gist.github.com/3779445" rel="nofollow">https://gist.github.com/3779445</a></strong>, but with Adjacency List instead, it appears to work ... Not sure if its the most efficient algorithm tho ... </p>