0

有向マルチグラフの隣接リスト表現が与えられた場合、それを無向の単純なグラフに変換するためのO（V + E）アルゴリズムはありますか？アルゴリズムは明らかに最小限のスペースを使用する必要があります。

4

1 に答える 1

1

[2013 年 6 月 5 日編集: a[] を一貫して 2D 配列として扱います。]

はい、リストされている各隣接内の頂点がソートされた順序であり、頂点のペアの間に最大で 1 つのエッジがある場合に限ります。頂点 i の j 番目の子が a[i][j] であるとします。

# First make sure each edge appears only in the lower endpoint's adjacency list.
# We don't care if this duplicates vertices in a list.
For each vertex i:
    j = 1
    For each k from 1 to len(a[i]):
        a[i][j] = a[i][k]
        If a[i][k] > i:
            j = j + 1        # Only save space for edges to higher vertices

        If a[i][k] < i:
            Append i to a[a[i][k]]

    Adjust len(a[i]) to j - 1

この時点で、すべての隣接リストは、最大 2 つのソートされたサブシーケンスで構成されます。元の子頂点のリスト (上位の頂点は削除されます) の後に、上位の頂点の隣接リストから追加された親頂点のリストが続く可能性があります。2 番目のシーケンスの開始は、前の要素よりも小さい最初の要素を探すことによって線形時間で見つけることができます。見つかった場合、2 つのサブシーケンスは、同じサイズのバッファーを使用して線形時間でマージできます (または、余分なスペースを使用せずに対数線形時間でソートするか、バケット ソートと対数余分なスペースを使用して線形時間でソートします)。ネイバーは 2 回以上出現できず、重複しているものはマージ中に削除できます。

于 2012-10-10T21:04:17.907 に答える