一、数组模拟有向图的理解
// 图的基本参数:n节点,m条边
int n, m;
int h[n], idx=0, e[n], ne[n];
void add(int a, int b)
{
// idx表示寻找节点的指针
// e表示指针idx可以寻找到的节点:e[idx] = b
// h表示节点值a直接对应的头指针:e[h[a]] = 头指针对应的节点
// ne表示idx轴上,节点e对应的下一个节点的指针:e[ne[b]] = b的下一个节点的节点值
e[idx] = b, ne[idx] = h[a], h[a] = idx;
// 生成新的地址用来作为指针值
idx ++ ;
}
图的基本节点值:1~n(或者此作为编号,另外设置数组value[]存储每个节点实际的节点值)
图的表头节点:h[1 ~ n],初始化为-1,所以每次循环遍历边链表时寻找到-1则表示链表尾部
图的邻接表:每次寻找边从h[a]开始,找到初始化值-1结束,可以将idx视为一个生成地址的轴,每个轴点一一对应着节点值(取e[]实现),每个轴点包含一个指向前面节点的指针(取ne[]实现)