图论链表存图 – 加边法的个人详解

存储变量

const int V = 510,E = 1e5;//分别为边(V)的个数和点(E)的个数
int h[V],e[E],ne[E],w[E],idx; //e,ne,w,都需要初始化为为边的最大个数

初始化

memset(h,-1,sizeof h); //h[a] 中初始化为 "-1"(代表链表尾巴)

加边法

void add(int a,int b,int c)
{
    e[++idx] = b,ne[idx] = h[a],h[a] = idx,w[idx] = c;
}

加边翻译：

    1. h[a] 中初始化为 "-1"(代表链表尾巴)
    2. 加 a->b (a指向b)的边时，可以先将b存储到e[inx]中,
    :idx为内部编排的号码(对使用者隐藏,可以忽略)
    3. ne[idx]为该 链表(存储a的下一个点的链表) 下一个点的内部排列序号idx的值 ，而使用e[ne[idx]]则是该点的序号
    4. w[idx] 为其权重

遍历点a下一个点(a所直接指向的点)

    for(int j = h[t]; ~j; j = ne[j]) //~为取反运算符，当j为-1是，~j为0
    {
        int p = e[j]; //p就是t的下一个点
    }