目录
图的存储与一般有三种形式，邻接矩阵、邻接表、链式前向星（邻接表的一种）。
本文全文使用这个图来进行演示。
我们规定，一共有 $n$ 个点，$m$ 条边。输入数据的格式为 “起点”、“终点”、“边权”。则这个图的输入数据为:
1 2 2
1 4 3
2 3 1
2 5 3
3 1 2
5 3 2
5 4 4
邻接矩阵
由于邻接矩阵空间消耗巨大，一般不使用。
邻接矩阵初始化时，我们使用无穷。
#define INF LLONG_MAX
typedef long long ll;
const int MAXN = 1000 + 1;
ll adj_matrix[MAXN][MAXN]; // 邻接矩阵声明，若为不带权图，则可以将 long long 改为 bool.
inline void addEdge(int prev, int next, ll w = 1) { // 加边，默认为有向图，边权默认为 1，便于使用不带权图
adj_matrix[prev][next] = w;
}
void init(int maxn, bool is_zero = false) { // 初始化
if (is_zero) return; // 若初始化为 0 则直接退出
for (int i = 1; i <= maxn; i++) // 外循环
for (int j = 1; j <= maxn; j++) { // 内循环
if (i == j) continue; // 若起点终点则初始化为 0
adj_matrix[i][j] = INF; // 否则初始化为无穷大
}
}
void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权
int a = 0, b = 0, w = 1; // 声明变量
for (int i = 1; i <= m; i++) { // 开始读入数据
scanf(
if (have_weight) scanf(
addEdge(a, b, w); // 加边
if (!directed) addEdge(b, a, w); // 若不带方向，即为无向图，添加反向边
}
}
void traversal(int amount_of_vertexes) { // 遍历，传入参数为点数
for (int i = 1; i <= amount_of_vertexes; i++)
for (int j = 1; j <= amount_of_vertexes; j++) {
if (i == j) continue;
if (adj_matrix[i][j] != INF) ; //操作一下
}
}
下面我们将介绍一种更加优越的存储方式。
邻接表
邻接表，是一种十分神奇的东西，它的基本组成是节点数组和边链表。
像之前那个图，邻接表如下：
根据输入可以发现，邻接表是一种动态存储方式。
邻接表的边是倒序存储的，也就是说，邻接表的构建和输入顺序是有关联的，但并不影响。
邻接表可以存储重边和自环。
事实上，边链表相对输入顺序，是倒序存储的。
显然，动态建图存储的时间、空间复杂度为 $\text{O}(m)$。
遍历的时间复杂度为 $\text{O}(m)$。
可以看出，因为邻接表使用了链表，因此内存管理是一个大问题，而且写起来也略微麻烦。
模板如下：
typedef long long ll;
const int MAXN = 1000 + 1;
struct Node {
struct Edge *firstEdge; // 第一条边 (事实上是最后一条边，因为倒序)
Node() {
firstEdge = NULL; // 设置指针初值为空
}
} Graph[MAXN];
struct Edge {
Node *prev, *next; // 前驱点、后继点
ll w; // 权值
Edge *nextEdge; // 下一条边 (事实上是上一条边，因为倒序)
Edge(Node *const &prev, Node *const &next, const ll &w) : prev(prev), next(next), w(w), nextEdge(prev->firstEdge) {} // 构造函数，利用 initializer list，自动设置 nextEdge 为下(事实上为上)一条边。
};
inline void addEdge(int prev, int next, ll w = 1) { // 添加边，默认有向，边权 w 默认为 1，便于使用不带权图
Graph[prev].firstEdge = new Edge (&Graph[prev], &Graph[next], w);
}
void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权
int a = 0, b = 0, w = 1; // 声明变量
for (int i = 1; i <= m; i++) { // 开始读入数据
scanf(
if (have_weight) scanf(
addEdge(a, b, w); // 加边
if (!directed) addEdge(b, a, w); // 若不带方向，即为无向图，添加反向边
}
}
void traversal(int amount_of_vertexes) { // 遍历，传入参数为点数
for (int i = 1; i <= amount_of_vertexes; i++) {
for (Edge* e = Graph[i].firstEdge; e != NULL; e = e->nextEdge) {
/*e->next ...;
e->prev ...;
...*/ // 此处可以操作
}
}
}
前方高能预警。
链式前向星
链式前向星是一种更加神奇优越的存储方式。
链式前向星的结构为一个点信息数组，一个边信息结构体数组，一个当前处理边的编号计数器。其核心思想是给边编号，这样就能方便地用数组存储了。
链式前向星也可以存储重边和自环。
链式前向星使用了数组来模拟链表，这样就避免了复杂的内存管理。而它是一种类似邻接表的存储方式，因此，也具有空间复杂度低，时间复杂度低的特性。
显然，由于读入完成则建图完成，建图的时间复杂度为 $\text{O}(m)$，存储的空间复杂度为 $\text{O}(n+m)$。
遍历的时间复杂度应该为 $\text{O}(m)$ (个人分析，如有误请指正)。
根据我们的输入，点信息数组 head 的值为：
下标：1 2 3 4 5
数据：2 4 5 0 7
边信息数组中的信息如下：
edges[1].next = 2 ; edges[1].w = 2 ; edges[1].nextEdge = 0
edges[2].next = 4 ; edges[2].w = 3 ; edges[2].nextEdge = 1
edges[3].next = 3 ; edges[3].w = 1 ; edges[3].nextEdge = 0
edges[4].next = 5 ; edges[4].w = 3 ; edges[4].nextEdge = 3
edges[5].next = 1 ; edges[5].w = 2 ; edges[5].nextEdge = 0
edges[6].next = 3 ; edges[6].w = 2 ; edges[6].nextEdge = 0
edges[7].next = 4 ; edges[7].w = 4 ; edges[7].nextEdge = 6
模板如下：
const int MAXN = 1000, MAXM = 2000;
int head[MAXN]; // 存储点的信息
int edge_count; // 当前处理的边的编号
struct Edge {
int prev, next, nextEdge; // 前驱、后继、下一条边
long long w; // 边权值
} edges[MAXM];
void addEdge(int const a, int const b, int w = 1) {
edges[++edge_count].prev = a; // 设置前驱点为起点 a，++edge_count 令当前处理的边的编号 +1
edges[edge_count].next = b; // 设置后继点为终点 b
edges[edge_count].w = w; // 设置边权
edges[edge_count].nextEdge = head[a]; // 从点信息数组 head 中取出下一条边的编号，若当前为第一条边则取出初值 0
head[a] = edge_count; // 记录当前的边编号到点信息数组 head 中，为下一条边的增添做准备
}
void read(int const m, bool directed = true, bool have_weight = true) { // m 为数据组数，即边数，directed 为是否有向，have_weight 为是否带权
int a = 0, b = 0, w = 1; // 声明变量
for (int i = 1; i <= m; i++) { // 开始读入数据
scanf(
if (have_weight) scanf(
addEdge(a, b, w); // 加边
if (!directed) addEdge(b, a, w); // 若不带方向，即为无向图，添加反向边
}
}
void traversal(int const n) { // n 为点数
for (int i = 1; i <= n; i++) { // 从第 1 个点开始遍历
for (int k = head[i]; k; k = edges[k].nextEdge) { // 令 k 为第 1 条边，直到最后一条边，当 k 到达最后一条边时为 0，结束遍历。
// do something.
}
}
}
事实上，除了不能像邻接矩阵那样直接判断两个点之间是否连通，链式前向星几乎是完美的。
在实际应用中，也可以根据题目读入的数据，通过动态数组来做，能够进一步优化空间开销。