链式前向星
图的存储一般有两种：邻接矩阵、邻接表（邻接表包括一种东西叫前向星）。
若图是稀疏图，边很少，开二维数组a[][]很浪费;
若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.
前向星的效率不是很高，优化后为链式前向星，直接介绍链式前向星。
（一）链式前向星
1. 结构
这里用两个东西：
1 结构体数组edge存边，edge[i]表示第i条边,
2 head[i]存以i为起点的最后一条边(在edge中的下标)
struct node{ int next; //下一条边的存储下标(默认0) int to; //这条边的终点 int w; //权值 }; node edge[500010];
2.增边
若以点i为起点的边新增了一条，在edge中的下标为j.
那么edge[j].next=head[i];然后head[i]=j.
即每次新加的边作为第一条边，最后倒序遍历
void add(int u, int v, int w) { //起点u, 终点v, 权值w //cnt为边的计数，从1开始计 edge[++cnt].next = head[u]; edge[cnt].w = w; edge[cnt].to = v; head[u] = cnt; //第一条边为当前边 }
3. 遍历
遍历以u为起点的边
for(int i=head[u]; i!=0; i=edge[i].next)
链式前向星实现SPFA
#include <cstdio> #include <map> #include <iostream> #include<cstring> #include<bits/stdc++.h> #define ll long long int #define M 6 using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; struct node{ int next; int to; int w; }; node edge[100007]; int n, m, u, cnt; int head[100007]; int dis[100007]; bool vis[100007]; void add(int u, int v, int w) { edge[++cnt].next = head[u]; edge[cnt].to = v; edge[cnt].w = w; head[u] = cnt; } void spfa(int x){ for(int i=1;i<=n;i++){ dis[i]=inf; } dis[x]=0; memset(vis,0,sizeof(vis)); queue<int > q; q.push(x); vis[x]=1; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=0;i=edge[i].next){ int to=edge[i].to; int d=edge[i].d; if(dis[to]>dis[u]+d){ dis[to]=dis[u]+d; if(!vis[to]){ q.push(to); vis[to]=1; } } } } } int main(){ }
今天的文章链式前向星_链式前向星和邻接表分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/54155.html
