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

Question

<分区>

Answer 1

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

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