链式前向星

目录

一、前言

二、链式前向星

三、优缺点

---

一、前言

链式前向星在我的上一篇文章“拓扑排序板子练习”中就已经用到了，敲这篇文章主要是想尽量准确地解释什么是链式前向星，以及其模板、作用是什么，经常用在哪些类型的题等等。

二、链式前向星

百度百科：

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。

假如我们要找出一条a -> b的边，先根据head[a]找出从起点a出发的所有边里最新录入的那条边，然后根据该边找出它的上一条边，再根据上一条边找出它的上上一条边……直到找到一条终点为b的边为止。整个过程是链式回溯的，所以是链式前向星。

链式前向星其实就是静态建立的邻接表，时间效率为 O(m)，空间效率也为 O(m)，遍历效率也为O(m)。对于下面的数据，第一行 5 个顶点，7 条边。接下来是边的起点，终点和权值。

5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7

链式前向星存的是以【1~n】为起点的边的集合，对于上面的数据输出就是：

1 //以1为起点的边的集合
1 5 6
1 3 4
1 2 1
 

2 //以2为起点的边的集合
2 3 2
 

3 //以3为起点的边的集合
3 4 3
 

4  //以4为起点的边的集合
4 5 7
4 1 5
 

5 //以5为起点的边不存在

我们先对上面的7条边进行编号，第一条边的编号是0，以此类推编号【0~6】，然后我们要知道两个变量的含义：

• next，表示与这个边起点相同的上一条边的编号。
• head[ i ]数组，表示以 i 为起点的最后一条边的编号。

 head数组一般初始化为-1，为什么是 -1呢？自己用脑子想一想。

加边函数是这样的：

struct Edge{
	int to;
	int w;
	int next;
} edge[MAXN];   //边集
 
int head[maxn];
 
void Add(int u, int v, int w){   //u起点，v终点，w边权
    edge[cnt].to = v;  //终点
    edge[cnt].w = w;  //权值
    edge[cnt].next = head[u]; //以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++; //更新以u为起点上一条边的编号
}

我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：

对于1 2 1这第0条边：edge[0].to = 2;     edge[0].next = -1;      head[1] = 0;

对于2 3 2这第1条边：edge[1].to = 3;     edge[1].next = -1;      head[2] = 1;

对于3 4 3这第2条边：edge[2].to = 4;     edge[2],next = -1;      head[3] = 2;

对于1 3 4这第3条边：edge[3].to = 3;     edge[3].next = 0;       head[1] = 3;

对于4 1 5这第4条边：edge[4].to = 1;     edge[4].next = -1;      head[4] = 4;

对于1 5 6这第5条边：edge[5].to = 5;     edge[5].next = 3;       head[1] = 5;

对于4 5 7这第6条边：edge[6].to = 5;     edge[6].next = 4;       head[4] = 6;

遍历函数是这样的：

for(int i = 1; i <= n; i++) {  //n个起点
    cout << i << endl;
    for(int j = head[i]; j != -1; j = edge[j].next) {  //遍历以i为起点的边
        cout << i << " " << edge[j].to << " " << edge[j].w << endl;
    }
    cout << endl;
}

第一层 for 循环是找每一个点，依次遍历以【1~n】为起点的边的集合。第二层 for 循环是遍历以 i 为起点的所有边，j 首先等于head[ i ]，注意 head[ i ] 中存的是以 i 为起点的最后一条边的编号。

然后通过 edge[ j ].next 来找下一条边的编号。我们初始化 head 为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的 edge[ j ].next 为 -1 做为终止条件。

链式前向星模板：

#include
using namespace std;
const int maxn = 1005;//点数最大值
int n, m, cnt;//n个点，m条边
struct Edge
{
    int to, w, next;//终点，边权，同起点的上一条边的编号
}edge[maxn];//边集
int head[maxn];//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
void init()//初始化
{
    for (int i = 0; i <= n; i++) head[i] = -1;
    cnt = 0;
}
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
{
    edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
    cin >> n >> m;
    int u, v, w;
    init();//初始化
    for (int i = 1; i <= m; i++)//输入m条边
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);//加边
        /*
        //加双向边
        //无向图，每次都需要反向加边 
        add_edge(u, v, w);
        add_edge(v, u, w);
        */
    }
    for (int i = 1; i <= n; i++)//n个起点
    {
        cout << i << endl;
        for (int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边
        {
            cout << i << " " << edge[j].to << " " << edge[j].w << endl;
        }
        cout << endl;
    }
    return 0;
}
/*
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
*/

参考链接：https://blog.csdn.net/sugarbliss/article/details/86495945

我们知道，链式前向星很类似于静态邻接表，有时候就直接多开几个不同的数组就可以代替结构体了。

三、优缺点

优点：

• 内存利用率高
可以准确开辟最多边数的内存，不像邻接表有爆内存的风险。

• 对不确定边的操作方便效率也不错
这点和邻接表一样，不会遍历到不存在的边。

• 几乎可以用于全部的图论题目（树、图都行）

缺点：

• 难于理解，代码较复杂

• 重边不好处理
这点与邻接表一样，只有通过遍历判重。

• 对确定边的操作效率不高
也与邻接表一样，不能通过两点马上确定边，只能遍历查找。

总的来说，链式前向星是真的非常nice啊！

以上，链式前向星

祝好