用邻接表实现无向图 -- 算法 -- IT技术博客大学习 -- 共学习 共进步！

用邻接表实现无向图

   今天在扩展我们游戏中的管道系统时，又遇到了实现一个无向图的问题。

   之前的管道系统，每节管道的邻接管数量有限，所以我用了类似树的方式储存，在每节管道上直接放了一个固定大小的数组，保存该节管道的上下游节点。对于液体管道系统，这套数据结构工作的很好。

   今天，我们的另一个系统需要一个有点不一样的管道。它没有方向，每个节点可以有很多的邻接点。例如电线拉成的网络、导热管构成的网络，都是这样的。这是典型的无向图结构。

   我重新考虑了数据结构，用邻接表实现了一版。

   我把节点的数据和节点的邻接关系分开到不同的数据结构中，这样方便单独把管道连接模块独立出来复用。

   首先，用一个有序的数字 id 表示图中的节点。由于我们的图规模不会太大，16bit 的 id 就够用了。那么，相邻节点的连接关系就是图中的边，它可以用两个 id 连起来共 32bit 表示。由于是无向图，我们可以把较小的 id 固定在低位，这样边就有唯一的表示方法。

   btw, 如果需要扩展到有向图，则需要留一个 1bit 表示它是有方向的。

   如果不考虑访问效率，那么，只需要用一个数组把这些 32 bits 数据储存下来即可。（事实上，数据持久化时我只保存了这些数据，其它部分都可以快速重建）

   但是,运行过程中还需要快速的从一个节点检索到所有关联的边。以用来处理能量在网络中的流动。

   我在节点边对象上放了两个链表指向两个端点的边集合。所以，边的数据结构看起来就是这样的：

struct edge {
  uint16_t endpoint[2];
  uint16_t left;
  uint16_t right;
} ;

   另外有一个 uint16 数组指向每个节点的第一条边。如果某个节点一条边都不存在，它可以指向任意一条边（通常是 0）。因为边本身可以反过来校验是否临接节点。

   如果不需要快速动态增删边，还可以进一步压缩这个数据结构。每条边只需要 48bit 就够了。因为每条边只属于两个顶点，我们可以把其中一个顶点所属边的集合排列在一起，另一个集合用链表表示，这样就能省下 16bit 。

   这里还有一个小技巧表示链表的结束，那就是把两个端点的 id 反过来储存。（一般情况下，第一个端点 id 一定比第二个小）。

   例如有这样一张图：

1 - 2 - 3
|   |   |
4 - 5 - 6
|   |   |
7 - 8 - 9

   它由 12 条边构成，我们可以按次序排列这些边：

[0] (1,2) 2
[1] (4,1) 5
[2] (2,3) 4
[3] (5,2) 5
[4] (6,3) 7
[5] (4,5) 7
[6] (7,4) a
[7] (5,6) 9
[8] (8,5) a
[9] (9,6) b
[a] (8,7) b
[b] (9,8) b

1 : 0
2 : 0
3 : 2
4 : 1
5 : 3
6 : 4
7 : 6
8 : 8
9 : 9

   比如，想遍历 5 这个顶点的所有边，从下面的表查到它的第一条边在索引 3 的地方，也就是 (5,2) 5 。因为 5 比 2 大，所有第二条边在 index 5 ，也就是 (4,5) 7。因为 5 比 4 大，所以第三条边在 index 7 ，也就是 (5,6) 9。这次 5 比 6 小，且 5 在前面，所以第四条边就在后一项：(8,5) a 。8 和 5 是反的，这就是最后一项。

   到此，四条边都找出来了。

   我花了半天时间实现它。无向图在我的日常工作中不算常见，我只在读书时做习题时实现过。想到这样一个紧凑的数据结构还是挺满意的。实现完后又去 wikipedia 上查了一下，发现早有人提出过一个基本一样的想法了 :) 不过我后面那个压缩的方案不知道有没有前人实现过。