什么更好，邻接列表或邻接矩阵的图形问题在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 * n）存储器。它具有快速查找以检查特定边缘的存在或不存在，但缓慢地遍历所有边缘。

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.

邻接列表使用内存与数字边缘成比例，如果邻接矩阵是稀疏的，可以节省大量的内存。它是快速迭代所有的边缘，但发现存在或不存在特定边缘比矩阵稍慢。

Adjacency lists use memory in proportion to the number edges, which might save a lot of memory if the adjacency matrix is sparse. It is fast to iterate over all edges, but finding the presence or absence specific edge is slightly slower than with the matrix.

这篇关于什么更好，邻接列表或邻接矩阵的图形问题在c ++？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！