(邻接矩阵只适用于没有重边(或重边可以忽略)的情况,一般情况下不用考虑)
- 邻接矩阵
- 空间复杂度高:为O(n^2)
- 查询一条边的存在情况快: O(1)
- 遍历一个点的所有出边 :O(n)
- 遍历整个图 :O(n^2)
- 邻接表
邻接表基本可以应对所有情况(除了要快速查询一条边要用邻接矩阵)
- 空间复杂度低 :为O(m) m为边数
- 查询某条边 : O(d (u))即这个点的边数 ,如果边有排序,则通过二分就是O(log d (u)) log边数的事件。
- 遍历一个点的所有出边 :O(d (u))即该点的边数
- 遍历整个图 :O(n m) 事件为点的个数加边数。
总结:快速查询时用邻接矩阵,其余情况用邻接表。
如果觉得有帮助的话,可以收藏,点赞支持一下哦!