一，前言
说实话，看到时候没有看懂，自己模拟了一下 边是怎么 加上去的，才搞明白。
想明白之后，才知道被这些 变量名 给忽悠了，我不知道取名的人是怎么想的，
但我觉的有些变量名并不恰当，直接把我带到沟里去了，所以这里 我写的代码源自
自己的习惯，勿怪！๑乛◡乛๑ (●´∀｀●)
二，引子
想要通过 一组有序的点来记录 一条路径 的话，你只需要 两个变量，
一个记录当前点的编号，一个记录前一个点的编号（在这里我有详细讲到 https://www.cnblogs.com/asdfknjhu/p/12499112.html）
但如果不是一条路，而是一张图，又有什么不同呢？
在 一条路中 ，一个点的前一个点是唯一的，而如果是图的话，就会出现 一点 映射 多点 的情况，
这样你就不知道要设 几个变量 来存 前一个点的编号了。
所以，重点来了(..•˘_˘•..) ，要存图，你需要 存放的是一个边的所有信息。于是，你需要构造一个结构体数组，其中每个结构体代表一条边。
三，边
那么一条边你需要存什么信息呢？
答案是：起点，终点（知道了起点和终点就可以确认方向了），权值
那么问题来了，知道了终点就可以找到，以此终点为起点的边，但是那些相同起点的边你怎么根据其中一条找到剩下的边（即怎么把相同起点的边连接起来）
所以，重点又来了，这一步可是整个链式前向星的精髓 (..•˘_˘•..)
因为起点无法直接使用，于是我们 取消 结构体中需要的起点变量，另设两个变量
一个是在结构体中 int ：我称之为，pre : 即与本边 同一起点的前一条边的 结构体编号，
一个是 int 数组：last: ：last[i] 里面存的是 表示以第 i 个点为起点 的所有边中 最后一条边的 结构体编号
为什么是 以第 i 个点为起点, 可以看添加边时，last 数组的赋值，下标用的是 起点的编号。
没错，我说名字误导我的就是这两个变量，原名为 next, head/first，我也是醉了，跟我理解的完全相反 ٩͡[๏̯͡๏]
有了这两个变量，我们就可以根据，最后一条边，往前遍历所有起点相同的边了。
四，边集
即结构体数组，我们根据边添加的顺序对边进行编号，即把某条边放进哪一个结构体，就是按顺序来，先来的一号，后来末尾。
通过 to 和 pre 链接边。
to: 向下搜索
pre:横向搜索
(•‾̑⌣‾̑•)✧˖°
由于结构体数组一开始肯定要开很大，所以为了记录边的数量且为了便于添加边
我们 还需要最后一个变量 int tot.
五，总结
综上，我们需要 一个结构体数组 e,
里面的变量有 to : 终点
w; 权值
pre;即与本边 同一起点的前一条边的 结构体编号，
还要一个数组 last, 一个变量 tot
六，具体实现
初始化：
struct Node { int pre; int to; int w; }e[N]; int last[N],vis[N]; int tot=0; // 没有边 memset(last, -1, sizeof(last)); // 初始化为 -1 ，因为结构体数组要从 0 开始
加边函数
void add(int from, int to , int w) //按顺序为 起点，终点，权值 {
tot++; e[tot].to = to; e[tot].w = w; e[tot].pre = last[from]; // 给新加的边，赋上 前一个相同起点的边的编号 last[from] = tot; // 更新 lasi 数组，新加入的边 才是这些起点相同的边中 最后一个 }
求以第 x 个点为起点 的所有边的权值
以 以该点为起点 的最后一条边开始，往前遍历所有起点相同的边，当 pre == -1 时，表示前面没有变了。
int sum = 0; for (int i = last[x];~i;i=e[i].pre) { sum += e[i].w; }
遍历所有边: 调用时 dfs(1); //从 第一个点 开始
int ci = 0; void dfs(int s) // 所找到的顺序与添加的顺序不一样 { vis[s] = 1; for (int i = last[s]; ~i; i = e[i].pre) // 同一个 for 循环起点都相同 { printf("第 %d 条边: 起点：%d 终点：%d 权值：%d ", ++ci, s, e[i].to, e[i].w); if (vis[e[i].to] == 0) // 以该终点为起点，向下搜索 { dfs(e[i].to); } } }
代码总结：
题目：来源 http://www.fjutacm.com/Contest.jsp?cid=863#P12
我多加了一个功能。遍历图
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #define N (int)2e6+5 struct Node { int pre; int to; int w; }e[N]; int tot = 0; // 没有边 int last[N], vis[N]; void add(int from, int to, int w) //按顺序为 起点，终点，权值 { tot++; e[tot].to = to; e[tot].w = w; e[tot].pre = last[from]; // 给新加的边，赋上 前一个相同起点的边的编号 last[from] = tot; // 更新 lasi 数组，新加入的边 才是这些起点相同的边中 最后一个 } int ci = 0; void dfs(int s) // 所找到的顺序与添加的顺序不一样 { vis[s] = 1; for (int i = last[s]; ~i; i = e[i].pre) // 同一个 for 循环起点都相同 { printf("第 %d 条边: 起点：%d 终点：%d 权值：%d ", ++ci, s, e[i].to, e[i].w); if (vis[e[i].to] == 0) // 以该终点为起点，向下搜索 { dfs(e[i].to); //vis[s] = 0; // 这句 不能有，不然会重复找， } } } int main(void) { int n, m, q; while (scanf("%d%d%d", &n, &m, &q) != EOF) { memset(last, -1, sizeof(last)); for (int i = 1; i <= m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, z); if (x != y) add(y, x, z); } // 询问 以第 x 个点为起点 的所有边的权值 while (q--) { int x; scanf("%d", &x); if (last[x] == -1) printf("第 %d 个点为起点 的所有边的权值:NULL ", x); else { int sum = 0; for (int i = last[x]; ~i; i = e[i].pre) { sum += e[i].w; } printf("第 %d 个点为起点 的所有边的权值：%d ", x, sum); } } puts(""); // 遍历 dfs(1); //从 第一个点 开始 } return 0; }
========== ========= ========= ======= ===== ===== === == =
渡荆门送别 唐 李白
渡远荆门外，来从楚国游。
山随平野尽，江入大荒流。
月下飞天镜，云生结海楼。
仍怜故乡水，万里送行舟。