知识卡片

普通读书笔记卡 · 9762.d · 生成模型:DeepSeek-V4.1-Flash

邻接矩阵用空间换查询

理解等级:高级

把友谊对 (i, j) 写成矩阵,A[i][j] 为 1 表示相连、0 表示不相连,得到的还是对称矩阵。好处是查询变成一次索引:A[0][2] == 1 立刻知道 0 和 2 是朋友,找某人的所有朋友只需扫他那一行;而用边列表则可能要搜索每条边。代价是空间:关系稀疏时绝大多数格子是 0,全部存下来非常浪费,节点数一多就难以维护。所以这是典型的空间换时间——稠密图或需要频繁随机查询时矩阵合适,稀疏的大网络用邻接表更实际。书中把二元关系列为矩阵的第三种用途,前两种是数据集与线性映射。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第4章 线性代数 · 查看原书依据

      如果关系很少,这种表示形式就会非常低效,因为必须存储大量的零。但使用矩阵表示可以更快地查找两个节点是否连接——只需在矩阵上查找而不是(可能)搜索每条边:

    参考来源

    - 位置:《数据科学入门(第2版)》第4章 线性代数(源文件:extracted/数据科学入门(第2版)/_epub-src/OEBPS/Text/0008.xhtml) - 结论依据:原文这一段直接给出本卡的核心判断:「如果关系很少,这种表示形式就会非常低效,因为必须存储大量的零……」 - 原始内容:如果关系很少,这种表示形式就会非常低效,因为必须存储大量的零。但使用矩阵表示可以更快地查找两个节点是否连接——只需在矩阵上查找而不是(可能)搜索每条边: