2

1 つのソース頂点とエッジのリストを含むグラフがあり、各反復でリストの 1 つのエッジがグラフから削除されます。

各頂点について、ソース頂点への接続が失われた後の反復回数を出力する必要があります。頂点とソースの間にパスはありません。

私の考えは、各反復でソース頂点から DFS アルゴリズムを実行し、ソース頂点と接続している頂点の値をインクリメントすることです。頂点とソース頂点の間にパスがあります。

各反復でソース頂点から dfs アルゴリズムを実行するよりも良いアイデアがあると確信しています。しかし、問題をより迅速に解決する方法がわかりません。

4

2 に答える 2

3

エッジ リスト全体を事前に取得しているため、逆方向に処理して、グラフを切断する代わりに接続できます。

擬似コード:

GIVEN:
edges = list of edges
outputMap = new empty map from vertex to iteration number
S = source vertex

//first remove all the edges in the list
for (int i=0;i<edges.size();i++) {
   removeEdge(edges[i]);
}

//find vertices that are never disconnected
//use DFS or BFS
foreach vertex reachable from S
{
   outputMap[vertex] = -1;
}

//walk through the edges backward, reconnecting
//the graph
for (int i=edges.size()-1; i>=0; i--)
{
    Vertex v1 = edges[i].v1;
    Vertex v2 = edges[i].v2;
    Vertex newlyConnected = null;

    //this is for an undirected graph
    //for a directed graph, you only test one way
    //is a new vertex being connected to the source?
    if (outputMap.containsKey(v1) && !outputMap.containsKey(v2))
        newlyConnected = v2;
    else if (outputMap.containsKey(v2) && !outputMap.containsKey(v1))
        newlyConnected = v1;

    if (newlyConnected != null)
    {
        //BFS or DFS again
        foreach vertex reachable from newlyConnected
        {
            //It's easy to calculate the desired remove iteration number
            //from our add iteration number
            outputMap[vertex] = edges.size()-i;
        }
    }
    addEdge(v1,v2);
}

//generate output
foreach entry in outputMap
{
    if (entry.value >=0)
    {
       print("vertex "+entry.key+" disconnects in iteration "+entry.value);
    }
}

このアルゴリズムは、ソースに接続される前に、各頂点が単一の BFS または DFS にのみ関与するため、線形時間を達成します。

于 2015-11-07T20:20:52.560 に答える
1

時間を逆転させるのに役立つので、エッジを 1 つずつ追加して、ソースへの接続がいつ達成されるかを判断することを考えています。各ステップの後にトラバーサルを実行するというあなたのアイデアは良いものです。総コストを線形に下げるには、次の最適化と償却分析が必要です。最適化は、トラバーサルからトラバーサルへと訪問した頂点のセットを保存し、そのセットを 1 つの「スーパーバーテックス」として扱い、トラバーサル時にセット内のエッジを削除することです。各トラバーサルのコストは、このように削除されたエッジの数に比例するため、償却された線形実行時間になります。

于 2015-11-07T18:15:53.480 に答える