设有向图 $G=(V,E)$, 令 $n=|V|$, $m=|E|$，$(x,y)$表示一条从 $x$ 到$y$ 的有向边，并记该条边的边权为$w(x,y)$。
存储 $G$时，我们一般使用两种存储结构：邻接矩阵和邻接表。如果$G$ 是无向图，我们可以把无向边看作两条方向相反的有向边，从而使用与有向图相同的方式存储。
邻接矩阵
当 $G$是稠密图且 $n$ 不太大（当内存限制为256MB时，一般有$n \leq 8192$ )时，一般使用邻接矩阵来存储。
邻接矩阵是一个大小为 $n^{2}$ 的矩阵，定义为： $$ A[i,j]=\left{\begin{matrix}0,i=j & \ w(i,j),(i,j)\in E & \ +\infty ,(i,j)\notin E & \end{matrix}\right. $$ 显然，邻接矩阵判断两点之间是否有有向边只需要 $O(1)$的时间复杂度，计算某点的出度和入度只需要分别遍历以该点为下标的行和列中介于 $0$和$+\infty$ 之间的值的数目即可。但显然，邻接矩阵的空间复杂度为$O(n^{2})$ ，且在存储稀疏图时，大量的存储空间被浪费，所以邻接矩阵通常只适合顶点数量较少的稠密图的存储。
const int MAXN = 3010;
int a[MAXN][MAXN], n, m;
// 邻接矩阵的构建
void build() {
scanf("%d %d", &n, &m);
memset(a, 0x3f, sizeof(a));
for(int i = 1; i <= n; i++)
a[i][i] = 0;
for(int i = 1; i <= m; i++) {
int x = 0, y = 0, w = 0;
scanf("%d %d %d", &x, &y, &w);
a[x][y] = min(a[x][y], w); // 当两点间存在多重边时，只记录权值最小的一条
}
}
邻接表
当 $n$ 比较大的时候，我们通常使用邻接表进行存储。
邻接表是存储图和树、以及实现开散列Hash表的通用结构，是多个数据链表的集合。在邻接表中，存储的数据被分为若干类，每类的数据单独存储在一个数据链表中。同时，在每个数据链表中选出一个代表元素，称为对应链表的表头，并将这些表头组成一个可以随机访问的索引数组，通过访问表头数组便可以定位到任一类数据对应的链表。
在存储图时，我们通常将每一类数据定义为每条以同一个顶点为起点的有向边之终点。此时，表头数组的成员是出度不为0的顶点，每个数据链表的成员是以对应表头元素为起点的有向边对应的终点。在向数据链表中加入新成员时，我们直接从表头处插入。因此，在我们遍历数据链表以获得以某个顶点为起点的所有有向边对应的终点集合时，我们的遍历顺序与插入顺序相反。
显然，邻接表的空间复杂度为 $O(n + m)$ 。
因为编写链表时涉及动态内存分配这一比较耗时的操作，所以我们通常使用以下两种方式实现邻接表：
多维Vector
Vector的push_back方法可以让我们很容易地建立邻接表，同时避免使用链表结构。
const int MAXE = 1e5 + 10; // 边的最大数目
vector<int> ver[MAXE], edge[MAXE]; // 存放每条边的终点和边权
// 添加权值为w的有向边(x,y)
void add(int x, int y, int w) {
ver[x].push_back(y);
edge[x].push_back(w);
}
// 遍历从x出发的所有边
int sz = ver[x].size();
for(int i = 0; i < sz; i++) {
int y = ver[x][i], w = edge[x][i];
// PROCEDURE...
}
但多维vector速度很慢（因为也涉及内存分配问题），而且每一次内存分配后会比之前多出50%的空间，可能导致MLE，因此在数据量较大时不宜使用。
数组模拟链表（链式前向星）
众所周知，在存储空间最大值确定时，我们可以用数组来模拟链表，且因为不涉及显式的内存分配操作，所以速度很快。我们也可以采用这一思路实现邻接表。在这种实现方法中，我们使用所谓的边集数组来显式地存储图的边，这种结构又被称作链式前向星。
我们需要以下四个数组进行存储：大小为 $\Omega (m)$的边集数组ver和edge分别存放编号为 $i$的边的终点ver[i]和边权edge[i]，并需要一个大小为 $\Omega (n)$ 的表头数组head来记录从第$j$ 个节点出发的第一条边的编号head[j]。最后，我们还需要一个大小为$\Omega (m)$ 的数组next来模拟指针，表示从相同节点出发的当前边的下一条边的编号。
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
int head[MAXN], ver[MAXM], edge[MAXM], next[MAXM];
int tot; // 表示已存储边的数目
// 初始化邻接表
void init() {
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
tot = 0;
}
// 插入权值为w的有向边(x, y)
void add(int x, int y, int w) {
ver[++tot] = y; edge[tot] = z; // 插入一条编号为++tot的新边
// 模拟插入到链表表头操作
next[tot] = head[x];
head[x] = tot;
}
// 遍历起点为x的所有边
for(int i = head[x]; i; i = next[i]) {
int y = ver[i], z = edge[i];
// PROCEDURE...
}
成对变换
前面讲到，我们可以通过存储两条顶点相同、方向不同的边，来将带权无向图化归为有向图进行存储。假设我们将任一无向边均存储为两条编号相邻的有向边 $i$和 $i + 1$( $1 \leq i \leq m - 1$)，我们可能希望从 $i$ 访问$i + 1$ ，反之亦然。但我们如何得知与当前边$p$ 的反向的边编号是$p - 1$ 还是$p + 1$ 呢？
此时，可以采用位运算的一个小技巧：
$$
k: \mathbf{xor}: 1=\left{\begin{matrix}k+1,, k=2p,, p\in \mathbf{N}
& \ k-1,, k=2p+1,, p\in \mathbf{N}
&
\end{matrix}\right.
$$
亦即，整数对 $(0,1)$, $(2,3)$, $\cdots$, $(2p, 2p+1)$关于运算 $\mathbf{xor} , 1$ 构成变换。从而，我们只需要对任一条边执行$\mathbf{xor} , 1$ 运算，便可获知与其反向的边的编号了。显而易见地，ver[i]为第$i$ 条边的终点，而ver[i xor 1] 为第$i$ 条边的起点。
在使用这一技巧时我们还需注意一点：变量tot应被初始化为1，因为0与1构成成对变换，而0在我们的模板中不是一个合法编号。
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
int head[MAXN], ver[MAXM], edge[MAXM], next[MAXM];
int tot = 1;
void init() {
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
tot = 1;
}
// 分别加入权值均为w的有向边(x, y)和(y, x)
void add(int x, int y, int w) {
ver[++tot] = y; edge[tot] = w;
next[tot] = head[x];
head[x] = tot;
ver[++tot] = x; edge[tot] = w;
next[tot] = head[y];
head[y] = tot;
}
// 遍历起点为x的所有边（及其反向边）
for(int i = head[x]; i; i = next[i]) {
int y1 = ver[i], y2 = ver[i ^ 1], w = edge[i];
// PROCEDURE...
}