开始学习数据结构时，“如何存储边缘”可能是大多数Oier关注的事情。 我最初经常使用邻接矩阵保存图。 8000*8000是极限。 也就是说，我能处理的图，点的最大规模也只有10000左右。
这种内存映射方案的最大缺点是，检查两点之间的边是否为o[1]，但无论是从一点到连接边的o[n]的时间复杂度，还是内存映射的空间复杂度，都不能满足我们更高的要求。 如果我们的目的是能够更好地穿越整个图的话，请考虑一下需要什么样的重要信息。
其实，我们只知道，我在哪里？ 我可以去哪里？ 你要去哪里？ 请参阅。 邻接矩阵在一定程度上满足了这样的要求，但显然浪费很大(对这个单一目的来说)。
接下来，我们开始根据需求设计必要的结构。
对于一条边，它可以提供的信息可能有其起点、终点及其权重等几个数据。 让我们来模拟一下。 如果我现在就站在一个点上，我现在一定要有一边、一个方向的指引。 我们用head数组保存那个。 具体来说，head[u]很明显他保存了边上的号码，如果你在u点，该去哪里。
接下来考虑一个问题。 边上的号码怎么指引方向？ 我们应该创建ver数组，负责记录它在编号I的边缘将我引向何处。
总之，现在我们的方案是，到达一个点，用head知道应该去的边，用ver知道下一个点的位置，然后直走。
如果我们面临的是一个连锁，那么我们的问题已经宣告解决，但是如果一个节点有好几个边，我们的head数组就不能发力。 你可能会想象用一个向量保存以每个点为起点时的边缘编号，链式前星提供了更好的解决方案。
链式前向星为什么是“链式”？ 我个人认为这是对其生存方式的暗示。 因为head数组只能保存一条边，所以保存“端点边”。 同一起点的边由一个环连接起来，访问头阵列就像抬起端点一样，它抬起以u为起点的所有边。 具体来说，我们让head[u]保管从u节点出来的最后一边。 这一带不简单。 一方面它提供了出去的方案，另一方面它必须连接到另一个兄弟边(从u出来的边)。 用next数组编写此关系。 next[i]是一个叫I的边的兄弟，具体来说是从u出来的边I的上一条边。 这样，我们的方案就可以愉快地添加“走完head[u]直接告诉我们的这一边I后，跟在这一边的兄弟边next[i]”。
至此，我们顺利构建了更好的数据结构来处理问题。