如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》
链式前向星其实就是静态建立的邻接表，时间效率为O（m），空间效率也为O（m）。遍历效率也为O（m）。
对于下面的数据，第一行5个顶点，7条边。接下来是边的起点，终点和权值。也就是边1 -> 2 权值为1。
-
5
7
-
1
2
1
-
2
3
2
-
3
4
3
-
1
3
4
-
4
1
5
-
1
5
6
-
4
5
7
链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：
-
1
//以1为起点的边的集合
-
1
5
6
-
1
3
4
-
1
2
1
-
-
2
//以2为起点的边的集合
-
2
3
2
-
-
3
//以3为起点的边的集合
-
3
4
3
-
-
4
//以4为起点的边的集合
-
4
5
7
-
4
1
5
-
-
5
//以5为起点的边不存在
我们先对上面的7条边进行编号第一条边是0以此类推编号【0~6】，然后我们要知道两个变量的含义：
- Next，表示与这个边起点相同的上一条边的编号。
- head[ i ]数组，表示以 i 为起点的最后一条边的编号。
head数组一般初始化为-1，为什么是 -1后面会讲到。加边函数是这样的：
-
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
-
{
-
edge[cnt].to = v;
//终点
-
edge[cnt].w = w;
//权值
-
edge[cnt].next = head[u];
//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
-
head[u] = cnt++;
//更新以u为起点上一条边的编号
-
}
我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：
对于1 2 1这条边：edge[0].to = 2; edge[0].next = -1; head[1] = 0;
对于2 3 2这条边：edge[1].to = 3; edge[1].next = -1; head[2] = 1;
对于3 4 3这条边：edge[2].to = 4; edge[2],next = -1; head[3] = 2;
对于1 3 4这条边：edge[3].to = 3; edge[3].next = 0; head[1] = 3;
对于4 1 5这条边：edge[4].to = 1; edge[4].next = -1; head[4] = 4;
对于1 5 6这条边：edge[5].to = 5; edge[5].next = 3; head[1] = 5;
对于4 5 7这条边：edge[6].to = 5; edge[6].next = 4; head[4] = 6;
遍历函数是这样的：
-
for(
int i =
1; i <= n; i++)
//n个起点
-
{
-
cout << i <<
endl;
-
for(
int j = head[i]; j !=
-1; j = edge[j].next)
//遍历以i为起点的边
-
{
-
cout << i <<
" " << edge[j].to <<
" " << edge[j].w <<
endl;
-
}
-
cout <<
endl;
-
}
第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过edge[ j ].next来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的edge[ j ].next为 -1做为终止条件。
具体代码为：
-
#include<bits/stdc++.h>
-
using
namespace
std;
-
const
int maxn =
1005;
//点数最大值
-
int n, m, cnt;
//n个点，m条边
-
struct Edge
-
{
-
int to, w, next;
//终点，边权，同起点的上一条边的编号
-
}edge[maxn];
//边集
-
int head[maxn];
//head[i],表示以i为起点的第一条边在边集数组的位置（编号）
-
void init()//初始化
-
{
-
for (
int i =
0; i <= n; i++) head[i] =
-1;
-
cnt =
0;
-
}
-
void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权
-
{
-
edge[cnt].to = v;
//终点
-
edge[cnt].w = w;
//权值
-
edge[cnt].next = head[u];
//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
-
head[u] = cnt++;
//更新以u为起点上一条边的编号
-
}
-
int main()
-
{
-
cin >> n >> m;
-
int u, v, w;
-
init();
//初始化
-
for (
int i =
1; i <= m; i++)
//输入m条边
-
{
-
cin >> u >> v >> w;
-
add_edge(u, v, w);
//加边
-
/*
-
加双向边
-
add_edge(u, v, w);
-
add_edge(v, u, w);
-
*/
-
}
-
for (
int i =
1; i <= n; i++)
//n个起点
-
{
-
cout << i <<
endl;
-
for (
int j = head[i]; j !=
-1; j = edge[j].next)
//遍历以i为起点的边
-
{
-
cout << i <<
" " << edge[j].to <<
" " << edge[j].w <<
endl;
-
}
-
cout <<
endl;
-
}
-
return
0;
-
}
-
/*
-
5 7
-
1 2 1
-
2 3 2
-
3 4 3
-
1 3 4
-
4 1 5
-
1 5 6
-
4 5 7
-
*/
参考：
https://blog.csdn.net/acdreamers/article/details/16902023#comments
https://blog.csdn.net/ZscDst/article/details/79060993
https://blog.csdn.net/pk__pk/article/details/78432288
转载：https://blog.csdn.net/sugarbliss/article/details/86495945