链式前向星

链式前向星是类似于邻接表的存图方式，具有空间复杂度小，便于遍历等优点，不过无法快速判断两点间是否有边

前言

链式前向星是类似于邻接表的存图方式，具有空间复杂度小，便于遍历等优点，不过无法快速判断两点间是否有边

储存

实现原理

这种存图方式只需要开一个数组存储每个点引出的第一条边，然后存储每个点作为起点的每条边，这样就可以做到不重不漏。

在链式前向星存图中，我们需要定义一个结构体：

struct EDGE 
{
    int next;
    int to;
}edge[1000000];

和一个数组：

int head[1000000];

和一个变量：

int cnt=0;//指针

你会发现竟然没存起点！！其实起点是用$head$存的

实例：

如图：这样的一个有向图，输入是：

1 2
1 3
1 4
2 3

逐步分析：

1.输入1 2，代表1连向2。

cnt++;//作为结构体下标，没有意义
head[1]=cnt;//结点1的第一个儿子存在了edge[cnt]里面
edge[cnt].to=2;结点1的儿子是2

此时：
$cnt=1$

$edge$	$cnt=1$	$cnt=2$	$ cnt=3$	$cnt=4$
$to $	$2$	$0$	$ 0$	$0$
$next$	$ 0 $	$0 $	$0$	$0$

$head $	下标$=1 $	下标$=2$	下标$=3 $	下标$=4 $
值	$1 $	$ 0 $	$ 0 $	$ 0 $

2.输入1 3，代表1连向3。

cnt++;
head[1]=cnt;
edge[cnt].to=3;结点1的儿子是3
//这时,3成为了结点1的儿子，不过2被挤了下去...
//所以要引入结构体中next元素，记录：3还有个兄弟（next）是2
//所以代码要换成：
cnt++;
edge[cnt].to=3;//结点1连向3
edge[cnt].next=head[1];//3的兄弟是2
head[1]=cnt;//更新head

此时：
$cnt=2$

$edge$	$cnt=1$	$cnt=2$	$ cnt=3$	$cnt=4$
$to $	$2$	$3$	$ 0$	$0$
$next$	$ 0 $	$1 $	$0$	$0$

$head $	下标$=1 $	下标$=2$	下标$=3 $	下标$=4 $
值	$2 $	$ 0 $	$ 0 $	$ 0 $

3.输入1 4，代表1连向4。

此时：
$cnt=3$

$edge$	$cnt=1$	$cnt=2$	$ cnt=3$	$cnt=4$
$to $	$2$	$3$	$ 4$	$0$
$next$	$ 0 $	$1 $	$2$	$0$

$head $	下标$=1 $	下标$=2$	下标$=3 $	下标$=4 $
值	$3 $	$ 0 $	$ 0 $	$ 0 $

4.输入2 3，代表2连向3。

此时：
$cnt=4$

$edge$	$cnt=1$	$cnt=2$	$ cnt=3$	$cnt=4$
$to $	$2$	$3$	$ 4$	$3$
$next$	$ 0 $	$1 $	$2$	$0$

$head $	下标$=1 $	下标$=2$	下标$=3 $	下标$=4 $
值	$3 $	$ 4 $	$ 0 $	$ 0 $

注意：$edge[cnt].next$ 和$head[1]$存贮的都是结构体下标（即$cnt$的值）若要访问指向的边的编号，分别用$edge[edge[cnt].next].to$，$edge[head[1]].to$

若需要记录权值，在结构体中加入一个元素即可

代码：

带权值：

#include<iostream>
using namespace std;
struct edge 
{ 
    int next;
    int to;
    int wei;
}edge[MAXM];
int head[MAXN];//head[i]为i点的第一条边
int cnt=0;
void addedge(int u,int v,int w) //起点，终点，权值 
{
    edge[++cnt].next=head[u];//更新cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}
int main()
{
	int n;
    for(int i=1;i<=n;i++)
    {
    	int a,b,wei;
        addedge(a,b,wei);
        //如果是无向图，还要addedge(b,a,wei);
    }
}

注意：

这里的$next$指的是遍历时的下一条边，$head$指的是遍历时的第一条边，而存边时相当于反过来操作，所以$next$记录上一条边，而$head$记录最后一条边。

---

边的遍历

在遍历以x为起点的所有边时，只需要这样就行

for(int i=head[x];i;i=edge[i].next)

这个循环的结束条件是$i$等于$0$，因为最后一条边，也就是存边时第一条边，在把$head$值存进$next$时，$head$还没有更新过，也就是$0$。所以当$next$返回$0$时，就说明这些边遍历完毕了。

---

优势与特点

既可以存图，也可以存树，比起邻接矩阵，链式前向星的空间复杂度是$O(n)$,大大节省了存储空间，因为按边存储省掉了很多两点无边的空间。并且在遍历的时候，那些与起点无边相连的点也不需要进行处理，可以说时间和空间都占优势，这就是被OIer们广泛使用的原因。

补充+技巧

（$2019/1/15 update$）

void addedge(int u,int v,int w) //起点，终点，权值 
{
    edge[++cnt].next=head[u];//更新cnt
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt;
}

这个代码中，$cnt$代表边的编号。

如果$cnt$初始值赋为$1$,存的是无向图，那么：

边$cnt$的反向边是$cnt$^$1$