注：本文以 ( u , v ) (u, v) (u,v)表示从 u u u到 v v v的有向边，本文所有图使用例题题意的图。
一、链式前向星：
1、什么是链式结构：
链式结构指的是在前一个元素的末位指向下一个元素的下标。一般使用结构体数组。
2、链式前向星是什么：
一般地，链式结构指向的是后面的元素，但是链式前向星，指向的是前面的元素的下标。所以，链式前向星可被认为是向前的链式结构。
3、链式前向星的储存方式：
通常我们定义一个结构体 e d g e edge edge，内包括了 t t t（边的终点）， w w w（可省，边的权值）， n x t nxt nxt（下一个同起点边的下标）。用一个数组储存（注意：在无向图中，数组要开两倍空间）。
struct edge {int to, w, nxt;} graph[size];
接着定义一个数组 h e a d [ ∣ V ∣ ] head[|V|] head[∣V∣]，初始化为0（Linus系统下不初始化为乱码）
级每个点发出的最后一条边的下标，定义一个指针 h p p hpp hpp为零，每增加一条边。让hpp自增，然后更新 h e a d [ u ] head[u] head[u]（ u u u为新增边的起点）为 h p p hpp hpp。无向图只需增加两条权值为 w w w边 ( u , v ) (u, v) (u,v)和 ( v , u ) (v, u) (v,u)。
我们给出链式前向星储存代码的样例：
例题：
第一行输入 n n n， m m m，分别表示 ∣ V ∣ |V| ∣V∣， ∣ E ∣ |E| ∣E∣。
接着输入 m m m行，每行两个数 u u u， v v v， w w w，表示边的起点，终点和权值。
#include <iostream>const int size = 100001;using namespace std;struct edge {int to, w, nxt;} graph[size];int head[size], hpp = 0;void addEdge(int from, int to, int weight) {hpp++, graph[hpp].to = to, graph[hpp].w = w, graph[hpp].nxt = head[from];// 亦可写作graph[++hpp] = edge{w, to, head[from]};(C++11以上版本)head[from] = hpp;}int main() {int n, m;cin >> n >> m;fill(head, head + n + 1, 0); //初始化head数组，也可用for循环for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;addEdge(u, v, w);}}
4、链式前向星遍历图：
原理：利用 h e a d head head数组，遍历每个点出发的边；输出结点即可
链式前向星的遍历代码直接给出：
for (int i = 1; i <= n; i++)for (int p = head[u]; p; p = graph[p].nxt) cout << graph[p].to;
二、图的DFS：
图的DFS与路径DFS不大相同，图的DFS从结点开始（记为 r o o t root root），查找由 r o o t root root出发的路径的终点，以终点为 r o o t root root继续进行DFS。
求DFS(1)
链式前向星代码如下：
#include <iostream>using namespace std;const int size = 100001;struct edge {int to, w, nxt;} graph[size];int head[size], hpp = 0;void addEdge(int from, int to, int weight) {hpp++, graph[hpp].to = to, graph[hpp].w = w, graph[hpp].nxt = head[from];head[from] = hpp;}bool vis[size];void dfs(int u) {if (vis[u]) return;vis[u] = true;cout << u;for (int p = head[u]; p; p = graph[p].nxt) dfs(graph[p].to);}int main() {int n, m;cin >> n >> m;fill(head, head + n + 1, 0);memset(vis, 0, sizeof vis);for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;addEdge(u, v, w);}dfs(1);}
邻接表代码如下：
#include <iostream>const int size = 100001;using namespace std;vector <int> graph[size];bool vis[size];void dfs(int u) {if (vis[u]) return;vis[u] = true;cout << u;for (auto p: g[u]) dfs(p);// C++11新特性，for (auto var: vectorName/setName) var为遍历所求得的值}int main() {int n, m;cin >> n >> m;while (m--) {int u, v;cin >> u >> v >> w;graph[u].push_back(v);}memset(vis, 0, sizeof vis);dfs(1);}
三、图的BFS：
图的BFS与路径BFS基本相同，图的BFS从结点开始，将该结点压入队列中，队列可以用STL容器queue定义，先弹出队首元素（记为 r o o t root root），在查找由 r o o t root root出发的路径的终点，将终点压入队列，直到队列为空。
求BFS(1)
邻接表代码如下：
#include <iostream>#include <queue>const int size = 100001using namespace std;vector <int> graph[size];bool vis[size]queue <int> q;void bfs(int u) {q.push(u);while (!q.empty()) {int v = q.front();q.pop();if (vis[v]) continue;vis[v] = true;cout << v;for (auto p: g[v]) q.push(p);}}int main() {int n, m;cin >> n >> m;while (m--) {int u, v, w;cin >> u >> v;;g[u].push_back(v);}memset(vis, 0, sizeof vis);bfs(1);}
链式前向星代码：
#include <iostream>using namespace std;const int size = 100001;struct edge {int to, w, nxt;} graph[size];int head[size], hpp = 0;void addEdge(int from, int to, int weight) {hpp++, graph[hpp].to = to, graph[hpp].w = w, graph[hpp].nxt = head[from];head[from] = hpp;}bool vis[size];queue <int> q;void bfs(int u) {q.push(u);while (!q.empty()) {int v = q.front();q.pop();if (vis[v]) continue;vis[v] = true;cout << v;for (int p = head[u]; p; p = graph[p].nxt) q.push(graph[p].to);}}int main() {int n, m;cin >> n >> m;fill(head, head + n + 1, 0); //初始化head数组，也可用for循环memset(vis, 0, sizeof vis);for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;addEdge(u, v, w);}bfs(1);}
OJ例题：洛谷—查找文献
题解，本题就是要求图的DFS和BFS，体重一大坑点就是要求排序，所以可以sort每一个vector。
题解：
#include <bits/stdc++.h>using namespace std;vector <int> graph[100001];bool vis[100001];void dfs(int u) {if (vis[u]) return;vis[u] = true;cout << u << " ";for (auto p: graph[u]) dfs(p);}queue <int> q;void bfs(int u) {q.push(u);while (!q.empty()) {int v = q.front();q.pop();if (vis[v]) continue;vis[v] = true;cout << v << " ";for (auto p: graph[v]) q.push(p);}}int main() {int n, m;cin >> n >> m;while (m--) {int u, v;cin >> u >> v;graph[u].insert(v);}for (int i = 1; i <= n; i++) sort(graph[i].begin(), graph[i].end());memset(vis, 0, sizeof vis);dfs(1);cout << endl;memset(vis, 0, sizeof vis);bfs(1);}
