線形時間でグラフを逆転させるには？

Question

グラフを表現する方法は2つあります.1つは行列を使用し、もう1つはリストを使用することです。

私が行列を使用する場合、行列のすべてのビットを反転する必要があります。それはO（V^2）時間かかりませんか？

私はリストを使用している場合は、私は、一つ一つがそれぞれのリストを横断して、新しいセットを作成する必要はありませんでしょうか？それは直線的なO（V + E）時間を取るように思われる。私は正しいですか？

私はここで別の質問があります。たとえば、グラフ（マトリックスまたはリストのいずれか）にDijkstraアルゴリズムを使用し、シーンの背後にあるデータ構造に優先キューを使用するとします。グラフの表現とデータ構造の関係はありますか？それはアルゴリズムのパフォーマンスに影響を与えますか？

私が表現してダイクストラアルゴリズムのための優先順位キューのリストを使用していたと仮定し、ダイクストラのための行列と利用プライオリティキューの違いがあるでしょうか？

私はそれだけでmakeQueue操作に関連すると思いますか？それとも全く違うのではないでしょうか？

Answer 1

は線形時間で行うことができます。グラフを1回だけトラバースします。複雑さの順序はO（| V | + | E |）になります。

1. キーが頂点ラベルで、値がキー頂点の隣接する頂点のArrayListである、AdjacenyリストのHashMapを維持します。
2. 逆の場合、同じ種類の新しいHashMapを作成します。元のハッシュマップをスキャンし、見つかったキーごとに対応するリストをトラバースします。値リストにある各頂点について
3. 、新しいハッシュマップ内の新しいキーに対応するArrayListの中にエントリとして元のハッシュマップのキーを入れ、新しいハッシュマップにキーを追加します。

public static HashMap<Character,ArrayList <Character>> getReversedAdjLists(RGraph g) 
{ 
    HashMap <Character, ArrayList<Character>> revAdjListMap = new HashMap <Character, ArrayList<Character>>(); 
    Set <Character> oldLabelSet = g.adjListMap.keySet(); 

    for(char oldLabel:oldLabelSet) 
    { 
     ArrayList<Character> oldLabelList = g.adjListMap.get(oldLabel); 

     for (char newLabel : oldLabelList) 
     { 
      ArrayList<Character> newLabelList = revAdjListMap.get(newLabel); 

      if (newLabelList == null) 
      { 
       newLabelList = new ArrayList<Character>(); 
       newLabelList.add(oldLabel); 
      } 
      else if (! newLabelList.contains(oldLabel)) 
      { 
       newLabelList.add(oldLabel); 
      } 

      revAdjListMap.put(newLabel, newLabelList); 
     } 
    } 

    return revAdjListMap; 
} 

Answer 2

グラフを反転させるには、O（V ）が必要です。なぜなら各頂点について、（V-1）個のエッジを追加または削除する必要があるからです。

Dijkstraのアルゴリズムについては、グラフを行列またはリストとして表現するとO（V ）が必要ですが、他のデータ構造も高速です。最も速く知られているのは、O（E + VlogV）を与えるフィボナッチヒープです。有向グラフの隣接リストを逆