用数组模拟链表的方式实现【带权有向图的邻接表】

摘要: 数组模拟链表的方式实现图的邻接表，代码模板

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 邻接表 中，我们学习了邻接表及其应用，在文章 用数组模拟双向循环链表 中，我们学习了用数组模拟的方式实现链表，并用该链表解决了实际问题，同时 结合链表容易删除的特点使用逆向思维 中也介绍了一个思路完全一样的题目，也是用数组模拟链表解决的。

邻接表中的链表实际上也可以用数组模拟的方式来实现，本文我们就来看一下带权有向图的邻接表用数组模拟的实现方式。

---

邻接表

在一个有 n 个点，m 个边的有向图结构中，我们可以把每条边所属的类别定义为该边的起点标号，这样所有边被分为 n 类，其中第 x 类就是由从 x 出发的所有边构成。

通过表头 head[x]，我们可以定位到第 x 类的链表，从而访问从 x 出发的所有边。

例如上图就是在临街表中插入一张 5 个点，6 条边的有向图之后的状态。这 6 条边按照插入的顺序依次是 (1, 2), (2, 3), (2, 5), (3, 5), (5, 4), (5, 1)。左侧是邻接表存储的宏观信息，右侧是用数组模拟链表时，内部数据的实际存储方式。

变量定义与初始化

head 与 next_ 数组保存的是 ver 数组的下标，相当于指针，其中 0 指向空，ver 存储的是每条边的终点。

const int E_SIZE = 2e5; // 总边数
const int V_SIZE = 1e5; // 总点数

int head[V_SIZE]; // head[i] 的值是 ver 下标，相当于链表节点指针
int ver[E_SIZE]; // 边的终点，相当于链表节点的 v 字段
int edge[E_SIZE]; // 边的权重，相当于链表节点的 w 字段
int next_[E_SIZE]; // 相当于链表节点的 next_ 字段

// tot 表示 node 数组(这里是 ver 和 next_)已使用的最右位置，而不是链表长度
int tot; 

void init()
{
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(next_, -1, sizeof(head));
}

加边和访问边的操作

void add(int x, int y, int z)
{
    // 增加有向边 (x, y), 权值为 z
    ver[++tot] = y;
    edge[tot] = z;
    next_[tot] = head[x];
    head[x] = tot; // 在表头 x 处插入
}

// 访问从 x 出发的所有边
for(int i = head[x]; i != -1; i = next_[i])
{
    int y = ver[i];
    int z = edge[i];
    // 找到有向边 (x, y) 其权值为 z
}

例子

在文章 二分图匹配-最大匹配 中有一个二分图匹配的模板题，其中使用 vector 的邻接表和用数据模拟链表的邻接表都做了实现，可以作为本文的代码模板的验证。

在文章 最近公共祖先问题 中有一个最近公共祖先的模板题，其中使用 vector 的邻接表会超时，用数组模拟链表的邻接表可以通过。

在文章 问题规约的艺术：基环树的直径 中有一个求基环树直径的模板题，其中使用 vector 的邻接表会超时，用数组模拟链表的邻接表可以通过。

---