链式前向星

ⓖⓞⓞⓢⓔ

2025-08-19 17:31:12

发布于：浙江

32阅读

0回复

0点赞

链式前向星

历史故事

在算竞的远古时代，那时的 $STL$ 容器还是个蒟蒻的时候，邻接表（指的不是vector邻接表）是当时世界上效率最高但是不好写的存储图的数据结构，但一些特别边台的题目会存在卡内存导致无法AC的情况。
这个时候以为伪人站出来了， $TA$ 就是链式前向星。如果说邻接表效率高但会被卡，邻接矩阵好写但效率低的情况下前向星就是一个相对于邻接表和邻接矩阵来说比较中性的数据结构。但一开始前向星~~也是个蒟蒻~~，效率并不高，而在别申必人优化成链式前向星后，效率就得到了加大的提升。

浅谈链式前向星

在介绍链式前向星之前，我们来看看图

如果用邻接表来存储我们会得到这个表格

点	第一个与其相连的点	第二个与其相连的点	第三个与其相连的点	第四个与其相连的点
1	3	4	5	NULL（无）
2	5	4	NULL（无）
3	NULL（无）
4	5	NULL（无）
5	NULL（无）

链式前向星存储图的方式和邻接表很像，也是以一种链表的形式存储的，但邻接表存储的是点，而链式前向星存储的是边。

例如：存点 $1$ 是就会存储 ${ 1,2,6 }$ 这几条边（如图）

那就会得到这张表

点	第一条相连的边	第二条相连的边	第三条相连的边	第四条相连的边
1	1	2	6	NULL（无）
2	3	4	NULL（无）
3	NULL（无）
4	5	NULL（无）
5	NULL（无）

链式前向星有一个 $head[]$ 数组，其作用是存储以该节点作为起点的所有边。

具体来讲，就是把从每个节点 $u$ 出发的边用链表链起来，这样只要记录 $head[u]$ 表示节点 $u$ 边表的第一条边是谁就可以了。

即下表

点	第一条相连的边	第二条相连的边	第三条相连的边	第四条相连的边
u	head[u]	next[head[u]]	next[next[head[u]]]	next[next[next[head[u]]]]

如果没有相连的边就写 $NULL$ ，通常写一个取不到的数，如： $-1145141919810$ ？

具体实现

首先我们要有一个边的结构体，因为我们存储的是边，所以我们要有：
- 记录这条边指向的点 $togo$
- 边表中下一条边的编号
- 这条边的权值 $w$ (最后一个看题目)

struct edge{
    int togo;
    int next;
    int w;
}edg[10086];

然后我们要有一个添加边的函数

int cnt=0;
void add(int u,int v,int w){
    cnt++;
    edg[cnt].togo=v;
    edg[cnt].w=w;//看题目
    edg[cnt].nect=head[u];
    head[u]=cnt;
}

$cnt$ 是用来给边编号的

在有了一个如此优秀的加边函数后，我们就可以轻松的读入边了

int n,m;//m个边，n个点
cin>>n>>m;
for(int i=1;i<=n;i++){
    int u,v,w;
    cin>>u>>v>>w;
    add(u,v,w);
    //如果是无向边的话就再加个add(v,u,w);
}

点邻边的遍历

在图被建立好后，我们只需要读取每个节点 $u$ 的 $head[u]$ ，即从节点 $u$ 出发的第一条边，之后循环查找下一条边，直到遇到 $NULL$
```
for(int i=head[u];i!=NULL;i=edg[i].next){
    ···
}
```

组合一下

#include <bits/stdc++.h>
using namespace std;
const int NULL= -1145141919810;
struct edge{
    int togo;
    int next;
    int w;
}edg[10086];

int head[10086];
int cnt=0;

void add(int u,int v,int w){
    cnt++;
    edg[cnt].togo=v;
    edg[cnt].w=w;//看题目
    edg[cnt].nect=head[u];
    head[u]=cnt;
}

int n,m;
int u,v,w;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int u,v,w;
    	cin>>u>>v>>w;
    	add(u,v,w);
    	//如果是无向边的话就再加个add(v,u,w);
	}
    for(int i=1;i<=n;i++)
        if(head[i])
            for(int j=head[u];j!=NULL;j=edg[i].next)
                cout<<i<<edg[j].togo<<edg[j].next;
        else 
            cout<<endl;
    return 0;
}

dfs 遍历图

遍历图就是需要记录每个点在当前递归中是否被走过。

void dfs(int u,int fa){
    ...
    for(int i=head[i];i!=NULL;i=edg[i].next)
        if(edg[i].togo!=fa && !vis[edg[i].togo]){
            // edg[i].to!=fa 一句若为无向图则需加上，防止死循环
            vis[edg[i].togo]=true;
            dfs(edg[i].togo,u);
            vis[edg[i].togo]=false;
        }
}

dfs遍历树

我们只需要在遍历点的邻边的基础上加上 $dfs$ 即可，函数中 $u$ 为当前节点编号， $fa$ 为父节点编号。无向图记得要需要判断下一个节点是否不为父节点。

void dfs(int u,int fa) {
    ...
    for(int i=head[i];i!=NULL;i=edg[i].next)
        if(edg[i].togo!=fa)  // 若为无向图则需加上，防止死循环
            dfs(edg[i].togo,u);
}

链式前向星与邻接表对比

在了解了链式前向星以后，我们需要了解我们为什么要用它（而不是使用邻接表）。

网上很多资料都有做过比较，比如说这样的：

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

据大佬@LeeCarry说： $vector$ 邻接表与链式前向星有内存性能上的差异，因为 $vector$ 扩充时是默认多申请2倍空间，所以一些特别变态的题目可能会卡内存只能用链式前向星写。他表示最近看 $STL$ 源码剖析， $vector$ 每次扩充都要复制一遍元素到新内存块，肯定会慢很多的。