定义
邻接表是树与图结构的一般化存储方式，还能用于实现开散列Hash表。领接表可以看做成“带有索引数组的多个数据链表”构成的结构集合。在这样的结构中存储的数据被分为若干类，每一类的数据构成一个链表。每一类还有一个代表元素，称为该类对应链表的“表头”。所有“表头”构成一个表头数组，作为一个可以随机访问的索引，从而可以通过表头数据定位到某一类数据对应的链表。
模板代码
const int N = 1e4 + 5, M = 1e5 + 5;
int ver[M]; //顶点集合
int edge[M]; //边权值集合
int head[N]; //父顶点集合，指向其能到达的第一个子节点序号
int Next[M]; //本节点能到达的下一个节点序号
int tot; //节点个数，序号
bool v[N];
//加入有向边 (x,y)，权值为z
void add(int x, int y, int z) {
ver[++tot] = y;
edge[tot] = z;
Next[tot] = head[x];
head[x] = tot;
}
//访问从 x 出发的所有点
void vis(int x) {
v[x] = true;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i], z = edge[i];
if(!v[y]) vis(y);
}
}
| 标题： | 信息学竞赛模板（十）— 邻接表 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/70 |
| 更新： | 2022-09-18 22:36:19 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |