如何将外邻接表转换为内邻接表？

Question

对于有向图G= (V，E)。该表示维护一个数组A...以V为索引，其中Av为链表。链表保存v所指向的所有节点u的名称，即(v，u)链表E (从技术上讲，Av包含指向链表中第一项的指针)的节点u的名称。.This是缺省邻接列表格式，并且可以被认为是out- adjacency∈表示

in-adjacency列表表示将是其中Av是指向v的节点的列表。

谁能给我一个O(|V | + |E|)算法的伪代码，把外邻接列表表示转换成内邻接列表表示。请解释为什么你的算法是正确的，为什么它在O(|V |+ |E|)时间内运行。

Answer 1

您可以在O(V + E)中执行此操作，但为此，您必须将链表中的insert操作修改为在固定时间的O(1)中完成。

这很容易做到，只需保留一个单独的指针last，其中last指向链表中插入的最后一个元素。在last的帮助下，链表的插入操作可以在O(1)中完成，而不是通常的O(N)。

现在来看问题，假设我们的新adjacency list是adj_new。我们首先从第一个链表开始遍历原始的adjacency list。

对于链表A[0]的每个元素x，我们执行插入操作：

insert 0 in linked list adj_new[x]

我们对每个链表执行上述操作。因为遍历整个邻接列表需要时间

O(V + E)，每次插入操作占用O(1)时间，总耗时为O(V + E)

伪代码如下：

For each linked list A[i]
{
 for each element x of A[i]
 {
  append i to linked list adj_new[x]
 }
}

adj_new[]是邻接列表。如果你仔细观察，它只是颠倒了你有向图的每一条边的方向。