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)