用邻接表实现无向图
这篇讲的是作者在游戏管道系统扩展中，如何用邻接表实现一个无向图数据结构。作者从原有的液体管道系统（采用类似树的固定数组存储）出发，面对电线网络等新需求——节点无方向且可多邻接，决定重新设计。核心思路是将节点id与边关系分离，便于模块化复用。具体实现上，每条边用32位紧凑表示（16位端点id对，小id在低位确保唯一性），并设计了一个巧妙的结构：在边数据中加入两个链表指针，分别指向两端点所属的边集合，从而支持高效遍历。 更精巧的是，作者进一步压缩了存储：通过将其中一端点的边集合连续排列，另一端以链表链接，并用“反转端点id”来标志链表结束（通常小id在前），最终每条边只需48位。文章以九宫格网格图为例，完整演示了如何从节点索引开始，逐步追踪并找出顶点5的全部四条邻接边。作者坦言这种无向图实现并非日常工作所需，但经过半天编码，能写出这样紧凑高效的结构让他颇为满意，其压缩方案甚至可能具有一定的原创性。