链式前向星核心代码解析 ← 数组模拟邻接表

83 阅读 0 评论 55 点赞

我是靠谱客的博主鲤鱼黄豆，最近开发中收集的这篇文章主要介绍链式前向星核心代码解析 ← 数组模拟邻接表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【知识点】
在图论算法实现中，常使用C++标准库STL自带的vector来模拟邻接表存图。详见：
https://blog.csdn.net/hnjzsyjyj/article/details/101233779
https://blog.csdn.net/hnjzsyjyj/article/details/101233485
https://blog.csdn.net/hnjzsyjyj/article/details/101233249
但是，在算法竞赛中，使用C++标准库STL自带的vector来模拟邻接表存图的方法，对某些复杂问题会超时。此外，在处理网络流问题中的构建反向边等操作时会麻烦一些。据此，可引入链式前向星这种用数组模拟邻接表存图的优秀数据结构。

本质上，链式前向星是以存储边的方式来存储图。换句话说，链式前向星是一种特殊的边集数组。
链式前向星特别适合用来优化 SPFA、DFS、BFS。

链式前向星的核心代码如下所述。其中：
val[idx] 表示第 idx 条边的权值。
e[idx] 表示第 idx 条边的终点。
ne[idx] 表示与第 idx 条边同起点的最近一次被添加的边的编号。
h[a] 表示以结点 a 为起点的最近一次被添加的边的编号。这个表述是在使用 ne[idx]=h[a] 时，也即使用 h[a]=idx++ 更新 h[a] 之前而言的。要特别注意这个语境。
很明显，h[a] 中存储的是以 a 为起点的所有边中编号最大的那个。且在遍历时，把这条边作为以 a 为起点的所有边中的第一条边进行遍历。即边的遍历顺序与输入顺序恰好是相反的。而网上常见的表述“e[idx] 表示第 idx 条边的终点，ne[idx] 表示与第 idx 条边同起点的下一条边的存储位置，h[a] 表示以 a 为起点的第一条边的存储位置”，是按边的遍历顺序进行表述的。

在上述约定下，则有：
● 链式前向星的核心代码如下：

void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

如果是有权图，需多设置一个数组 val[] 存储权值。有权图的链式前向星的核心代码如下：

void add(int a,int b,int w) {
val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

● 基于链式前向星的深度优先搜索（DFS）的核心代码如下：

void dfs(int u) {
cout<<u<<" ";
st[u]=true;
for(int i=h[u]; ~i; i=ne[i]) { //~i; equivalent to i!=-1;
int j=e[i];
if(!st[j]) {
dfs(j);
}
}
}

● 基于链式前向星的广度优先搜索（BFS）的核心代码如下：

void bfs(int u) {
queue<int>q;
st[u]=true;
q.push(u);
while(!q.empty()) {
int t=q.front();
q.pop();
cout<<t<<" ";
for(int i=h[t]; ~i; i=ne[i]) { //~i; equivalent to i!=-1;
int j=e[i];
if(!st[j]) {
q.push(j);
st[j]=true; //need to be flagged immediately after being queued
}
}
}
}

【参考文献】
https://zhuanlan.zhihu.com/p/343092172
https://malash.me/200910/linked-forward-star/
https://www.acwing.com/solution/content/124095/
https://blog.csdn.net/hnjzsyjyj/article/details/119917795
https://blog.csdn.net/hnjzsyjyj/article/details/103778724