1
マルチグラフの隣接リストG =（V、E）と等価（単純）な無向グラフの隣接リストを計算するためのO（V + E）アルゴリズムを見つける必要があります。multigraphの隣接リストが与えられた場合、O（| V | + | E |）時間内の等価（単純な）無向グラフの隣接リストを計算する
私は（それが故に私の再投稿質問セクションの一部であった）別のポストでは、次の解決策を見つけた：
「[H]サイズの配列をAVING | V |となっている頂点をマークするようにadj [u]に少なくとも1回遭遇し、重複を防止します。配列は、各adj [u]を横断する前にリセットされます。
私の無知を許しますが、これがどのようにO（| V | + | E |）であるか分かりません。長さをリセットするコストはどれくらいですか| V |配列| V |時間？
ありがとうございます。
あなたがリセットとして考えるものによって異なります。新鮮なメモリを割り当てて古いものを削除して、0のすべての値を上書きして古い値を無視して0に書き始めることができます。引用にはこれを判断するコンテキストがありません。また、実行時の複雑さに関する主な問題は、**何が測定されるか（通常は最も高価な操作ですが、ここではかなり曖昧です）に大きく依存するということです。 – Paul
こんにちは@Paul。複雑さの要件を満たすことができる「再設定」の解釈について考えてみませんか？私は古い値を無視することはできないと思っています... – tarski
設定されている頂点のリストを保持しておけば、それらの配列の位置だけをリセットすることができます。セットのコストに一定の要素があります。もう1つの方法は、整数値に設定することによって配列内の位置を設定し、各トラバースでその整数値をインクリメントし、現在の値より小さい値に設定された位置を未設定として扱うことです。 – mcdowella