有效地检测断开连接的图形组件

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，在它返回后，列表仅包含断开连接的节点。