C++ 中图形问题的邻接表或邻接矩阵哪个更好?

What is better, adjacency lists or adjacency matrices for graph problems in C++?(C++ 中图形问题的邻接表或邻接矩阵哪个更好?)

本文介绍了C++ 中图形问题的邻接表或邻接矩阵哪个更好?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

What is better, adjacency lists or adjacency matrix, for graph problems in C++? What are the advantages and disadvantages of each?

推荐答案

这取决于问题.

邻接矩阵

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

邻接表

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

这篇关于C++ 中图形问题的邻接表或邻接矩阵哪个更好?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!

本文标题为:C++ 中图形问题的邻接表或邻接矩阵哪个更好?

基础教程推荐