연결이 끊어진 그래프 구성 요소를 효율적으로 감지합니까?

Question

다음과 같이 그래프를 검색하여 모든 꼭지점에 연결되어야하는 첫 번째 꼭지점에서 꼭지점에 도달 할 수 있는지 확인합니다. 연결되지 않은 부분이 없도록하기 위해이 작업을 수행합니다.

불행히도 매우 느립니다.

최적화를 위해 내가 할 수 있거나 저장할 수있는 것이 있습니까?

실제 그래프 라이브러리를 사용하지 않으므로 그래프와 생성 된 도시에 대해 배우고 싶습니다.

private void removeDisconnectedSquares() 
{ 
    for(int i = 0; i < getNumXNodes(); ++i) 
    { 
     for(int j = 0; j < getNumYNodes(); ++j) 
     { 
      //removeDisconnectedSquare(i, j); 
      visitedNodes.clear(); 
      if(!isNodeReachableFrom(getNodeAt(i, j), getNodeAt(0, 0))) 
      { 
       removeVertex(i, j); 
      } 
     } 
    } 
} 

private boolean isNodeReachableFrom(GraphNode node, GraphNode target) 
{ 
    if(node == null) 
    { 
     return false; 
    } 

    if(visitedNodes.contains(node)) 
    { 
     return false; 
    } 
    else 
    { 
     visitedNodes.add(node); 
    } 

    if(node == target) 
    { 
     return true; 
    } 

    if(node.contains(target)) 
    { 
     return true; 
    } 


    for(int i = 0; i < node.getSize(); ++i) 
    { 
     if(isNodeReachableFrom(node.at(i), target)) 
     { 
      return true; 
     } 
    } 

    return false; 
} 

Answer 1

연결이 끊어진 정점을 감지하는 것처럼 들리는 것 같습니다.

private ArrayList<GraphNode> getDisconnectedSet(ArrayList<GraphNode> allNodes, GraphNode target) 
{ 
    if(!allNodes.contains(target)) 
     return; 

    allNodes.remove(target); 

    for(Edge e : edges) // Need to edit to iterate through connected nodes 
     getDisconnectedSet(allNodes, e.otherSide); 
} 

는 그런 다음 모든 노드의 목록을 getDisconnectedSet를 호출하고 목록을 반환 한 후에 만 ​​연결이 끊긴 노드가 포함 : 당신이해야 할 것은의 라인을 따라 무언가이다.