为了储存一张图，发明算法的人们费劲了心思，极其主要的，有以下几种．

邻接矩阵#

我们定义一个二维数组 g[i][j]，表示从点 i 到点 j 的权重．千万要记得初始化．

#define N (int)1e5 // 最多可能有的节点数
#define INF 0xffffff // 极大值，代表无穷

int g[N][N]

void addEdge(int u, int v, int w)
{
    g[u][v] = w;
    // g[v][u] = w; // 如果是无向图的话
}

int getWeight(int u, int v)
{
    return g[u][v];
}

int main()
{
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = INF; // 初始化
        }
    }
}

cpp

邻接矩阵很简单，也很容易写，但很低效，很占用空间，在上面的题目中， $n$ 达到了 $10^5$ ，明显会 MLE．

邻接表#

为了解决邻接矩阵占用空间的问题，我们可以定义 vector<Node> v[N] 来创建一个邻接链表．

对于 v[i]，会存储所有以 i 为起点的边的终点．

#define N (int)1e5 // 最多可能有的节点数
#define INF 0xffffff // 极大值，代表无穷

// Node储存一个节点
struct Node
{
    int id; // 编号
    int w; // 权重
}

vector<Node> v[N];

// 添加一条边
void addEdge(int u, int v, int w)
{
    v[u].push_back({v, w});
    // v[v].push_back({u, w}); // 如果是无向图的话
}

// 获取权值
int getWeight(int u, int v)
{
    for(int i = 0; i < v[u].size(); i++){ // 遍历以u为起点的边
        if (v[u][i].id == v) return v[u][i].w;
    }
    return INF;
}

cpp

显然，这种方法解决了邻接矩阵可能出现的问题，例题可以使用．

链式前向星#

当然，还有更加优雅的方式．

我们为每一条边编号，储存每一条边．

我们尝试将最新的边，定义为编号最大的边．

我们定义：

cnt，表示当前所有边中，编号最大的一条边．储存的是边的编号．
fi[i]，表示最新的、且指向编号为 i 的点的边的编号．注意：i 是点的编号，储存的值是边的编号．
to[i]，表示编号为 i 的边的终点．注意：i 是边的编号，而储存的值是点的编号．
ne[i]，表示编号比边 i 较小的一条，同样指向 to[i] 的边．注意：i 和储存的值都是边的编号．
co[i]，表示编号为 i 的边的权值．注意：i 是边的编号，储存的值是权值．

#define N (int)1e5 // 最多可能有的节点数
#define M (int)2e5 // 最多可能有的边数
#define INF 0xffffff // 极大值，代表无穷

int cnt; // 目前边的总数
int fi[N]; // fi[i]（即first）表示最新的、指向编号为i的点的边编号
int ne[M]; // ne[i]（即next）表示除去编号为i的这条边外，最新的，指向to[i]的边的编号
int to[M]; // to[i]表示编号为i的边指向的节点编号
int co[M]; // co[i]（即cost）表示编号为i的边的权值

// 增加一条以u为起点，v为终点，权值为w的边
void add(int u, int v, int w){
    cnt++; // 将总数加1，加1后的cnt就是现在要加的这条边的编号
    ne[cnt] = fi[u]; // 将这条边的下一个同源边设定为未更新过的fi[u]
    fi[u] = cnt; // 更新fi[u]，将最新的、从u发出的边（fi[u]）设为当前边
    to[cnt] = v; co[cnt] = w; // 将当前的边的终点设为v，花费设为w
}

cpp

如何遍历一个链式前向星呢？

其实很像邻接表，采用“顺藤摸瓜”的方式可以遍历邻接链表．

for(int i = 1; i <= n; i++){
    int now; // 定义now表示这条以i为起点的边的终点
    now = fi[i]; // 初始化now为最新的、指向编号为i的点的边的编号
    while(now != 0){ // 检查是否遍历完成
        // 你可以在这里，获取到一条从i到to[now]，权重为co[now]的边
        // Do something...
        now = ne[now];
        // 将j设定为除去编号为j的这条边外，最新的，指向to[j]这个点的边的编号
    }
}

cpp

稍微整合一下，将 now 变成 j，就可以有更加优雅的方式：

for(int i = 1; i <= n; i++){ // 遍历每一个点i
    for(
        int j = fi[i]; // 初始化j为最新的、指向编号为i的点的边的编号
        j != 0; // 检查是否遍历完成
        j = ne[j] // 将j设定为除去编号为j的这条边外，最新的，指向to[j]的边的编号
    ){
        // 你可以在这里，获取到一条从i到to[j]，权重为co[j]的边
        // Do something...
    }
}

cpp

特别要当心的是，此处的 now 和 j 并非表示一条边的终点，而是一条边的编号．所以获得这条边的终点需要使用 to[j]．

图的储存

邻接矩阵#

邻接表#

链式前向星#