data-structures - 無向グラフでの接続のテスト (DFS を使用)

Question

どの頂点が「重要」であるかをテストする必要があります。接続されたエッジが削除されると、グラフは切断されます。したがって、私の考えは、各エッジを削除してから、あるノードから別のノードへの接続をテストすることでした。

例: 2 ～ 5 を接続しているエッジを削除します。次に、2 ～ 5 の接続をテストします。isConnected(2,5)

  // 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 < 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 < V; i++) { // for all children of node1
        if (AdjMatrix[node1][i] == 1 && visited[i] == VertexState.NotVisited) {
          if (_isConnected(i, node2)) { // test if child can reach node2
            return true;
          }
        }
      }
      visited[node1] = VertexState.Visited;
    }
    return false;
  }

単純なグラフで試してみるとうまくいきますが、複雑なテスト ケースでテストすると、間違った結果になるようです。複雑なテストケースであるため、デバッグが困難であり、それを引き出すことができません。

---

アップデート

それが疑似コードだけに役立つ場合：

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

更新 2

完全なソースhttps://gist.github.com/3779445、代わりに隣接リストを使用すると、機能するように見えます...最も効率的なアルゴリズムかどうかはわかりません...