若用矩阵压缩算法是否可以降低无向图的复杂度到邻接表的级别？

来源：2-3 图的基本表示：邻接矩阵

yushou

2020-01-11

使用矩阵压缩算法在无向图中是不是可以把邻接矩阵算法的复杂度降低到比TreeSet更好的级别呢？
空间复杂度貌似只需要O(v*(v+1)/2)，而查找两点相邻和查找邻边只需要O(1)的时间复杂度即可。似乎是个更好的算法。

写回答

1回答

liuyubobobo

2020-01-11

已采纳

单纯查找，使用 HashSet 也是 O(1) 级别。关键是图的遍历的复杂度。使用邻接表，图的遍历是 O(V + E) 级别的。而图的遍历，才是在图论中，近乎每一个图论算法都需要的操作。

继续加油！：）

yushou

非常感谢！

2020-01-11

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

相似问题

回答 1

回答 1

回答 1

回答 2

回答 1