最近学习了图(点用边连起来就叫做图)来理解一下数组模拟邻接表存储//头插法
#include<bits/stdc++.h> const int N = 100005; struct node { int to; int dis; int next; }edge[N]; int head[N],cnt,n,m,u,v,d;//head[i]表示以i为起点的上一个边(edge数组)的下标 void add_edge(int from,int to,int dis)//感觉这里比较核心也有点不好理解 { edge[++cnt].to=to; //cnt给每一个边命名用序号来找。 edge[cnt].dis=dis;//这条边的长度。 edge[cnt].next=head[from];///记录以from节点出发的上一条边在edge数组的位置 head[from]=cnt;//更新起点from指向的边(这样就相当于把这个边放在了头上)怎么说呢给人一种迭代的感觉。 } int main() { memset(head,0,sizeof(head));//如果为0就说明没有边了就可以终止了。 int n,m; scanf("%d%d",&n,&m); cnt=0; for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); } for(int i=1;i<=n;i++) { printf("%d: ",i); for(int j=head[i];j;j=edge[j].next) printf("%d ",edge[j].to); printf("\n"); } return 0; }再看看最短路径最小生成树。
