知识卡片

普通读书笔记卡 · 3648.a.1

无向边在邻接表记两次

理解等级:中级
  • 有向图的邻接表长度总和等于边数 E;
  • 无向图每条边要在两个端点表中各出现一次,长度总和为 2E。

两者存储量仍是 Θ(V+E),遍历所有边还要检查 V 个表。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第20章 基本图算法 · 查看原书依据

      If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|, since an edge of the form (u, v) is represented by having v appear in Adj[u]. If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2 |E|, since if (u, v) is an undirected edge, then u appears in v’s adjacency list and vice versa.

    参考来源

    - 位置:《算法导论(第4版)》第20章《基本图算法》(OEBPS/chapter020.xhtml,文本字符[0,5000))。 - 结论依据:原文分别计算有向和无向边在邻接表中的出现次数与空间界。 - 原始内容:If G is a directed graph, the sum of the lengths of all the adjacency lists is | E |, since an edge of the form ( u , v ) is represented by having v appear in Adj [ u ]. If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2 | E |, since if ( u , v ) is an undirected edge, then u appears in v ’s adjacency list and vice versa.