干货分享｜图论的常见存储方式之链式前向星

链式前向星示意图链式前向星的代码非常模板话但是在初学截断单看代码很难理解其中的原理。下面着重对第 1 步和第 4 步的建图进行阐述设为 0。选取最近未使用的边的空间此时边号 idx02 有一条权值为 3 的边。选取最近未使用的边的空间此时边号idx0在 idx0 处存储入度点 2 和权值 3将 idx0 处 nex 位置存为 head[0]-1将 head[0] 更新为当前的边号 idx0第 4 步[0, 3, 5] 表示 0 到 3 有一条权值为 5 的边。选取最近未使用的边的空间此时边号 idx 3在 idx3 处存储入度点 2 和权值 3将 idx3 处 nex 位置存为head[0]0 (注意这是第 1 步时存储的值)将 head[0] 更新为当前的边号 idx3由于 head 数组始终指向最后存储的位置。因此在遍历 head[from] 时与存储的顺序时相反的。而邻接表在遍历时与存储顺序一致聪明的读者应该已经发现了其实链式前向星就是另一种表现形式的邻接表。数据结构struct Edge { int to; // 入度点 int val; // 权值 int nex; // 下一个节点 }; Edge edge[边数]; int head[点数]; int tot 0; // 使用到了第几条边操作// 添加边 void addEdge(int from, int to, int value) { // 根据tot的初始值确定使用的第一条边的边号 tot 1; edge[tot].to to; edge[tot].val value; edge[tot].nex head[from]; head[from] tot; } // 遍历 for (int i head[from]; /*根据head初始值作为终止条件*/; i edge[i].nex) { int to edge[i].to; int val edge[i].val; }