存边的结构,也是挺简单的,重点就三个数组h,ne,e和一个变量idx
idx是index索引的缩写,这就是它的作用,索引。
时间空间复杂度都是$O(n + m)$很不错
h是存的表头,ne存的是下一个点的idx,e是当前点的序号,一般还有一个w存的是当前点的权值
更详细一些
h[a]
表示a的表头,里面存储的是a所连向点b的idx,而e[idx]
就是b点的序号b,ne[idx]
是a连向的下一个边的idx,w[idx]
存的是权值。
这都有什么用?
看看加边代码
void add(int a, int b, int c) // 从a向b连一条权值为c的边
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
现在来说说这些量是怎么存边的。
首先idx开始为0,且此时没有被任何一条边使用。
开始我们让h[a] = -1
-1表示没有,即a现在不连向任何一条边
现在加入一条从a连向b的边
这时候索引idx,正好没用我们把它分配给这条边。
这条边的终点e[idx] = b
,我们让ne[idx] = h[a], h[a] = idx
表示a里面添加了一个索引idx,通过h[a]
就能找到这个点,再通过ne[idx]
就能找到之前存的点,而这条边的信息e[idx]
,也有idx所关联。就相当于存起来了。
给一张好懂的图
关于w,它和e作用一样都是存储当前边信息的
而加边,就是让ne[idx0] = h[a]
也就是ne[idx0] = idx1
然后让h[a] = idx0
即可