前向星存图

为什么要用前向星存图？

前向星可以很方便地读取点的出边，在某些图论算法（如SPFA）中可以做到很低的复杂度

FlyuZ：邻接表是用链表实现的，可以动态的增加边，而前向星是用结构体数组实现的，是静态的，需要一开始知道数据范围，开好数组大小。相比之下，邻接表灵活，但链式前向星好写。

这里只介绍链式前向星。

这是一篇原始文章，不保证内容的正确性

准备工作

head[x]是点的头指针

next[i]是链表的下一个元素

to[i]是这一个点所到达的边，e[i].v是这条边的权值

建立边表

1	int head[MAXN],to[MAXN],next[MAXN],weigh[MAXN];

加边的方法

void add(int u,int v,int w){
	cnt++;//cnt可以理解为当前加入这条边的编号
	to[cnt]=v;//这条边指向了v，可以这么理解，所有邻接表中只有to会指向点的编号
	next[cnt]=head[u];//将当前边的的下一条边指向u的头指针
	head[u]=cnt;//更新u的头指针
	weigh[cnt]=w;//记录边权
}

原理

cnt记录的是当前点的序号，后面所有的操作都是在cnt内的。

将cnt的边的终点指向v。

将下一个元素连到起点u的头指针并更新u的头指针。

最后记录边权，这一步可有可无。

遍历的方法

1
2
3

for(int i=head[now]; i!=0; i=next[i]) {
	//Do something
}

从now的头元素开始沿着链表遍历全图。

效率对比

方式	查询（出边）	插入
邻接矩阵	$\Theta(n)$	$\Theta(1)$
前向星	$\Theta(k)$	$\Theta(3)$

注：上图中的k指的是所连出边，n是指点的个数

也就是说，如果在一个完全图（任何一点与所有点都有连边）中，邻接表与邻接矩阵几乎是一样的。

代码提交

GYOJ提供了模板数据，具体参照here

Update 2018.

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。