前向星和链式前向星
链式前向星
添加边的操作
链式前向星，就是以链式结构来储存前向星，每条边就要用结构体，结构体中包含三个数据：
Edge[i].to ：第i条边的终点
Edge[i].next ：与第i条边同一个起点的下一条边
Edge[i].w：第i条边的边权
还有一个head数组来储存第一个以i为起点的边的位置，同时head初始化为-1。
我们先看代码：
void add_edge(int u, int v, int w) // 这里面初始化cnt = 1
{edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;
}
还是举个上面的例子：
1 3 9
5 1 3
1 4 4
2 3 5
4 5 7
1 2 8
5 3 2
通过用表格来看添加每一条边的变化：
| 起点 | 终点 | 边权 | Edge[i].to | Edge[i].next | head[i] |
|---|---|---|---|---|---|
| 1 | 3 | 9 | Edge[1].to = 3 | Edge[1].next = -1 | head[1] = 1 |
| 5 | 1 | 3 | Edge[2].to = 1 | Edge[2].next = -1 | head[5] = 2 |
| 1 | 4 | 4 | Edge[3].to = 4 | Edge[3].next = 1 | head[1] = 3 |
| 2 | 3 | 5 | Edge[4].to = 3 | Edge[4].next = -1 | head[4] = 4 |
| 4 | 5 | 7 | Edge[5].to = 5 | Edge[5].next = 4 | head[4] = 5 |
| 1 | 2 | 8 | Edge[6].to = 2 | Edge[6].next = 3 | head[6] = 6 |
| 5 | 3 | 2 | Edge[7].to = 3 | Edge[6].next = 2 | head[7] = 7 |
如果表格不太理解可以看图来理解
第一次 起点 ：1 终点：3 边权：9
Edge[1].to = 3
Edge[1].next = -1
Edge[1].w = 9
head[1] = 1
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 1 | -1 | -1 | -1 | -1 |
第二次 起点 ：5 终点：1 边权：3
Edge[2].to = 1
Edge[2].next = -1
Edge[2].w = 3
head[5] = 2
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 1 | -1 | -1 | -1 | 2 |
第三次 起点 ：1 终点：4 边权：4
Edge[3].to = 4
Edge[3].next = head[1] = 1
Edge[3].w = 4
head[1] = 3
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 3 | -1 | -1 | -1 | 2 |
第四次 起点 ：2 终点：3 边权：5
Edge[4].to = 3
Edge[4].next = -1
Edge[4].w = 5
head[2] = 4
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 3 | 4 | -1 | -1 | 2 |
第五次 起点 ：4 终点：5 边权：7
Edge[5].to = 5
Edge[5].next = -1
Edge[5].w = 7
head[4] = 5
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 3 | 4 | -1 | 5 | 2 |
第六次 起点 ：1 终点：2 边权：8
Edge[6].to = 3
Edge[6].next = head[1] = 3
Edge[6].w = 8
head[1] = 6
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 6 | 4 | -1 | 5 | 2 |
第七次 起点 ：5 终点：3 边权：2
Edge[7].to = 3
Edge[7].next = head[5] = 2
Edge[7].w = 2
head[5] = 7
| head[1] | head[2] | head[3] | head[4] | head[5] |
|---|---|---|---|---|
| 6 | 4 | -1 | 5 | 7 |
通过上面的例子，我们可以发现head[i]数组最终储存的值是最后一个输入以i为起点的边的位置，而next就是将原来的head储存起来。
遍历操作
遍历代码是这样的：
for (int i = 1; i <= n; i++) // n是节点的个数
{for (int j = head[i]; j != -1; j = Edge[i].next) {printf("%d %d %d", i, Edge[i].to, Edge[i].w);}
}
其中第二个循环中，我们是从最后一个输入的以i为起点的边开始，由它的next再找到倒数第二条边……
比如下面一个例子，一共四条边，都是以1为起点的。
1 2 9
1 3 4
1 4 5
1 5 7
| 终点 | Edge[i].next |
|---|---|
| 2 | Edge[1].next = -1 |
| 3 | Edge[2].next = 2 |
| 4 | Edge[3].next = 3 |
| 5 | Edge[4].next = 4 |
看，这是不是很明显的链式结构？所以我们从第四条边开始，通过第四条的next找到第三条，由第三条的next找到第二条……直到等于-1，也就是没有下一条边了，也就说明以1为起点的边都遍历完了。
