圖算法從鄰接表中刪除重複的頂點和自循環

Question

給定一個有向多圖的鄰接表表示是否有O（V + E）算法將其轉換爲無向簡單圖？該算法明顯應該使用最小的空間。

Answer 1

[編輯2013年6月5日：治療[]一致地作爲2D陣列。]

是，提供列出的每個鄰接內的頂點是按排序順序，並且可以存在至多一個邊緣在一對頂點之間。假設頂點的第j個孩子，我是一個[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個排序的子序列 - 孩子頂點的原始列表（與任何更高的頂點被刪除），可能後跟一個從頂點的鄰接表中追加的頂點列表。第二個序列的開始可以通過查找比前一個元素小的第一個元素在線性時間中找到;如果找到，則可以使用相同大小的緩衝區以線性時間合併這兩個子序列（或者使用沒有額外空間的對數線性時間進行排序，或者使用桶排序和對數額外空間以線性時間排序）。沒有鄰居可以出現兩次以上，並且任何重複的都可以在合併期間被移除。