gpt4 book ai didi

c++ - 对于 C++ 中的图问题,邻接列表或邻接矩阵哪个更好?

转载 作者:IT老高 更新时间:2023-10-28 11:53:13 28 4
gpt4 key购买 nike

对于 C++ 中的图问题,邻接列表或邻接矩阵哪个更好?各自的优点和缺点是什么?

最佳答案

这取决于问题。

Adjacency Matrix

  • 使用 O(n^2) 内存
  • 查找和检查特定边是否存在的速度很快
    任意两个节点之间 O(1)
  • 遍历所有边很慢
  • 添加/删除节点慢;复杂运算 O(n^2)
  • 添加一条新边 O(1) 很快

Adjacency List

  • 内存使用更多取决于边数(更少取决于节点数),
    如果邻接矩阵稀疏,这可能会节省大量内存
  • 查找任意两个节点之间是否存在特定边
    比使用矩阵 O(k) 稍慢;其中 k 是邻居节点的数量
  • 迭代所有边的速度很快,因为您可以直接访问任何节点邻居
  • 添加/删除节点速度快;比矩阵表示更容易
  • 添加一条新边 O(1) 速度很快

关于c++ - 对于 C++ 中的图问题,邻接列表或邻接矩阵哪个更好?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2218322/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com