1

我有以下搜索我的图表以查看是否可以从第一个顶点到达顶点，所有内容都应该连接到该顶点。我这样做是为了确保没有断开的部件。

不幸的是，它非常慢。

有什么我可以做或存储来优化它的吗？

我想了解图表和生成的城市，所以我没有使用真正的图表库。

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

1 回答 1

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

于 2012-10-06T20:37:59.687 回答