目录

静态链表(链式前向星)- 表示图的另一种方法


静态链表是一种用数组静态储存的数据结构。它通常用来表示图。它还有个非常有趣的名字叫“链式前向星”。你可以通过以下两种方式来了解它:

但是我还是建议两种都了解一下啦。如果你知道其中一种或两种的吧,点这里跳过。点一下,玩一年。

在本文中,让u表示边从该节点出发,v表示边到达该节点。

前向星

前向星也叫做领接数组,边集数组。我们先把所有的边按照出发节点排序,到达节点的顺序不重要。接着分别用两个数组,一个存节点的在边数组的下标,一个存改节点的出度(有多少条边从该节点出发)。

范例

/static-linked-list/static_linked_list_example.png

我们的图包含如下这些边(出,入):

1
2
3
4
5
6
7
(1, 2)
(2, 4)
(3, 4)
(1, 3)
(4, 3)
(3, 2)
(1, 4)

我们首先以出发节点进行排序然后填入数组:

  • es[]: 所有的到达节点

  • head[]: 以u为起点的第一条边的位置

  • len[]: u的出度(从该节点出发的边的数量)

1
2
3
4
5
6
7
8
9
(1, 2) --|
(1, 3) --| => len[1] = 3
(1, 4) --|
(2, 4)
(3, 2) => head[3] = 5
(3, 4)
(4, 3)
    ^
  es[]
Array1234567
es2344243
head1457
len3121

下面我们来看如何取得所有从节点1出发的所有边。我们可以用head[1] == 1来找到第一条边在es[]中的位置是1。然后从head[1]head[1]+len[1]遍历es[],得到es[1+0] == 2, es[1+1] == 3, es[1+2] == 4。这样我们就得到了边(1,2), (1,3), (1,4)。

1
2
3
4
// 找到所有从u出发的边
for (int i = 0; i < len[u]; i++) {
    cout << u << " " << es[head[u]+i] << endl;
}

因为前向星需要进行一次排序操作,时间复杂度提升到了$ O(E \times log(E)) $, 所以前向星并不是非常常用。然而链式前向星避免了排序,就解决了这个问题。

领接表

领接表在C++中通常用vector<int> G[MAXN_V]来实现。G[u]指向一个包含所有从u出发的边的vector。

范例

/static-linked-list/static_linked_list_example.png

最后的结果如下图所示,左边的数组表示G[]。当我们读入一条从u出发的边,就推入G[u]的vector.

/static-linked-list/static_linked_list_list.png

1
2
3
for (int i = 0; i < G[u].size(); i++) {
    cout << u << " " << G[u][i] << endl;
}

链式前向星

链式前向星是前向星的改进版本,也可以说是领接表的静态版本。它不用像前向星那样进行排序。它是怎么做到的?不停地戳自己!:)

范例

我们和上文使用相同的范例。

static_linked_list_example.svg

有如下边(出发,到达):

1
2
3
4
5
6
7
8
9
(1, 2)
(2, 4)
(3, 4)
(1, 3)
(4, 3)
(3, 2)
(1, 4)
    ^
   es[]

我们开始构造数组:

  • es[]: 所有的到达节点v,出发节点的信息会在head[]中储存。

  • head[]: 以u为起点的第一条边的位置。

  • next[]: 下一条以u为起点的边在es[]中的位置。用0来代表已经是最后一条了。

可以得到

Array1234567
es2443324
head1235
next4067000

我们需要另一个数组储存每个节点最后一条边的位置来构造next[]数组。当然我们也可以反向构造,不断更新head[]来储存。

下面我们来看如何得到从节点1出发的所有边:

  1. head[1] == 1来找到第一条边的位置,设i = head[1]es[i] == 2输出了(1, 2)这条边,更新 i = next[i],现在i == 4

  2. es[i] == 3 输出边(1, 3),更新i = next[i],现在i == 7

  3. es[i] == 4 输出边(1, 4),更新i = next[i], 现在i == 0

  4. 因为i == 0,结束。

1
2
3
for (int i = head[u]; i; i = next[i]) {
    cout << u << " " << es[i] << endl;
}

发现了吗?链式前向星除了第一次使用head[],其他时候都在es[]next[]之间左右横跳来得到下一数据。想法和链表很像,不过用的是数组实现的。

比较

前向星$O(E \times log(E))$的复杂度让人望而却步,有时候可能会变得更糟。

领接表易于理解,用C++ STL vector也易于实践。vector动态分配空间所以我们不用知道边的数量。但是,有时候可能会浪费空间因为vector在需要的时候会加倍分配空间。

链式前向星不改变数组的顺序,它只是建立起了边之间的关系。它比使用STL更快而且在理解之后易于实现。

但是,这些数据结构都在寻找一条特定的边的时候不太优秀,在最坏情况下需要遍历到链表结束。