链式前向星又称静态邻表，今天我们谈的是图，让我们从图的角度来看这个优化的存储结构。
绘制图的优缺点时，链式前星是介于邻接矩阵和邻接表中的记忆结构。
邻接矩阵保存图一般用这个啊。 啊，但是遇到稀疏图的时候，顶点很多，边就那么多，空间浪费必然很大，所以我想了想旁边的表
邻表的邻表(未优化的链式前向星)是最常见的存储结构之一。 但是，vector (动态数组)比)常规数组的时间效率更低。
所以链式前星也是靠运气产生的。 链式正向星是邻接矩阵和邻接表之间比较均衡的数据结构。
链式前向星
让我们先看看代码：
//链式前向星的存储结构struct node{ int to； //边指向的终点int next； //下边的存储下标int w； //权重}edge[maxn]； int head[maxn]； int cnt； //增边voidadd_edge(intu，int v，int w ) { edge[cnt].w=w； edge[cnt].to=v； edge[cnt].next=head[u]； head[u]=cnt； //CNT=0需要初始化(列举枚举器：
这是我拍的别人家博客的照片哦。 请不要在意。
对于这样的图，我们进行升边操作；
1 .首先，cnt的初始化可以是0，也可以是1。 看看你的喜好。 初始化head[]数组。 0或1都可以。
2 .调用函数增加边缘：
for(intI=0； in； //n为边数{ cinuvw； //u为起点，v为该边的终点，w为权重add_edge(u，v，w )； )比如上面的照片就是输入(我这里没有权重，就这样无视吧) :
1 2
2 3
3 4
1 3
4 1
1 5
4 5
这样就形成了链式的前方星星的图。
我想其他人也很理解，edge[].next=head[]这个说法很模糊。 实际上，保存着以I为起点，连接I的顶点编号的最大编号所在的边的数量。 如上图所示，是1-2 (第0边)、1-3 )、1-5边)和1-5边)。edge[3].next=0； 所以有一句话说，遍历的时候，相当于倒过来遍历
for(intI=head[u]； I！=-1； i=edge[i].next ) { .}//u假设起点(当前节点)有这样的邻表基础，那么对于图中最大的经典问题，它是最短路的，这样的存储结构有什么不同呢？ 请看下面的代码：
dijsktra //堆优化最短路的typedef pairint，int P； //编号和距离以VoidDijkstra(ints )//s为起点) { priority_queue P，vectorP，greaterP q； memset(d，inf，sizeof(d ) d )； //memset(vis，0，sizeof ) vis )； d[s]=0； q .推(p (0，s )； while (！ q.empty () ) { P p=q.top； q.pop (； int u=p.second； if(d ) u ) p.first ) continue； for(intI=head[u]； I！=-1； I=edge [ I ].next ({ intv=edge [ I ].to； if(d ) v ) d ) u ) edge(I ).w ) d ) v=d ) u ) edge ) I ).w； q .推(p ) d[v]，v )； } }上面是使用堆优化(priority_queue )的dijkstra模板，最重要的思想是先放松到不能放松的位置，然后遍历的过程就是放松过程。 有关一些主题，请参见priority_queue P、vectorP、greaterP q； 的greater有几个超时，重载运算符也是一种解决方案。 复杂性：
o(ve ) lgV ) SPFA int d[maxn]； //最短距离int vis[maxn]； 确定//队列中是否可以计算具有voidspfa(ints )//负权重的图表(memset ) d、inf、sizeof(d ) d )； 短信(vis，0，sizeof ) vis )； 队列输入q； q.push(s； vis
[s]=1; d[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; //开始遍历松弛 for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; if(!vis[v]) { q.push(v); vis[v]=1; } } } }}有没有觉得这个非常像，就是相差了vis[]这样一个数组判断，而这也就是差别，vis[]在SPFA就是判断当前点是否在队列中，从而进行松弛操作，还有就是vis[]还能判断图中是否有“负权环”（当vis[]>n， 就表示有环）。
复杂度：O(kE)O(kE)。
适用场景如果是稠密图，Dijkstra+heap比SPFA快。稀疏图则SPFA更快。SPFA可以有SLF和LLL两种优化，SLF就是d比队头小就插入队头，否则插入队尾。
全部代码：
#include<iostream>#include<queue>#include<string.h>using namespace std;const int maxn=1e5+10;const int inf=0x3f3f3f3f;//链式前向星的存储结构struct node{ int to;//边指向的终点 int next;//下一条边的存储下标 int w;//权值}edge[maxn];int head[maxn];int cnt;//增边void add_edge(int u,int v,int w){ edge[cnt].w=w; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;//需初始化cnt=0}int d[maxn];//记录最短距离int vis[maxn];//判断是否在队列中/*void SPFA(int s)//可以计算含负权的图{ memset(d,inf,sizeof(d)); memset(vis,0,sizeof(vis)); queue<int > q; q.push(s); vis[s]=1; d[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; //开始遍历松弛 for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(d[v]>d[u]+edge[i].w) { d[v]=d[u]+edge[i].w; if(!vis[v]) { q.push(v); vis[v]=1; } } } }}*///堆优化的最短路typedef pair<int ,int > P;//存编号与距离void dijkstra(int s)//s为起点{ priority_queue< P,vector<P>,greater<P> > q; memset(d,inf,sizeof(d)); //memset(vis,0,sizeof(vis)); d[s]=0; q.push(P(0,s)); while(!q.empty()) { P p=q.top(); q.pop(); int u=p.second; if(d[u]<p.first) continue; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(d[v]>d[u]+edge[i].w){ d[v]=d[u]+edge[i].w; q.push(P(d[v],v)); } } }}int main(){ int m;//顶点数 int n;//边数 int u,v,w; cnt=0; cin>>m>>n; memset(head,-1,sizeof(head)); for(int i=0;i<n;i++) { cin>>u>>v>>w; add_edge(u,v,w); } dijkstra(1); //SPFA(1); for(int i=1;i<=m;i++) cout<<d[i]<<" "; cout<<endl; return 0;}注意：对于inf这个定义，0x7fffffff和0x3f3f3f3f这两个也是一个大坑，
很多人可能设为0x7fffffff,这个数的确是32-bit int的最大值，符号位为0，其他的都是1
但在很多情况下，0x7fffffff会出现错误，比如溢出，这样两个无穷大数相加会变成负数，还有如在做dijkstra求最短路时，当做松弛操作，判断if (d[u]+w[u][v]<d[v]) d[v]=d[u]+w[u][v]时，若u到v没有路劲，w[u][v]=0x7fffffff，这样d[u]+w[u][v]会变成负数，这就产生了错误。
所以，memset(d,0x3f,sizeof(d));