知识卡片
邻接表与矩阵权衡稀疏性
邻接表按顶点保存出边,空间 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)。 查询 我们可能会做如下的查询:图是否为有向图,寻找给定顶点的出边,查询是否某条边存