图的邻接表存储(链式前向星)

链式前向星

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

图的邻接表存储(链式前向星)

代码

// 稠密图用邻接矩阵来存储
// 稀疏图(用邻接表(链式前向星)来存储)
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)
}
上一篇:826. 单链表


下一篇:数组模拟链表