java - 有效检测断开连接的图形组件？

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