链式前向星理解

大家好，欢迎来到IT知识分享网。

    在初学数据结构时，“如何存边”或许是大部分Oier关注的事情。我在最初学时，常常使用邻接矩阵存图，8000*8000已经是极限，这意味着我所能处理的图，点的最大规模也只能在10000左右。

    这种存图方式的最大弊端在于，它虽然查找两点之间是否有边是O（1）的，但无论是从一个点开始走它所连的边的O（n）的时间复杂度，还是存图的空间复杂度，都无法满足我们的更高要求。我们不妨思考一下，倘若我们的目的是能够更优地遍历整张图，那我们需要哪些关键信息？

    事实上，我们只需要知道，我在哪儿？我可以往哪里走？（我会到哪？）。邻接矩阵在某种程度上达到了这种要求，但显然浪费较大（对于这个单一目的而言）。

    接下来，我们开始面向需求设计所需的结构。

    对于一条边，它能给我们提供的消息有它的起点、终点，可能还有它的权值等等一些数据。我们不妨模拟一下，倘若我现在就站在一个点上，我此刻必然需要一条边，一个方向的指引。我们用head数组来存储它，具体来说，head[u]存放的是：如果你在u点，你该向哪走，显然，他所保存的是一个边的编号。

    接下来考虑一个问题，边的编号如何指引方向？我们应该建立一个ver数组，让它来负责记录编号为i的边会将我导向哪里。

    概括说来，现在我们的方案是：到达一个点，通过head知道该走的边，通过ver知道下一个点的位置，一直走下去。

    如果我们面对的是一条链，那我们的问题已经宣告解决，但是，一个节点倘若连有好几条边，那我们的head数组便力不从心了。大家可能会想到用一个vector存放每个点作为起点时出边的编号，但链式前向星提供了一个更好的解决方案。

    链式前向星为何是“链式”？我个人以为，就是对其存边方式的一种暗示。head数组只能存一条边，那就让它存一个“端点边”，同一起点的边环环相扣，访问head数组就犹如提起了一个端点，也就拎起了所有以u为起点的出边。具体来说，我们让head[u]存放从u节点出来的最后一条边，这条边可不简单，它一方面要提供出去的方案，另一方面，还得连着另一条兄弟边（从u出来的边）。我们用next数组来描述这个关系，next[i]就是i这条边的兄弟，具体来说，就是从u出去的边i的上一条边。这样，我们的方案就可以愉快地加上“走完head[u]直接告诉我们的这条边i后，走这条边连着的兄弟边next[i]”。

    至此，我们便顺利的建立了一种更优的数据结构，来处理我们的问题。