有效檢測斷開的圖形組件？

我有以下搜索我的圖形，看看是否可以從第一個頂點到所有應該連接到的頂點。我這樣做是爲了確保沒有斷開的部分。有效檢測斷開的圖形組件？

不幸的是它非常緩慢。

有什麼我可以做或存儲來優化？

我想了解圖形和生成的城市，所以我不使用真正的圖形庫。

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; 
}

來源

2012-10-06 jmasterx

這似乎比[SO]更適合[codereview]（http://codereview.stackexchange.com/）。你應該嘗試在那裏問。 – toniedzwiedz

我想說它屬於這裏，因爲他有點問如何快速找到他的圖表的不連貫的組件。 – CrazyCasta

我覺得這個說法（「我想了解圖形和生成的城市，所以我不使用真正的圖形庫」）是相反的直覺。學習一個開源圖形庫將是一個很好的方式來實現你更多地瞭解圖形的目標。例如，工業強度圖庫的來源可能會回答這個問題。 – WeirdlyCheezy

這聽起來像你想要做的是檢測斷開的頂點。你應該做的是沿着線的東西：

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的所有節點的列表，並將其返回列表後，只包含斷開連接的節點。

來源

2012-10-06 20:37:59 CrazyCasta

問題是我沒有連接節點列表，連接和斷開都在同一個數組中。 – jmasterx

是的，但是在每個節點上，您都有一個哪些節點直接連接到該節點的列表。也許我的編輯更清晰一點（或者更少一些：P） – CrazyCasta

有效檢測斷開的圖形組件？

回答

相關問題