一、概述

我们在学习图论的时候学习了一种图的存储结构--二维数组邻接矩阵储存，他虽然可以表达直观，快速访问连接两点的边，但是它占用空间大，只适用于点少的图，所以我们需要一种能够可以存储大型图的东西--链式前向星。

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度。

二、链式前向星基本原理

首先我们要存入以下一张图：

点1指向点2、点3、点4。

链式前向星是以边为主的存图方式，我们需要利用结构体来规划边，这会使图变得更加清晰。

首先我们需要建立边的数组edge[ ]，一般我们需要它记录多种元素：下一条边的编号，这条边到达的点，这条边的长度

struct Edge
{int next;//下一条边的编号 int to;//这条边到达的点 int dis;//这条边的长度 
}edge[maxm];

其次我们将已知的边加入；

int main()
{num_edge=0;//定义边数，后面直接++ scanf("%d%d",&n,&m);//输入点数和边数for(int i=1;i<=m;i++)//记录边数 {scanf("%d%d%d",&u,&v,&d);//输入从哪里来到哪里去权值是多少 add_edge(u,v,d);//正存图 add_edge(v,u,d);//如果是无向图，就要反存图 }	}

我们可以添加一个add函数方便我们添加：

void add_edge(int from,int to,int dis) //加入一条从from到to距离为dis的单向边 
{edge[++num_edge].next=head[from]; edge[num_edge].to=to;//将to记录 edge[num_edge].dis=dis;//将dis记录 head[from]=num_edge;// 
}

可能过这一步有点迷，下面是一个存图的模拟：