图的存储

图的存储方式

图的主要存储方式有两种：

• 邻接矩阵
• 邻接表

邻接矩阵

对于一个有 $n$ 个点的简单图，使用 $n\times n$ 的二维数组存储，假定二维数组名为 $g$，则 $g[i][j]$ 表示节点 $i$ 与节点 $j$ 之间边的边权。

• 复杂度分析
  空间复杂度：$O(n^2)$，
  调用每条边的时间复杂度：$O(1)$，
  调用一个节点所有边的时间复杂度：$O(n)$。

邻接表

vector 存储

对于一个有 $n$ 个结点的图，我们开 $n$ 个变长数组 vector 进行存储，其中第 $i$ 个 vector 中的元素是从点 $i$ 出发经一条边能到达的点，即点 $i$ 的所有出边。

如果用邻接矩阵存一张带权图，通常使用 pair 或结构体，用 $v[i]$ 表示第 $i$ 个 vector，那么 v[i][j].to 可以表示点 $i$ 的第 $j$ 条出边连向哪个点，v[i][j].wt 表示这条边的权值。

👑链式前向星

由于 vector 的大常数和特殊时空需求，我们需要另一种方式存储邻接表，那么，我们就可以写一种新的存储方式：链式前向星。

链式前向行是一种类似于链表的邻接表存储结构，其空间复杂度为 $O(m+n)$，访问一个点邻接的所有变得时间复杂度相当于这个点邻接的边数，不支持访问单条边。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5, M = 1e6+7;
int hd[N],tot;
struct node {
    int to,nx,wt; //如果是无权边就忽略wt变量
} eg[M];
void adeg(int st,int ed,int wt) {
    eg[++tot]={ed,wt,hd[st]};
    hd[st]=tot;
}
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;++i) {
        int u,v,w;
        cin>>u>>v>>w;
        adeg(u,v,w);
        adeg(v,u,w); //如果是有向图删掉本行
    }
    for(int i=1;i<=n;++i) {
        for(int j=hd[i];j;j=eg[j].nx)

    return 0;
}