蒟蒻们往这里看！

链式前向星存图的讲解

先上代码：

//MAXN指的是最大边数
//MAXM指的是最大节点数
int cnt;
int head[MAXM];
//head[n]指的是 第n个节点存储的最后一条边地址，图全部存储完毕后均指向最后一条边
//并按最后地址 => edge[最后地址].nex => edge[edge[最后地址].nex].nex……进行遍历
struct ed{
	int to,nex;//to means 这条边指向的节点,nex means 放出这条边的节点的上一条边的存储地址； 
}edge[MAXN];
inline void add(int u,int v){//建图的函数，u指的是节点，
	cnt++;
	edge[cnt].to=v;//to 指向下一节点
	edge[cnt].nex=head[u];//nex 上一条边
	head[u]=cnt;//地址更新为本条边的存储地址
}

链式前向星是一种高效的存图方法，是基于存储“边”而不是邻接矩阵的存储“点与点”之间的关系，如果题目时间复杂度卡的紧没办法用邻接矩阵遍历，就可以试试这种方法，同时邻接矩阵也浪费了大量的空间，而链式前向星却可以在节省时间复杂度同时节省空间复杂度。

注意：链式前向星适合的存储有向图，对于无向图有可能造成空间复杂度过高！

思路梳理

正如代码中所说，它的主要思想便是：定义一个结构体，包含三个变量：

to：用于存储这条边所指向的节点

nex：用于存储与这条边同一出发节点的上一条边的存储位置（注意与节点位置不是一个概念！）

再定义一个head数组，这个数组就是在建图过程中用来记录该节点当前已建成的最后一条边的存储位置！在遍历图的过程中用于

存储位置：指的是edge数组的下标位置。存贮的是边集！

节点位置：指的是head数组的下标位置。

add(int u,int v)函数详解

add函数的主要作用是进行建图，注意该函数add的不是节点而是边！u是边的起始端，v是边的结束端。

实际上add函数的功能很简单，首先，将cnt++，这是要让cnt这个伪指针从上一个边集存储位置跳到下一个边集存贮位置，以便进行新边的存储。

第二句：主要作用便是让to指向下一节点也就是v

第三句：nex指向上一条边的存储位置，这是为了方便进行图的遍历。

第四句：既然head中的元素指的是存储位置，那么我们就应当在最后更新该节点存储位置，使其值为我们最新插入的这条边的存储位置，也就是cnt

所以，每输入一条边就运行一次add（），最后就能完整的存下整张图！

搭配食用：

out和in数组
这两个数组大小应当开到最大节点数，用于记录每个节点的入度和出度，防止进行不必要的遍历（主要是遍历in数组，若in[i]为零，则以此为基准开始链式前向星的遍历）

链式前向星的遍历

这里给出深搜遍历方法，仅仅是一个框架，若题目有特殊要求可以在其中加入数据处理。

void dfs(int now){
	if(!out[now])return;//遇到出度为零则代表遍历到头，结束遍历；
	for(int i=head[now];i;i=edge[i].nex){
		dfs(edge[i].to);
	}
}

其中，先令i=head[now],每次遍历都让i=edge[i].nex,即i=edge[head[now]].nex。

达到的效果是一个边一个边向前遍历，直到i=0循环结束

补充

由于head是全局变量，初始值是零，所以每个节点遍历完后edge.nex必然指向0，观察add函数即可得知。

结语

其实这个巧妙的方法我也是学了很久才学会，之前一度以为完全没法学，但最终还是攻克了，可见，蒟蒻并非一直是蒟蒻，神犇们也是由蒟蒻来的，所以大家共勉吧
逃