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 に答える