链式前向星

发现一个对链式前向星讲解特别好的视频，在这里分享给大家。

代码

// 稠密图用邻接矩阵来存储
// 稀疏图（用邻接表（链式前向星）来存储）
int N, M;
int[] h = new int[N];   // h : head
int[] w = new int[M];   // w : weight
int[] e = new int[M];   // e : end
int[] ne = new int[M];  // ne : next
int idx = 0;    // idx表示当前空节点地址
// 点的编号1～N-1。N可以自定义
// M表示边。M也可以自定义

// 初始化（所有点都是孤立点，相邻节点为空。这里用-1标识空）
void init()
{
    memset(h, -1, sizeof h);
}

// 加边函数（h[u]]头插法插入v）
void add(int u, int v, int w) { // u -> v 权重 w
    e[idx] = v; w[idx] = w; ne[idx] = h[u]; h[u] = idx;
    idx++;
}

// 查看某个点u连向的所有边
for (int i = h[u]; i != -1; i = ne[i]) {
    v = e[i];       // u -> v
    w = w[i];       // u -> v 的权重是 w
    // i为当前节点的地址（i其实就是遍历之前的idx）
}

图的邻接表存储（链式前向星）