云风的 BLOG: 用邻接表实现无向图

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

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

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

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

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

首先，用一个有序的数字 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 上查了一下，发现早有人提出过一个基本一样的想法了 :) 不过我后面那个压缩的方案不知道有没有前人实现过。

Comments

好像graphhopper底层的图的实现和你这个很像。https://github.com/graphhopper/graphhopper

Posted by: zhiqiang zhao | (12) July 9, 2022 09:10 AM

CSS乱的问题，就是你web脚本没有设计好，设计web后台，CSS放在最开头，然后是HTML部分，尽量把js放在web面页的最末尾，这样就不会乱。 Dom就相当于win系统的explorer.exe

Posted by: rawa459 | (11) June 13, 2022 09:47 AM

我认为，这种图的结构在图形技术和显示引擎方面才有有意义，无论是什么结构，在内存中都是一个线性存储的结构，关键在与MMU的内存管理如何去快速的读写这些数据结构，并且这部分，跟寻址和MMU有很大的关系，X86在这方面是最先进的指令集。

Posted by: rawa459 | (10) June 13, 2022 03:49 AM

@leanfox 这个你完全使用NV的代码，你将来的技术如果市场化真的很有影响力，英伟达告你，你咋办？

Posted by: rawa459 | (9) June 13, 2022 02:52 AM

移动端 css 乱了

Posted by: 扑来树袋熊 | (8) June 12, 2022 11:43 PM

不可思议，什么游戏会用到这种类似互联网路由协议的复杂节点结构系统？

Posted by: rawa459 | (7) June 12, 2022 10:14 PM

https://github.com/NVIDIAGameWorks/Falcor/blob/master/Docs/Tutorials/03-Creating-and-Editing-Render-Graphs.md 用来表示passes还是挺直观的。

Posted by: leanfox | (6) June 8, 2022 12:04 PM

=。= 这是在做Render Graph么, 我这边很可耻的直接“参考”了nv家的实现。 https://github.com/NVIDIAGameWorks/Falcor/tree/master/Source/Falcor/RenderGraph 图相关的代码是 https://github.com/NVIDIAGameWorks/Falcor/blob/master/Source/Falcor/Utils/Algorithm/DirectedGraph.h

Posted by: leanfox | (5) June 8, 2022 11:56 AM

这种压缩方式确实有利于遍历，但我觉得小技巧可能没什么用。反正除了最后一条边以外，其它状况都要把下一条边读取出来，那比起先判断完才发现要读下一条，不如就直接取出来判断邻接还比较单纯。还可以在最后再加一条 (0,0) 的边，这样遍历到最后就一定会是不邻接的边，不用根据 id 大小关系来判断结束。储存边 [E1] (P1,P2) E2 的时候，把 P1,P2 这两点的大小顺序固定下来，读取的时候可以少一些判断，写起来比较省事。例如按照 P1这种压缩方式确实有利于遍历，但我觉得小技巧可能没什么用。反正除了最后一条边以外，其它状况都要把下一条边读取出来，那比起先判断完才发现要读下一条，不如就直接取出来判断邻接还比较单纯。还可以在最后再加一条 (0,0) 的边，这样遍历到最后就一定会是不邻接的边，不用根据 id 大小关系来判断结束。储存边 [E1] (P1,P2) E2 的时候，把 P1,P2 这两点的大小顺序固定下来，读取的时候可以少一些判断，写起来比较省事。例如按照 P1<P2 这个顺序，要找下一条边的时候，P1 的下一条边就是 E1+1，P2 的下一条边就是 E2。邻接则继续遍历，否则结束遍历。

Posted by: mingwei | (4) June 6, 2022 03:35 PM

我理解这个图的数据结构是将点和边分别存储在不同的数组或者数的结构中,然后在点或者边的结构体中引用对应的边或者点的信息,这样就既能快速遍历图中的点边又不会带来冗余

Posted by: kknd li | (3) June 6, 2022 11:19 AM

看了半天，这个压缩方法还是没看懂。。

Posted by: matcat | (2) June 3, 2022 02:47 PM

先辈留给我们的机会不多...

Posted by: chnleen | (1) June 2, 2022 11:07 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

用邻接表实现无向图

Comments

Post a comment