知识卡片
稀疏结构按有效关系保存
邻接矩阵为每一对节点保留位置,查询某条边是否存在很直接,但稀疏图中大多数位置没有实际关系。若内存紧张,可选择只保存存在的连接,避免为空关系支付同样空间;代价是某些查询需要搜索相应集合。选择表示要看节点数、边密度及查询方式,不能把矩阵或稀疏表示当作所有图的默认最优方案。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第 4 章 宝贵的内存:空间效率 · 查看原书依据
如果图是稀疏的,大部分矩阵单元就会被闲置,导致内存的浪费。在这种情况下,你可能要考虑使用一种内存效率高但牺牲了时间效率的表示方法。 当今智能手机的内存几乎和一台标准的笔记本计算机一样大,但当Googl
参考来源
- 位置:《你真的会写代码吗-2021》第4章《宝贵的内存:空间效率》(来源项目book-sources:`extracted/你真的会写代码吗-2021/_epub-src/OEBPS/Text/0014.xhtml`)
- 结论依据:原文以“如果图是稀疏的,大部分矩阵单元就会被闲置,导致内存的浪费”所在的机制、例子或限制条件支撑本文;适用边界及读者推导在正文中单独说明。
- 原始内容:如果图是稀疏的,大部分矩阵单元就会被闲置,导致内存的浪费。在这种情况下,你可能要考虑使用一种内存效率高但牺牲了时间效率的表示方法。 当今智能手机的内存几乎和一台标准的笔记本计算机一样大,但当Googl