邻接表存储与处理树代码
作者:
常台盘の超炮
,
2022-03-11 15:40:22
,
所有人可见
,
阅读 148
//存储
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
//h[]的下标映射的是权值本身的值
static int idx = 0;
static void add(int a,int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
Arrays.fill(h, -1);//注意需要初始化h[]的值全为-1
//怎么说呢,e[]存的是各结点的权值,ne[]存的是各个结点的连着的下一个结点的idx,他们通过下标idx联系起来
//idx在这里的写法是每写一次++一次,所以不会有什么规律对应权值
//处理
//我们想要开始从权值为u的点为根遍历的话,先通过h[u]取得这个u的idx
static void dfs(u){
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
//j就是u后面的第一个权值
dfs(j,u);
}
}