图的储存
1177 字
6 分钟
图的储存
为了储存一张图，发明算法的人们费劲了心思，极其主要的，有以下几种．
邻接矩阵
我们定义一个二维数组 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; // 初始化 } }}邻接矩阵很简单，也很容易写，但很低效，很占用空间，在上面的题目中， 达到了 ，明显会 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;}显然，这种方法解决了邻接矩阵可能出现的问题，例题可以使用．
链式前向星
当然，还有更加优雅的方式．
我们为每一条边编号，储存每一条边．
我们尝试将最新的边，定义为编号最大的边．
我们定义：
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}如何遍历一个链式前向星呢？
其实很像 邻接表，采用“顺藤摸瓜”的方式可以遍历邻接链表．
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]这个点的边的编号 }}稍微整合一下，将 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... }}特别要当心的是，此处的 now 和 j 并非表示一条边的终点，而是一条边的编号．所以获得这条边的终点需要使用 to[j]．
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！