本文共 1013 字，大约阅读时间需要 3 分钟。

之前存图用邻接表都是直接使用的vector，但是vector是自动扩容的，在空间不够的时候会自动申请多一倍的空间，这样的话空间浪费比较严重，而且有的题目会卡空间，可能就过不了。如果使用链式前向星，就可以节省不少空间，开一个和边的数目相同的数组就可以了。

链式前向星包括两个部分：head数组，和edge数组。

head[i]表示以i为起点的第一条边的位置。

edge是个结构体数组：

struct Edge{	int to;//表示第i条边的终点	int next;//表示与第i条边同起点的下一条边的存储位置	int w;//权值}edge[M];

void add(int u,int v,int w)  {      edge[cnt].w = w;      edge[cnt].to = v;      edge[cnt].next = head[u];      head[u] = cnt++;  }

for(int i=head[u];i!=-1;i=edge[i].next)

#include 
   
    #include 
    
     #define N 105	//顶点数目 #define M 10005	//边的数目 struct Edge{	int to;	int next;	int w;}edge[M];int head[N];int main(){	int n, m, u, v, w, cnt;	scanf("%d%d", &n, &m);	memset(head, -1, sizeof(head));	cnt = 0;	for(int i = 0; i < m; i++){	//建图 		scanf("%d%d%d", &u, &v, &w);		edge[cnt].w = w;  	    edge[cnt].to = v;  	    edge[cnt].next = head[u];  	    head[u] = cnt++; 	}		for(int i = 0; i < n; i++){	//遍历以i为头的所有边 		for(int j = head[i]; j != -1; j = edge[j].next)			printf("%d ", j);		printf("\n");	}	return 0;}
    
   

转载地址：https://blog.csdn.net/zhj_fly/article/details/75270737 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！