对于C++中的图形问题,什么是更好的,邻接列表或邻接矩阵？

Question

对于C++中的图形问题,什么是更好的,邻接列表或邻接矩阵？各有哪些优缺点？

Answer 1

这取决于问题.

邻接矩阵

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

邻接清单

• 使用内存挂起的边数(不是节点数),
  如果邻接矩阵是稀疏的,可能会节省大量内存
• 找到任意两个节点之间存在或不存在的特定边缘
  比使用k个邻居节点的矩阵O(k)稍慢
• 遍历所有边缘的速度很快
  因为您可以直接访问任何节点邻居
• 添加/删除节点比使用矩阵表示更容易
• 快速添加新边O(1)

Answer 2

这个答案不仅适用于C++,因为所提到的一切都是关于数据结构本身,无论语言如何.而且,我的答案是假设你知道邻接列表和矩阵的基本结构.

记忆

如果内存是您主要关注的问题,您可以按照此公式获得允许循环的简单图表:

邻接矩阵占据Ñ ² /8个字节的空间(每个条目的一个比特).

邻接列表占用8e空间,其中e是边数(32位计算机).

如果我们将图的密度定义为d = e/n ² (边数除以最大边数),我们可以找到"断点",其中列表占用的内存多于矩阵:

图8e>Ñ ² /8 当 D> 1/64

因此,使用这些数字(仍然是32位特定的),断点落在1/64处.如果密度(e/n ²)大于1/64,则如果要节省内存,则最好使用矩阵.

您可以在维基百科(关于邻接矩阵的文章)和许多其他网站上阅读此内容.

旁注:可以通过使用哈希表来提高邻接矩阵的空间效率,其中键是顶点对(仅仅是无向的).

迭代和查找

邻接列表是仅表示现有边缘的紧凑方式.然而,这是以可能缓慢查找特定边缘为代价的.由于每个列表与顶点的程度一样长,因此检查特定边的最坏情况查找时间可以变为O(n),如果列表是无序的.然而,查找顶点的邻居变得微不足道,对于稀疏或小图,迭代邻接列表的成本可能可以忽略不计.

另一方面,邻接矩阵使用更多空间以提供恒定的查找时间.由于存在每个可能的条目,因此您可以使用索引在恒定时间内检查是否存在边.但是,邻居查找需要O(n),因为您需要检查所有可能的邻居.显而易见的空间缺点是,对于稀疏图形,添加了大量填充.有关详细信息,请参阅上面的内存讨论.

如果您仍然不确定要使用什么:大多数现实问题都会产生稀疏和/或大图,这些图更适合于邻接列表表示.它们似乎更难实现,但我向你保证它们不是,当你编写BFS或DFS并想要获取节点的所有邻居时,它们只是一行代码.但请注意,我并不是在推广邻接列表.

Answer 3

好的,我已经在图表上编译了基本操作的时间和空间复杂性.
下图应该是不言自明的.
注意当我们期望图形密集时,邻接矩阵是如何优选的,以及当我们期望图形稀疏时,邻接列表如何更可取.
我做了一些假设.问我复杂性(时间或空间)是否需要澄清.(例如,对于稀疏图,我将En作为一个小常数,因为我假设添加一个新顶点只会添加一些边,因为我们希望图形在添加之后仍保持稀疏顶点.)

请告诉我是否有任何错误.

Answer 4

这取决于你在寻找什么.

使用邻接矩阵,您可以快速回答有关两个顶点之间的特定边是否属于图的问题,还可以快速插入和删除边.的缺点是,你必须使用过多的空间,尤其是对于有许多顶点,这是非常低效的,特别是如果你的图是稀疏图.

另一方面,对于邻接列表,更难以检查给定边是否在图中,因为您必须搜索适当的列表以找到边,但它们更节省空间.

通常,邻接列表是大多数图形应用程序的正确数据结构.

Answer 5

如果您正在查看C++中的图形分析,可能首先要做的是boost图库,它实现了许多算法,包括BFS.

• 提升图库文档

编辑

关于SO的上一个问题可能会有所帮助:

如何创建-ac-boost-undirected-graph-and-traverse-it-in-depth-first-searc h

Answer 6

让我们假设我们有一个图表,其中有n个节点和m个边,

示例图

邻接矩阵: 我们正在创建一个具有n个行和列的矩阵,因此在内存中它将占用与n ²成比例的空间.检查名为u和v的两个节点是否在它们之间有边缘将花费Θ(1)时间.例如,检查(1,2)是代码中的边缘如下所示:

if(matrix[1][2] == 1)

如果你想识别所有边,你必须迭代矩阵,这将需要两个嵌套循环,它将采用Θ(n ²).(您可以只使用矩阵的上三角形部分来确定所有边,但它将再次为Θ(n ²))

邻接列表: 我们正在创建一个列表,每个节点也指向另一个列表.您的列表将包含n个元素,每个元素将指向一个列表,该列表的项目数等于此节点的邻居数(为了更好的可视化,请查看图像).因此,它将占用内存中与n + m成比例的空间.检查(u,v)是否为边将花费O(deg(u))时间,其中deg(u)等于u的邻居数.因为最多,你必须遍历u指向的列表.识别所有边缘将采用Θ(n + m).

示例图的邻接列表

您应该根据自己的需要做出选择. 由于我的声誉,我不能把矩阵的图像,抱歉

Answer 7

最好通过示例回答这个问题.

以Floyd-Warshall为例.我们必须使用邻接矩阵,否则算法会渐近变慢.

或者如果它是30,000个顶点上的密集图形怎么办？然后一个邻接矩阵可能有意义,因为你将每对顶点存储1位,而不是每边缘16位(你的邻接列表需要的最小值):那是107 MB,而不是1.7 GB.

但对于像DFS,BFS(以及使用它的那些,如Edmonds-Karp),优先级优先搜索(Dijkstra,Prim,A*)等算法,邻接列表与矩阵一样好.好吧,当图表密集时,矩阵可能会略有边缘,但只有不显着的常数因子.(多少钱？这是试验的问题.)