1

我需要测试哪个顶点是“重要的”，当连接的边被移除时，图形变得断开连接。所以我的想法是尝试删除每条边，然后测试从一个节点到另一个节点的连接性。

示例：删除连接 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，但使用邻接列表，它似乎可以工作......不确定它是否是最有效的算法......

4

0 回答 0