? ? ? ? 图最常用的存储结构主要是邻接矩阵和邻接表。当顶点数太大时，用二维数组表示的邻接矩阵可能超内存（MLE），而用邻接表的编码工作量较大，此时，使用vector数组或链式前向星模拟邻接表是不错的选择。因vector数组容易理解，这里仅介绍链式前向星存储图。
? ? ? ? 设有向图的顶点数n=5，边数m=10，输入的边用三个整数from, to, w，分别表示一条边的起点（弧尾顶点）、终点（弧头顶点），边上的权值。输入的10条边如下：
3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7
? ? ? ? 因链式前向星存储图实际上是静态链表，即用数组模拟链表，这里先回顾邻接表存储图的知识，以便读者能更好地理解链式前向星。若读者清楚知道这部分内容，则可跳过。
? ? ? ? 邻接表包含表头结点表（一个数组，设为head）和边表（若干链表）两部分，边表的每个链表结点包含邻接点to，权值weight，指向下一条边的指针域next。每条边采用头插法插入对应链表中，则用上述的数据构建的邻接表如下（表头结点表用整型指针数组即可，1~5表示下标）：
? ? ? ? ?相应的实现代码如下：
//有向图的邻接表实现
#include <iostream>
using namespace std;
const int N=10;
struct ENode{
int to; //某弧所指向顶点的下标
int weight; //弧上的权重
ENode* next; //指向下一条弧
};
ENode* head[N];
int n, m;
void insertArc(int from, int to, int weight) { // 将弧<from,to>加入图
ENode *s=new ENode;
s->to=to;
s->weight=weight;
s->next=head[from]; // 插到链表head[from]的头部
head[from]=s;
}
void output() { //逐个顶点输出各边
for(int i=1;i<=n;i++) {
cout<<i<<"";
ENode *p=head[i];
while(p!=NULL) {
cout<<"->("<<p->to<<","<<p->weight<<")";
p=p->next;
}
cout<<endl;
}
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) head[i]=NULL;
for(int i=0;i<m;i++)
{
int from, to, w;
cin>>from>>to>>w;
insertArc(from, to, w);
}
output();
return 0;
}
? ? ? ? 输入如下：
5 10
3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7
? ? ? ? 输出结果如下：
1->(2,9)->(3,5)
2->(1,4)->(3,6)->(4,8)
3->(5,7)->(2,5)->(4,7)
4->(2,5)->(1,3)
5
? ? ? ? 理解邻接表之后，就可以开始链式前向星了。关键是两个数组，一个是类似邻接表的表头结点表的整数数组head，其中head[i]表示以i为起点的最后（输入）那条边的序号（或称编号），对应邻接表边表中以i为起点的第一条边的编号；另一个是next（实现时next作为表示边的结构体的一个成员，用一个结构体数组表示边集，next是结构体数组元素的一个域），其中next[i]表示以第i条边的起点为起点的前一条（输入）边的编号，对应邻接表边表中的下一条边的编号。设边结构体包含的成员为邻接点to，权值weight，指向下一条边的指针（实际上是一个整数）next，则可得上述数据构建的链式前向星（图中的起点是为方便阅读，可不必存储；有时为方便起见，可在边结构体增加起点成员from）如下：
? ? ? ? 相应的实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=10, M=100;
struct Edge {
int to; //一条边的终点（弧头顶点）
int weight; //边上的权值
int next; //以该条边的起点（弧尾顶点）为起点的前一条（输入）边的编号，对应邻接表边表中的下一条边的编号
};
int head[N]; //head[i]：以i为起点的最后（输入）那条边的编号；对应邻接表边表中以i为起点的第一条边的编号
Edge edges[M];
int cnt; //边的编号计数器
int n,m; //实际的顶点数和边数
void output();
void addEdge(int from, int to, int w) {
cnt++; //边数增1
edges[cnt].to=to; //终点直接赋值
edges[cnt].weight=w; //边上的权值直接赋值
edges[cnt].next=head[from]; //相当于把第cnt条边链接到第from个顶点的第一条边之前
head[from]=cnt; //把第from个顶点的head值置为当前以from为起点的最后一条边的编号，相当于把最后一条边作为边表的第一条边
}
int main() {
cin>>n>>m;
cnt=0;
fill(head+1,head+n+1,-1);//把head[1]~head[n]都置为1
for(int i=0; i<m; i++) { //输入m条边，建立链式前向星存储结构
int from,to,w;
cin>>from>>to>>w;
addEdge(from, to, w);
}
output(); //输出head、edges数组验证
return 0;
}
void output() { //输出head、edges数组的函数
cout<<"head:\n";
for (int i=1; i<=n; i++) {
cout<<i<<": "<<head[i]<<endl;
}
cout<<"edges:\n";
for (int i=1; i<=m; i++) {
cout<<i<<": "<<edges[i].to<<" "<<edges[i].weight<<" "<<edges[i].next<<endl;
}
}
? ? ?
????????输入如下：
5 10
3 4 7
4 1 3
1 3 5
2 4 8
3 2 5
2 3 6
4 2 5
1 2 9
2 1 4
3 5 7
? ? ? ? 输出结果如下：
head:
1: 8
2: 9
3: 10
4: 7
5: -1
edges:
1: 4 7 -1
2: 1 3 -1
3: 3 5 -1
4: 4 8 -1
5: 2 5 1
6: 3 6 4
7: 2 5 2
8: 2 9 3
9: 1 4 6
10: 5 7 5
????????
? ? ? ? 每段岁月都有价值。谨以此文纪念2021年暑假集训。祝愿集训队员们都有美好的未来！明天的你会感谢今天奋斗的自己，加油！