知识卡片

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

邻接表与矩阵权衡稀疏性

理解等级:中级

邻接表按顶点保存出边,空间 O(V+E),遍历一个顶点的邻边与其度数相关;邻接矩阵占 O(V²) 空间,可在 O(1) 时间检查指定位置,但遍历所有候选邻点需 O(V)。无向图的邻接表通常保存两个方向,矩阵则对称。

若用0表示无边,就不能同时不加区分地表示权重为0的边;需要单独存在标记或不同哨兵。带方向的关系、重复边与权重范围也须明确。

145指出矩阵无论有多少边都需要 V² 个位置,邻接表可节省稀疏图空间。邻接项排序或压缩为连续范围可能加速某些存在性查询并减少存储,但插入删除更复杂;具体成本依数据结构而定。航班频次不等同于不同机场对数,不能据此严格计算矩阵稀疏度。

147图03281的接口包括建图、加载、查询边与权重、迭代邻接点、增加和删除边。无向图若以双向邻接项表示,更新时必须同时维护两侧;顶点范围、重复边和删除不存在边的行为需约定。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      邻接矩阵来存储有向有权图,每个维度可以被索引。条目A[i][j]存储的是从vi到vj的边的权值;当A[i][j]=0时,顶点vi和顶点vj之间不存在边。使用邻接矩阵表示法,添加一条边只需要常数时间。 图 6-4 有向有权图的邻接矩阵表示 我们也可以使用邻接表和邻接矩阵来存储无向图。看看图6-5的无向

    • · 查看原书依据

      稀疏图,由于计算机内存的限制,不可能存储超过数千个顶点的图。例如,Java虚拟机堆使用默认值256MB,创建一个二维的int[4096][4096]矩阵就已经超出可用内存。即使程序员能够在一台有着更多内存的计算机上执行程序,事实上创建的矩阵规模存在一个固定的上界。另外,在大规模矩阵中存储稀疏图,遍历

    • · 查看原书依据

      关键图操作 图6-6的操作可以分为如下几类: 创建 图是创建自n个顶点的集合,也许有向,也许无向。load(char*)读取文件中的点和边的信息来更新图。如果图是无向的,那么添加边(u,v)的同时添加了边(v,u)。 查询 我们可能会做如下的查询:图是否为有向图,寻找给定顶点的出边,查询是否某条边存

    参考来源

    - 位置:《算法技术手册》第6章《图》(spine1561;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1524.html;u144-ch06-002)。 - 结论依据:144全文及03276–03279有向图、邻接表、矩阵和无向图实读。 - 原始内容:邻接矩阵来存储有向有权图,每个维度可以被索引。条目A[i][j]存储的是从vi到vj的边的权值;当A[i][j]=0时,顶点vi和顶点vj之间不存在边。使用邻接矩阵表示法,添加一条边只需要常数时间。 图 6-4 有向有权图的邻接矩阵表示 我们也可以使用邻接表和邻接矩阵来存储无向图。看看图6-5的无向 - 位置:《算法技术手册》第6章《存储问题》(spine1562;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1525.html;u145-ch06-002)。 - 结论依据:145指出矩阵无论有多少边都需要 V² 个位置,邻接表可节省稀疏图空间。邻接项排序或压缩为连续范围可能加速某些存在性查询并减少存储,但插入删除更复杂;具体成本依数据结构而定。航班频次不等同于不同机场对数,不能据此严格计算矩阵稀疏度。 - 原始内容:稀疏图,由于计算机内存的限制,不可能存储超过数千个顶点的图。例如,Java虚拟机堆使用默认值256MB,创建一个二维的int[4096][4096]矩阵就已经超出可用内存。即使程序员能够在一台有着更多内存的计算机上执行程序,事实上创建的矩阵规模存在一个固定的上界。另外,在大规模矩阵中存储稀疏图,遍历 - 位置:《算法技术手册》第6章《数据结构设计》(spine1564;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1527.html;u147-ch06-002)。 - 结论依据:147图03281的接口包括建图、加载、查询边与权重、迭代邻接点、增加和删除边。无向图若以双向邻接项表示,更新时必须同时维护两侧;顶点范围、重复边和删除不存在边的行为需约定。 - 原始内容:关键图操作 图6-6的操作可以分为如下几类: 创建 图是创建自n个顶点的集合,也许有向,也许无向。load(char*)读取文件中的点和边的信息来更新图。如果图是无向的,那么添加边(u,v)的同时添加了边(v,u)。 查询 我们可能会做如下的查询:图是否为有向图,寻找给定顶点的出边,查询是否某条边存