对于C++中的图问题，邻接表和邻接矩阵哪个更好？
对于C++中的图问题，邻接表和邻接矩阵哪个更好？
提问于 2010-02-08 04:59:03
对于C++中的图问题，邻接表和邻接矩阵哪个更好？每种方法的优缺点是什么？
回答 4
Stack Overflow用户
发布于 2015-07-18 15:51:10
好的，我已经编辑了图上基本运算的时间和空间复杂度。
下面的图片应该是不言自明的。
请注意，当我们期望图是密集的时，邻接矩阵是如何可取的；当我们期望图是稀疏的时，邻接列表是如何可取的。
我做了一些假设。问我一个复杂性(时间或空间)是否需要澄清。(例如，对于稀疏图，我将En设为一个小常量，因为我假设添加一个新顶点只会添加几条边，因为我们希望即使添加了该顶点，该图也会保持稀疏。)
如果有什么错误，请告诉我。
Stack Overflow用户
发布于 2016-11-25 19:04:42
这个问题最好用例子来回答。
以Floyd-Warshall为例。我们必须使用邻接矩阵，否则算法将渐近变慢。
或者，如果它是一个有30,000个顶点的密集图呢？那么邻接矩阵可能是有意义的，因为您将每对顶点存储1位，而不是每条边存储16位(邻接列表所需的最小位)：即107MB，而不是1.7 GB。
但对于DFS、BFS (以及那些使用它的算法，如Edmonds-Karp)、优先级优先搜索(Dijkstra，Prim，A*)等算法，邻接表就像矩阵一样好。嗯，当图是密集的时，矩阵可能会有轻微的边缘，但只有一个不起眼的恒定因子。(多少钱？这是一个实验的问题。)
Stack Overflow用户
发布于 2014-05-08 16:36:03
根据邻接矩阵的实现，图的'n‘应该更早知道，以便更有效地实现。如果图表过于动态，需要时不时地扩展矩阵，这也可以算作不利因素？
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2218322
复制相关文章
相似问题
腾讯云开发者
