链式前向星
介绍
有权边的图的存储一般有两种：邻接矩阵、前向星。
若图是稀疏图，边很少，开二维数组 a[][]很浪费;若点很多(如 10000 个点)a[10000][10000]又会爆.只能用前向星做。
前向星的效率不是很高（要将边的起点或终点进行排序），优化后为链式前向星，效率有所提升。
数据结构
1 结构体数组 edge 存边，edge[i]表示第 i 条边，
2 head[i]存以 i 为起点的第一条边(在 edge 中的下标)
增边方法
增边：若以点 i 为起点的边新增了一条，在 edge 中的下标为。
那么 edge[j].next=head[i]；然后 head[i]=j。
即每次新加的边作为从该起点出发的第一条边，最后倒序遍历（即 edge[j].next 用来记录以该点为起点的下一条边在 edge 中的下标，用于遍历）
代码示例
#include <iostream>
using namespace std;
#define MAXM 500010
#define MAXN 10010
struct EDGE
{
int next; //与该边同起点的下一条边的存储下标
int to; //这条边的终点
int w; //权值
};
EDGE edge[MAXM];
int n, m, cnt;
int head[MAXN]; //head[i]表示以i为起点的第一条边
void Add(int u, int v, int w)
{
//起点u, 终点v, 权值w
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt; //第一条边为当前边
}
void Print()
{
int st;
cout << "Begin with[Please Input]: ";
cin >> st;
for (int i = head[st]; i != 0; i = edge[i].next)
{
//i开始为第一条边，每次指向下一条(以0为结束标志)若下标从0开始，next应初始化-1
cout << "Start: " << st << endl;
cout << "End: " << edge[i].to << endl;
cout << "W: " << edge[i].w << endl
<< endl;
}
}
int main()
{
int s, t, w;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> s >> t >> w;
Add(s, t, w);
}
Print();
return 0;
}