邻接表+链式前向星

邻接表

• 1. 邻接表

1. 邻接表

• 邻接表存储图需要注意的要点有：

1. 模板采用的是无向图，所以最大边数 $M$ 开到了题目所给最大边数的两倍，如果是有向图，那么在建边的时候，只需要建一次即可，比如 $a$ 到 $b$ 有一条边，那么只需要 $add(a,b)$ ，不需要 $add(b,a)$ 对称建边
2. 链式前向星（也称数组模拟邻接表）的数据结构为：

int h[N]; // h[i]:第i个顶点的起始边编号,默认从-1开始
int ne[M]; // ne[idx]:第idx条边的下一条边的编号
int e[M]; // e[idx]:第idx条边指向的节点的编号
int idx; // 边的编号

• 注意，数组 $h$ 应被初始化为 $-1$ ，表示所有顶点的起始边编号是 $-1$ ，可以理解为头结点，因为采用的是头插法，如果顶点 $i$ 没有与其直接相连的边，那么 $h[i]=-1$，如果顶点 $i$ 有与其直接相连的边，那么顶点 $i$ 的邻接表的最后一个元素是 $-1$

此处表格参考博客：CSDN博客

3. 重点讲解链式前向星，假设现在有五条边有向边， $(1,4),\ (4,3),\ (1,2),\ (2,4),\ (1,3)$ ，对应执行 $add(1,4),\ add(4,3),\ add(1,2),\ add(2,4),\ add(1,3)$，我们手动模拟一下建边过程应该是这样的

// 建边(链式前向星)[头插法]
void add(int a,int b) {
	e[idx]=b; // 第idx条边指向顶点b
	ne[idx]=h[a]; // 第idx条边的下一条边是顶点a的起始边[体现头插法思想]
	h[a]=idx++; // 顶点a的下一条边是第idx条边,编号+1以表示下一条边
}

add(a,b)	idx	e[idx]=b, ne[idx]=h[a],h[a]=idx++
(1,4)	1	e[1]=4, ne[1]=h[1]=-1, h[1]=1, idx=2
(4,3)	2	e[2]=3, ne[2]=h[4]=-1, h[4]=2, idx=3
(1,2)	3	e[3]=2, ne[3]=h[1]=1, h[1]=3, idx=4
(2,4)	4	e[4]=2, ne[4]=h[2]=-1, h[2]=4, idx=5
(1,3)	5	e[5]=3, ne[5]=h[1]=3, h[1]=5, idx=6

3. 建边完成后，每个数组的情况应该是（下标均从 $0$ 开始）：

   • $h=[-1, 4, 3, -1, 1, -1]$

   • $ne=[-1, -1, 0, -1, 2]$

   • $e=[4, 3, 2, 4, 3]$

• 比如我们现在要输出与顶点 $1$ 直接相连的边，代码最终会输出 $3\ 2\ 4$，因为采用的是头插法，所以边的遍历顺序是 $(1,3),\ (1,2),\ (1,4)$

// j初始化为顶点1的起始边,因为最后一条边的编号一定为-1(头插法),然后j通过ne数组迭代到下一条相连边的编号
for(int j=h[1];j!=-1;j=ne[j]) {
    cout<<e[j]<<' '; // e[j]:编号为j的边指向的顶点编号
}

• 完整样例代码，注意代码中的模拟数据和前文不同，并且采用无向图建边，如果从无向图建边改为有向图建边前文已介绍

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 邻接表、链式前向星模板

const int N=1e3+5; // 最大顶点数
const int M=(1e5+5)*2; // 最大边数,因为无向图是双向建边,所以要*2

int h[N]; // h[i]:第i个顶点的起始边编号,默认从-1开始
int ne[M]; // ne[idx]:第idx条边的下一条边的编号
int e[M]; // e[idx]:第idx条边指向的节点的编号
int idx; // 边的编号

// 建边(链式前向星)[头插法]
void add(int a,int b) {
	e[idx]=b; // 第idx条边指向顶点b
	ne[idx]=h[a]; // 第idx条边的下一条边是顶点a的起始边[体现头插法思想]
	h[a]=idx++; // 顶点a的下一条边是第idx条边,编号+1以表示下一条边
}

int main() {
	memset(h,-1,sizeof h); // 每个顶点的起始边编号初始化为-1
	add(1,2),add(2,1);
	add(2,3),add(3,2);
	add(3,5),add(5,3);
	add(1,3),add(3,1);
	add(3,4),add(4,3);
	// 遍历每个顶点,输出与其直接相邻的所有顶点
	for(int i=1;i<=5;i++) {
		vector<int> s;
		// 从顶点i的起始边开始搜索,因为是头插,所以-1最终会变成最后一个边的编号,遇到则停止,通过ne数组迭代到下一条边的编号
		for(int j=h[i];j!=-1;j=ne[j]) {
			s.push_back(e[j]); // e里面存储的是顶点编号
		}
		sort(s.begin(),s.end());
		cout<<"与顶点 "<<i<<" 直接相连的顶点有:";
		for(auto item:s) cout<<item<<' ';
		cout<<endl;
	}
	return 0;
}

打赏