理解ACW邻接表

更新：原来这个东西有个名字叫“链式前向星”……孤陋寡闻了。跟链表的最大区别就是需要预先开好空间（当然空间如果不够也可以new）。

核心：与数据结构课不同，ACW邻接表是从头插入的！

在理解邻接表时，先入为主地按照了尾插法去思考，所以总是对不上。实际上最重要的是它使用的是头插法。
因为抽象思考能力很差（没错就是这么菜），这里用一个形象的方式模拟观察一下。

add函数：

void add(int a, int b, int c)  // 添加一条边a->b，距离为c
{
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
  // e = dst, ne = h(from), h(from) = idx
}

模拟：

• 插入 a-b：

  id	0 -> h[a]	-	-	-
  e	b	-	-	-
  w	w(a,b)	-	-	-
  ne	= h[a] = -1	-	-	-

• 插入 a-c:

  id	0	1 -> h[a]	-	-
  e	b	c	-	-
  w	w(a,b)	w(a,c)	-	-
  ne	-1	0	-	-

• 插入 a-d:

  id	0	1	2 -> h[a]	-
  e	b	c	d	-
  w	w(a,b)	w(a,c)	w(a,d)	-
  ne	-1	0	1	-

• 插入 e-f：

  id	0	1	2 -> h[a]	3 ->h[e]
  e	b	c	d	f
  w	w(a,b)	w(a,c)	w(a,d)	w(e,f)
  ne	-1	0	1	-1

总结

• 一开始h数组初始化为-1，在第一次创建节点是他的ne就是-1，相当于实现指向空指针
• 之后每次有新节点，他的next指向头结点指向的节点，并且头结点指向新的节点
• 理解邻接表添加节点时使用的是头插