B02 图的存储——信息学奥赛算法_哔哩哔哩_bilibili

图的存储方式

结构体邻接表（链式前向星）

请强记！

struct edge{
    int v,c,nxt;
}e[N];
int h[N],idx;
void add(int a,int b,int w){
    e[++idx]={b,w,h[a]};
    h[a]=idx;
}

邻接表（链式前向星）

由以下3个数组组成

int h[],nxt[],to[]; //头,节点i(i为实际编号)的相邻节点在数组里的编号,节点i的相邻节点的实际编号
int cnt;    //记录节点个数

存储

模拟一下（不一定准确）

插入前	插入9后(连接1,9)
h[1]=3	h[1]=4
nxt={0,0,2}	nxt={0,0,2,3}
cnt=3	cnt=4

当访问1的临边时,让i=h[1],然后不断v=to[i] ( v 是相邻的点的真实编号), i=nxt[i] ,直到nxt[i]为空停止.

void add(int a, int b) {
    to[++cnt] = b;        //新建节点的目标
    nxt[cnt] = h[a];    //头插法
    h[a] = cnt;        //接上
}

遍历

当我们要访问一个点的出边时,从i=h[i]开始向下i=nxt[i],直到nxt[i]==0

int u=1;    //u是目前节点的编号
for(int i=h[u],i;i=nxt[i]){}

邻接矩阵

建立矩阵web[a][b],如果web[a][b]==1,则表示存在 $ a\to b$ 的路径

可按具体环境改变web[a][b]存的内容

Vector存图

连边（无向图）

void add(int a,int b){
    e[a].push_back(b);
    e[b].push_back(a);
}

访问u的邻点

for(int i=0;i<e[u].size();i++){
    int v=e[u][i];
}
//或者
for(int v:e[u]){

}

可以去学习一下:的使用方法。同时了解一下auto类型的使用方法。

对于有边权的情况，我们要么把vector定义为struct或者pair，要么开第二个vector来同步存其边权。