algorithm - 从邻接表表示中删除重复顶点和自环的图算法

Question

给定有向多重图的邻接表表示，是否有 O(V+E) 算法将其转换为无向简单图？该算法显然应该使用最小的空间。

Answer 1

[编辑 6/5/2013：将 a[] 始终视为二维数组。]

是的，只要列出的每个邻接中的顶点按排序顺序排列，并且在一对顶点之间最多可以有一条边。假设顶点 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 个已排序的子序列 - 子顶点的原始列表（删除了任何更高的顶点），可能后面是从更高顶点的邻接列表附加的父顶点列表。通过寻找小于前一个元素的第一个元素，可以在线性时间内找到第二个序列的开始；如果找到，这两个子序列可以使用相同大小的缓冲区在线性时间中合并（或者在不使用额外空间的情况下以对数线性时间排序，或者使用桶排序和对数额外空间在线性时间中排序）。任何邻居都不能出现超过两次，并且任何重复的都可以在合并期间删除。