知识卡片
无向边在邻接表记两次
- 有向图的邻接表长度总和等于边数 E;
- 无向图每条边要在两个端点表中各出现一次,长度总和为 2E。
两者存储量仍是 Θ(V+E),遍历所有边还要检查 V 个表。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.