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