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

【知识点】 在图论算法实现中，常使用C++标准库STL自带的vector来模拟邻接表存图。详见： 但是，在算法竞赛中，使用C++标准库STL自带的vector来模拟邻接表存图的方法，对某些复杂问题会超时。此外，在处理网络流问题中的构建反向边等操作时会麻烦一些。据此，可引入链式前向星这种用数组模拟邻接表存图的优秀数据结构。 本质上，链式前向星是以存储边的方式来存储图。换句话说，链式前向星是一种特殊的边集数组。 链式前向星特别适合用来优化 SPFA、DFS、BFS。 链式前向星的核心代码如下所述。其中： e[i] 表示第 i 条边的终点； ne[i] 表示与第 i 条边同起点的前一条边的编号（按边的添加顺序）； h[i] 表示以 i 为起点的当前边的编号（按边的添加顺序）。 很明显，h[i] 中存储的是以 i 为起点的所有边中编号最大的那个。且在遍历时，把这条边作为以 i 为起点的所有边中的第一条边进行遍历。即边的遍历顺序与输入顺序恰好是相反的。而网上常见的表述“e[i] 表示第 i 条边的终点，ne[i] 表示与第 i 条边同起点的下一条边的存储位置，h[i] 表示以 i 为起点的第一条边的存储位置”，是按边的遍历顺序进行表述的。 在上述约定下，则有： ● 链式前向星的核心代码如下：

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
			}
		}
	}