链式前向星

const int N;
const int M = 2 * N;    //每条边会被存俩次,所以空间为点的两倍
int e[M],ne[M],h[N],idx;

其中

• e[ i ] 表示 下标 为 i 的点的编号
• ne[ i ] 表示下标为 i 的点的next结点的下标( 如无next则将其置为 -1 )
• h[ i ] 表示 编号 为 i 的点的next结点的下标

//建边
void add(int a,int b)   //建立一条由a指向b的边
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

//遍历结点a的所有子节点
for(int i = h[a]; i != -1; i = ne[i])
{
    int j = e[i];
    cout << j;
}

q1 : 为什么 i = ne[ i ] 遍历的是 a 的所有子节点,而不是 a 的路径?

add(1, 2); add(2, 1); // 1-2双向边
add(1, 3); add(3, 1); // 1-3双向边
add(2, 4); add(4, 2); // 2-4双向边
add(3, 5); add(5, 3); // 3-5双向边

得到如下的树:

我们逐个进行分析:

add(1,2): e[0] = 2,ne[0] = -1,h[1] = 0; (idx + 1 变为 1)
add(2,1): e[1] = 1,ne[1] = -1,h[2] = 1; (idx + 1 变为 2)
add(1,3): e[2] = 3,ne[2] = 0, h[1] = 2; (idx + 1 变为 3)
add(3,1): e[3] = 1,ne[3] = -1,h[3] = 3; (idx + 1 变为 4)
...

看第三行的代码可以发现,当运行到第三行时,编号为 2 的结点后面时没有结点的,但他的 ne 并不为 -1 ,而是指向了idx 为 0 的结点 3

至此我们可以发现: 链式前向星的存储与树的样子并不相似 , ne 存的并不是树里面的下一个节点 .

而是一条以某个结点作为链表头的一条锁链 : i –> i的子节点 –> i的另一个子节点…

所以我们在遍历时, i = h[ a ] 此时 i 为最后一个与点 a 建边的结点的下标 , 这个结点的 ne 指向的是倒数第二个与结点 a 建边的结点 , 这样就把点 a 的所有子节点都遍历了.

至此就可以解决第二个问题:
q2 : 为什么 h 只需要开 N 的空间?

因为 h 所表示的是一个链表:

h[ i ] : 子节点 –> 子节点 –> 子节点…

有几个结点,就有几条这样的链表,所以 h 只需要开到 N 即可