大家好，欢迎来到IT知识分享网。
在描述链式前向星之前，我们先来看一下什么是前向星。
前向星：
复杂度说明：
时间复杂度 O(mlogm)
空间复杂度 O(m+n)
优点：
1.点多的情况有优势
2.可以储存重边
缺点：
1.排序浪费时间
2.无法直接判断两个点之间是否有边
概念阐述：
一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序(可以使用基数排序，如下面例程)，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。
通俗一点来讲：
前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.
用len[i]来记录所有以i为起点的边在数组中的存储长度.
用head[i]记录以i为边集在数组中的第一个存储位置.
这个东西并不是什么高深莫测的东西，只是一种思维的抽象，因此在没有讲解的情况下不太好理解，不过实际上不难，前向星特别适合用来优化 SPFA、DFS、BFS。
我们来看一个图：
针对上图，假设我们输入边的顺序为:
1 2
2 3
3 4
1 3
4 1
1 5
4 5
那么依据上述规则排完序后就得到:
编号: 1 2 3 4 5 6 7
起点u: 1 1 1 2 3 4 4
终点v: 2 3 5 3 4 1 5
最终得到head[i]、len[i]值如下：
head[1] = 1 len[1] = 3
head[2] = 4 len[2] = 1
head[3] = 5 len[3] = 1
head[4] = 6 len[4] = 2
显然，利用前向星会使用到排序操作，所以即便是使用效率较高的快速排序，前向星算法的时间复杂度也至少为O(mlog(m))。
链式前向星：
有了前向星的铺垫，那对于链式前向星无疑更好理解一点
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》
链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。
我们建立边结构体为:
struct Edge
{
int next;
int to;
int w;
};
其中：
edge[i].to表示第i条边的终点,
edge[i].next表示与第i条边同起点的下一条边的存储位置,
edge[i].w为边权值.
另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号.
head[]数组一般初始化为-1
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为起点的上一条边的编号
}
我们接下来来实际演示一遍。
给你一组数据：
第一行表示 5 个顶点 7 条边
接下来是7条边的起点、终点和权值
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
然后我们根据上面的结构体，建图，我把图具象出来以便理解：
依据next，head数组的约定，并按边的输入顺序从0开始对边进行编号，
然后按照上面的数据就可以写出下面的过程：
对于1 2 1这条边：edge[0].to=2; edge[0].next=-1; head[1]=0;
对于2 3 2这条边：edge[1].to=3; edge[1].next=-1; head[2]=1;
对于3 4 3这条边：edge[2].to=4; edge[2],next=-1; head[3]=2;
对于1 3 4这条边：edge[3].to=3; edge[3].next= 0; head[1]=3;
对于4 1 5这条边：edge[4].to=1; edge[4].next=-1; head[4]=4;
对于1 5 6这条边：edge[5].to=5; edge[5].next= 3; head[1]=5;
对于4 5 7这条边：edge[6].to=5; edge[6].next= 4; head[4]=6;
很明显,head[i]保存的是以i为起点的所有边中编号最大的那个,而把这个当作顶点i的第一条起始边的位置.
遍历函数如下：
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来找与边j起点相同的上一条边的编号，终止条件为edge[j].next=-1。
总结性代码：
#include<bits/stdc++.h>
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;
}
【测试样例】
in：
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
out：
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为起点的边不存在
总结：
我也是最近写最短路问题的时候，发现这个神奇的东西，也多亏了下面几个博客大佬的参考，我还会继续改
进的。
参考博客：
https://blog.csdn.net/sugarbliss/article/details/86495945
https://blog.csdn.net/acdreamers/article/details/16902023
https://blog.csdn.net/hnjzsyjyj/article/details/103778724
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/12621.html
