7,129
个编辑
更改
跳到导航
跳到搜索
第57行：
第57行： − +
→数据结构
注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V 2边(允许循环)，我们可以让''d ''= |E|/|V|2表示该图的密度。然后，当|E|/|V|2 > 1/64时，8|E| > |V|2/8 ,即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V <sup>2</sup>边(允许循环)，我们可以让'' d ''= |E|/|V|2表示该图的密度。然后，当|E|/|V|2 > 1/64时，8|E| > |V|2/8 ,即当d = |E|/|V|2 ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。