这是一种神奇的数据结构。

来源

听说是某个高中Oi菊苣发明,%%%

应用

有的时候有的图可能比较稀疏而且点数较多,邻接矩阵存不下,所以就要用到邻接表。
邻接表用vector数组比较方便,但是vector比较慢。所以就有了链式向前星。

理解

通过Head可以找到一个点的所有边,可以把Head理解为:链表的有实际含义的头节点

Head[N]永远保存最后一次输入的N点数组的下标值,

Head[N]=idx; 意思是,保存N点的数组的下标值

而Next保存变化中的Head,但不保存最后一次的Head

Edge[i].Next=Head[N]; Head[N]=idx++;
从而Head与Next数组实现链式向前星的整个过程,

Head相当于链表的有实际含义的头节点
Next保存链表中的节点,但值得注意的是Next与Head都是通过保存下标值的方式实现的
相当于:索引式链表

End为终点,Value为权值,先不提
而Next就相当于链表中的节点的位置,而没有头节点Head ,是无法提取的。
保存下标值的方式很有趣,虽然开始理解起来有点怪。

int i=Head[S]; 此时i为最后一次保存S点数组的下标值,也就是最后一次输入的S点数据
Edge[i].End 便为最后一次输入S点的终点,Value也是同理,而S作为出发点,不再多提

之后很关键,i=Edge[i].Next,要知道,每次的Edge[i].Next 都是由Head变化而来
意思就是,i=Edge[i].Next,此后的 i为倒数第二次输入S点数组的下标值!
i=Edge[Head[S]].Next;之后 i=Edge[Edge[Head[S]].Next;].Next;
从而反复循环,直到,下一条边为0时,便是最后一次输入的S点的数组的下标值
因为 最开始时,Edge[i].Next=Head[S]=0;

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
struct Node{
int End;//保存一个边的终点
int Next;//保存一个点(起点)的 除了最后一条(输入的顺序)之外的所有边的下标值
int Value;//保存一条边的权值
Node(){}
Node(int a,int b,int c):
End(a),Next(b),Value(c){}
}Edge[maxn];
bool Vis[maxn];
int Head[maxn];//Head数组 为边的索引
int Idx;
queue<int>Map;
inline void AddEdge(int Start,int End,int Value){
Edge[Idx]=Node(End,Head[Start],Value);
Head[Start]=Idx++;
}
inline void Init(){
Idx=1;
memset(Edge,0,sizeof(Edge));
memset(Vis,false,sizeof(Vis));
int N,M,x,y,z;
scanf("%d%d",&N,&M);
while(M--){
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
int Start;
scanf("%d",&Start);
Vis[Start]=true;
Map.push(Start);
}
inline void Traverse(){
while(!Map.empty()){
int Start=Map.front();
Map.pop();
for(int i=Head[Start];i;i=Edge[i].Next){
printf("%d->%d=%d\n",Start,Edge[i].End,Edge[i].Value);
if(!Vis[Edge[i].End]){
Map.push(Edge[i].End);
Vis[Edge[i].End]=true;
}
}
}
}
int main(){
Init();
Traverse();
return 0;
}
/*
输入样例
5 5
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
1
*/

总结

优点:不会浪费数据空间;
缺点:无法直接判断两个点是否是邻接点
链式向前星是一个很不错的数据结构,利用数组索引特性,加上其他权值,存储了整个图。