C++ 中图形问题的邻接表或邻接矩阵哪个更好? [英] What is better, adjacency lists or adjacency matrices for graph problems in 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++ 中图形问题的邻接表或邻接矩阵哪个更好?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！