对于 C++ 中的图问题，邻接表和邻接矩阵哪个更好？
各自的优点和缺点是什么？
这取决于问题。
邻接矩阵
- 使用 O(n^2) 内存
- 快速查找和检查特定边缘是否存在
任意两个节点之间 O(1)
- 遍历所有边的速度很慢
- 添加/删除节点速度慢；复杂运算 O(n^2)
- 添加新边的速度很快 O(1)
邻接表
- 内存使用更多地取决于边的数量（而不是节点的数量），
如果邻接矩阵稀疏，这可能会节省大量内存
- 查找任意两个节点之间是否存在特定边
比矩阵 O(k) 稍慢；其中 k 是邻居节点的数量
- 迭代所有边的速度很快，因为您可以直接访问任何节点邻居
- 添加/删除节点速度快；比矩阵表示更容易
- 添加新边的速度很快 O(1)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
