- 邻接表:h[N]表示有N个顶点,也就会有N个列表,这N个列表就是图G的邻接表。其中,h[i]存放顶点i的所有出边组成的列表
- e[i] ne[i] 中的i并不是顶点号 e[i]的值才是顶点号 i的值随便是多少 ne[i]的值是e[j]中的j,也并不是顶点
- h[i]中的i才是顶点 h[i]并不是头节点 而是头指针 指向头节点的指针
- w[i]:边的权重是多少
-
h[N]: head 头指针 其值相当于地址空间
- e: edge[地址], 其值为边的另一个点
- ne: ne[地址1], 其中表示为地址2,表示地址指针。
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b) //添加边a到b 即需要在顶点a构成的邻接表中添加一个顶点b 头插法
{
e[idx] = b;//用一个节点存下顶点b
ne[idx] = h[a];//将节点idx指向的节点连接上a顶点指向的节点(即原来的头节点 )
h[a] = idx ++ ; //将头指针的指向更新为新的头节点
}
// 初始化
idx = 0;
memset(h, -1, sizeof h); //初始化 所有的头指针指向-1