MicDZ's blog

为什么要用前向星存图?

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

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

这里只介绍链式前向星。

准备工作

head[x]是点的头指针

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

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

建立边表

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

加边的方法

1
2
3
4
5
6
7
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的头元素开始沿着链表遍历全图。

效率对比

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

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

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

代码提交

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

Update 2018.

 评论