链式前向星(存的是边)

yuanheci 2024年08月09日 49次浏览

邻接表&链式前向星

组成:

  • idx 记录边的序号
  • 邻接表包括四个数组:e、w、ne、h

add(a, b) 时:

e[idx] = b:表示第 idx 条边通向 b 点
w[idx] = c:表示第 idx 条边的权值为 c
ne[idx] = h[a]:表示以a为起点的第 idx 条边的下一条边为 h[a](-1表示无边)
h[a] = idx++:把这条边idx赋给a这个结点,表示点 a 的上一条边为 idx (有点类似于头插法,在一条链上用头插法,插入了一条边)

边号idx通过ne数组可以一直往后走(是结点u所拥有的边)
for(int i = h[u]; ~i; i = ne[i])

其中 h 数组的大小是点数,其他三个数组的大小都是边数。