知识卡片

普通读书笔记卡 · 5654.d.1.f.2

矩阵与邻接表保留不同信息

理解等级:中级

邻接矩阵为每对顶点保留槽位,已知顶点索引时可以直接判断或更新边,但空间为顶点数平方。邻接表只存实际邻居,稀疏图更省空间,判断某边则可能要搜索邻居集合。

无向边要维护对称关系;有权图若用0表示无边,就不能同时无歧义表示零权边,需要独立标记。矩阵常数边访问不包含按值查顶点索引或增删整行整列的成本。

矩阵addVertex给每行append可能触发整行重新分配,因此教学“只加一行一列”的线性槽数不保证每次实际最坏仅线性;仍要计搬移。邻接表用map[Vertex][]Vertex,键的相等取决于Go类型实际定义,不能只因名为实例就保证不同对象唯一身份。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      邻接表仅存储实际存在的边,而边的总数通常远小于 ,因此它更加节省空间。然而,在邻接表中需要通 过遍历链表来查找边,因此其时间效率不如邻接矩阵。 观察图9‑6 ,邻接表结构与哈希表中的“链式地址”非常相似,因此我们也可以采

    • · 查看原书依据

      使用哈希表来存储邻接表,key 为顶点实例,value 为该顶点的邻接顶点列表(链表) 。 另外,我们在邻接表中使用Vertex 类来表示顶点,这样做的原因是:如果与邻接矩阵一样,用列表索引来区 分不同顶点,那么假设要删

    参考来源

    - 位置:《Hello 算法--Go版本》第09章《图》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[25656,25766)) - 结论依据:实际两类表示与空间/查询比较,限定零边权和操作范围。 - 原始内容:邻接表仅存储实际存在的边,而边的总数通常远小于 ,因此它更加节省空间。然而,在邻接表中需要通 过遍历链表来查找边,因此其时间效率不如邻接矩阵。 观察图9‑6 ,邻接表结构与哈希表中的“链式地址”非常相似,因此我们也可以采 补充原书证据:spine 4 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;归一字符[2531,2641)。 - 结论依据:实际两种实现补充增长成本与顶点键身份。 - 原始内容:使用哈希表来存储邻接表,key 为顶点实例,value 为该顶点的邻接顶点列表(链表) 。 另外,我们在邻接表中使用Vertex 类来表示顶点,这样做的原因是:如果与邻接矩阵一样,用列表索引来区 分不同顶点,那么假设要删