邻接表存储和遍历的标准模板

tech2025-10-07  2

 邻接表声明

int h[N], e[M], w[M], ne[M], idx; //邻接表 N节点个数,M边个数 其中 h[a] 指向a节点起点的邻接表列表的最后一个元素。 e[idx] 为当前idx编号的边指向的终点节点 w[idx] 为当前idx编号的边权重 ne 存储邻接表链表,当前值对应邻接表中下一个的地址,类似于值是指针。

 邻接表构建

void add(int a, int b, int c) { //构建邻接表 e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; //h[a] 一直指向a邻接表头插法起点,其实是最后一个,指针保留的方式也是向前 } 1. idx一直向前,如果a是第一次出现,则h[a]的值对应ne中位置即是起点。 2. 插入的方式是类似头插法,每次邻接表中的新元素出现,则插入邻接链表的第一个。也可以这样理解,是每次插到最后,让h[a]指向最后一个元素,遍历的时候倒着向前遍历。 3. 如果指向下一个为空时,指针值为-1.

 

邻接表遍历

for(int i = h[vel]; i != -1; i = ne[i]) { //TODO } i = ne[i] 模拟链表指针的next操作 h[vel] 指向vel链表的最后一个,遍历是从后往前的

 

最新回复(0)