知识卡片

普通读书笔记卡 · 5654.d.1.f.3.j · 生成模型:未记录

邻接表按实际边存储关系

理解等级:中级

邻接表为每个顶点保存其直接邻居集合;有向图按出边保存,每条边贡献一项邻接记录,无向图通常在两端各存一次,因此记录数约为2|E|。02917显示02915中每顶点的出邻居,如1有3和4、2有1、3有2。

这种表示按顶点和实际边保存,通常用O(|V|+|E|)空间,适合边较少的图。邻接矩阵为每对顶点预留一格,空间O(|V|²),原文O(VE)错误;并非一定要边稠密才可用矩阵,选择还要看邻接查询与遍历需求。

图示的链表顺序只是表示层的枚举次序,不自动让数学图的顶点或边有序。具体C类型和销毁归属留后续实际头文件。

202矩阵为每对顶点[u,v]保存邻接标记,空间O(V²),呼应186修正。稠密图的边数接近平方量级而非正文所写顶点数开平方;接口可重新实现,但借用邻接Set等具体返回形式是否仍适用需设计,不能仅换内部数组就保持所有细节。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      所有邻接表中的顶点总数同总的边数相等。在无向图中,由于边(u,v)暗含了边(v,u),因此顶点v包含在顶点u的邻接表中,而顶点u也包含在顶点v的邻接表中。因而,在这种情况下所有邻接表中的顶点总数是总边数的两倍。 通常,邻接表多用于稀疏图中,稀疏图是指边数相对来说较少的图。稀疏图非常普遍,但是如果图是

    • · 查看原书依据

      V×V阶矩阵组成,这里V代表图中的顶点个数。如果顶点u和v之间存在一条边,就在矩阵的[u,v]处设置一个标志。邻接矩阵表示法通常用于稠密图中,此时边的数量与顶点总数开平方后的值相接近。尽管本章中给出的接口都是基于邻接表表示方式的,我们也可以将其修改为支持邻接矩阵表示方式,同时仍然隐藏具体的实现细节。

    参考来源

    - 位置:《算法精解:C语言描述》第11章《图的描述》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u186-ch11-011)。 - 结论依据:186完整邻接表/稀疏稠密说明和02917六个邻接链实读;矩阵平方由每顶点一行一列直接推导,不重复原文错误。 - 原始内容:所有邻接表中的顶点总数同总的边数相等。在无向图中,由于边(u,v)暗含了边(v,u),因此顶点v包含在顶点u的邻接表中,而顶点u也包含在顶点v的邻接表中。因而,在这种情况下所有邻接表中的顶点总数是总边数的两倍。 通常,邻接表多用于稀疏图中,稀疏图是指边数相对来说较少的图。稀疏图非常普遍,但是如果图是 - 位置:《算法精解:C语言描述》第11章《相关主题》(spine1335;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1302.html;u202-ch11-011)。 - 结论依据:202矩阵为每对顶点[u,v]保存邻接标记,空间O(V²),呼应186修正。稠密图的边数接近平方量级而非正文所写顶点数开平方;接口可重新实现,但借用邻接Set等具体返回形式是否仍适用需设计,不能仅换内部数组就保持所有细节。 - 原始内容:V×V阶矩阵组成,这里V代表图中的顶点个数。如果顶点u和v之间存在一条边,就在矩阵的[u,v]处设置一个标志。邻接矩阵表示法通常用于稠密图中,此时边的数量与顶点总数开平方后的值相接近。尽管本章中给出的接口都是基于邻接表表示方式的,我们也可以将其修改为支持邻接矩阵表示方式,同时仍然隐藏具体的实现细节。