链式前向星是一种常见的储存图的方式（是前向星存图法的优化版本），支持增边和查询，但不支持删边（如果想要删除指定的边建议用邻接矩阵）。
- 储存方式
首先定义数组 head[ i ] 来储存从节点 i 出发的第一条边的下标，定义结构体 edge[ i ] 中包含三个元素 nxt, to, val, 分别储存从节点 i 出发的下一条边的下标（nxt），该边的终点（to）， 该边的边权（val）。
struct EDGE {
int nxt, to, val; /* 下一条边的下标， 这条边的终点， 边权 */
};
EDGE edge[maxn];
int head[maxn]; /* head[ i ]储存从节点 i 出发的第一条边的下标 */
- 添加节点
定义变量 cnt 表示当前边的编号（初始值为0），具体如代码所示。
int cnt = ;
void add ( int st, int ed, int v ) {
edge[ ++cnt ].nxt = head[st];
edge[cnt].to = ed;
edge[cnt].val = v;
head[st] = cnt;
/*
edge[ ++cnt ].nxt = head[ed]; * 如果是无向图就加上这个语句
edge[cnt].to = st;
edge[cnt].val = v;
head[ed] = cnt;
*/
}
- 节点的遍历
从数据结构就可以看出来，上代码。
/* i 是作为原点的节点编号 */
for ( int j = head[i]; j != ; j = edge[j].nxt ) /* <-- 链式前向星遍历的关键 */
printf ( "-->%d || val = %d \n", edge[j].to, edge[j].val );
}
- 汇总代码
#include <cstdio>
#include <cstring> using namespace std; const int maxn = ; struct EDGE {
int nxt, to, val; /* 下一条边的下标， 这条边的终点， 边权 */
};
EDGE edge[maxn]; int head[maxn], cnt = ; /* head[ i ]储存从节点 i 出发的第一条边的下标 */ void add ( int st, int ed, int v ) {
edge[ ++cnt ].nxt = head[st];
edge[cnt].to = ed;
edge[cnt].val = v;
head[st] = cnt; /*
edge[ ++cnt ].nxt = head[ed]; * 如果是无向图就加上这个语句
edge[cnt].to = st;
edge[cnt].val = v;
head[ed] = cnt; */ } int main () {
memset ( head, , sizeof head );
int n, m;
scanf ( "%d%d", &m, &n ); /* 共有 m 个节点， n 条边 */
for ( int i = ; i <= n; i ++ ){
int a, b, c;
scanf ( "%d%d%d", &a, &b, &c );
add ( a, b, c );
}
for ( int i = ; i <= m; i ++ ){
printf ( "开始以节点%d为原点\n", i );
for ( int j = head[i]; j != ; j = edge[j].nxt ) /* <-- 链式前向星遍历的关键 */
printf ( "-->%d || val = %d \n", edge[j].to, edge[j].val );
}
return ;
}