侧边栏壁纸
  • 累计撰写 43 篇文章
  • 累计创建 0 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

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

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

链式前向星.jpeg

代码

// 稠密图用邻接矩阵来存储
// 稀疏图(用邻接表(链式前向星)来存储)
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 x) { // u -> v 权重 x
    e[idx] = v; w[idx] = x; ne[idx] = h[u]; h[u] = idx;
    idx++;
}

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

勘误:将上图中int w改为int x,对应处随之修改即可。因为int wint[] w命名冲突了!

0

评论区