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

来源

听说是某个高中 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;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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
*/

总结

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