对于C中的图形问题，什么是更好的，邻接列表或邻接矩阵？各有哪些优缺点？
这取决于问题 .
邻接矩阵使用O（n * n）存储器 . 它具有快速查找以检查特定边缘的存在或不存在，但是在所有边缘上迭代的速度很慢 .
邻接列表使用与数字边缘成比例的内存，如果邻接矩阵是稀疏的，则可能节省大量内存 . 迭代所有边缘的速度很快，但找到特定边缘的存在或不存在比使用矩阵稍慢 .
这个答案不只是针对C，因为所提到的一切都是关于数据结构本身的，无论语言如何 . 而且，我的答案是假设你知道邻接列表和矩阵的基本结构 .
如果内存是您主要关心的问题，您可以按照此公式获得一个允许循环的简单图表：
邻接矩阵占用n2 / 8字节空间（每个条目一位） .
邻接列表占用8e空间，其中e是边数（32位计算机） .
如果我们将图的密度定义为d = e / n2（边数除以最大边数），我们可以找到"breakpoint"，其中列表占用的内存多于矩阵：
8e > n2/8 何时 d > 1/64
因此，对于这些数字（仍然是32位特定的），断点落在 1/64 . 如果密度（e / n2）大于1/64，则如果要节省内存，则最好使用矩阵 .
您可以在wikipedia（关于邻接矩阵的文章）和许多其他网站上阅读此内容 .
Side note ：可以通过使用哈希表来提高邻接矩阵的空间效率，其中密钥是顶点对（仅限于无向） .
邻接列表是仅表示现有边缘的紧凑方式 . 然而，这是以可能缓慢查找特定边缘为代价的 . 由于每个列表与顶点的程度一样长，因此检查特定边的最坏情况查找时间可以变为O（n），如果列表是无序的 . 然而，查找顶点的邻居变得微不足道，对于稀疏或小图，迭代邻接列表的成本可能可以忽略不计 .
另一方面，邻接矩阵使用更多空间以提供恒定的查找时间 . 由于存在每个可能的条目，因此您可以使用索引在恒定时间内检查是否存在边 . 但是，邻居查找需要O（n），因为您需要检查所有可能的邻居 . 明显的空间缺点是，对于稀疏图形，添加了大量填充 . 有关详细信息，请参阅上面的内存讨论 .
If you're still unsure what to use ：大多数现实世界的问题产生稀疏和/或大图，它们更适合于邻接列表表示 . 它们可能看起来更难实现，但我向你们保证，它们不仅仅是一行代码 . 但请注意，我并不是在推广邻接列表 .
好的，我已经在图表上编译了基本操作的时间和空间复杂性 .下面的图片应该是不言自明的 .注意当我们期望图形密集时，邻接矩阵是如何优选的，以及当我们期望图形稀疏时，邻接列表如何更可取 .我认为En是一个小常数，因为我假设添加一个新顶点只会添加几个边，因为我们希望图形在添加该顶点后仍然保持稀疏 . ）
请告诉我是否有任何错误 .
这取决于你在寻找什么 .
使用 adjacency matrices ，您可以快速回答有关两个顶点之间的特定边缘是否属于图形的问题，还可以快速插入和删除边缘 . 缺点是你必须使用过多的空间，特别是对于有很多顶点的图形，这是非常低效的，特别是如果你的图形很稀疏 .
另一方面，使用 adjacency lists 更难检查给定边是否在图中，因为您必须搜索相应的列表以找到边，但它们更节省空间 .
通常，邻接列表是大多数图形应用程序的正确数据结构 .
如果您正在查看C中的图形分析，可能首先要启动的是boost graph library，它实现了许多算法，包括BFS .
EDIT
关于SO的上一个问题可能会有所帮助：
how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-searc h
最好通过示例回答这个问题 .
以Floyd-Warshall为例 . 我们必须使用邻接矩阵，否则算法会渐近变慢 .
或者如果它是30,000个顶点上的密集图形怎么办？然后一个邻接矩阵可能有意义，因为你将每对顶点存储1位，而不是每边缘16位（你的邻接列表需要的最小值）：那是107 MB，而不是1.7 GB .
但对于像DFS，BFS（以及使用它的那些，如Edmonds-Karp），优先级优先搜索（Dijkstra，Prim，A *）等算法，邻接列表与矩阵一样好 . 好吧，当图形密集时，矩阵可能会有轻微的边缘，但只有不显着的常数因子 . （多少钱？这是试验的问题 . ）
让我们假设我们有一个图表，它有n个节点和m个边，
Example graph
Adjacency Matrix: 我们正在创建一个具有n个行和列的矩阵，因此在内存中它将占用与n2成比例的空间 . 检查名为u和v的两个节点是否在它们之间有边缘将花费Θ（1）时间 . 例如，检查（1,2）是代码中的边缘如下所示：
if(matrix[1][2] == 1)
如果你想识别所有边，你必须迭代矩阵，这将需要两个嵌套循环，它将采用Θ（n2） . （您可以只使用矩阵的上三角部分来确定所有边，但它将再次为Θ（n2））
Adjacency List: 我们正在创建一个列表，每个节点也指向另一个列表 . 您的列表将包含n个元素，每个元素将指向一个列表，该列表的项目数等于此节点的邻居数（为了更好的可视化，请查看图像） . 因此，它将占用内存中与n m成比例的空间 . 检查（u，v）是否为边缘将花费O（deg（u））时间，其中deg（u）等于u的邻居数 . 因为最多，你必须遍历u指向的列表 . 识别所有边缘将采用Θ（n m） .
Adjacency list of example graph
您应该根据自己的需要做出选择 . Because of my reputation I couldn't put image of matrix, sorry for that
根据Adjacency Matrix实现，为了有效实现，应该提前知道图的'n' . 如果图形过于动态并且需要时不时地扩展矩阵，这也可以算作下行？
添加到keyser5053的内存使用情况的答案 .
对于任何有向图，邻接矩阵（每边1位）消耗 n^2 * (1) 位存储器 .
n^2 * (1)
对于complete graph，邻接列表（具有64位指针）消耗 n * (n * 64) 位的内存，不包括列表开销 .
n * (n * 64)
对于不完整的图，邻接列表消耗 0 位的内存，不包括列表开销 .
0
对于邻接列表，您可以使用以下公式来确定邻接矩阵最适合内存之前的最大边数（ e ） .
e
edges = n^2 / s 确定最大边数，其中 s 是平台的指针大小 .
edges = n^2 / s
s
如果您的图形是动态更新，则可以使用 n / s 的平均边缘计数（每个节点）来保持此效率 .
n / s
一些例子（64位指针） .
对于有向图，其中 n 为300，使用邻接列表的每个节点的最佳边数为：
n
= 300 / 64 = 4
如果我们将其插入keyser5053的公式 d = e / n^2 （其中 e 是总边数），我们可以看到我们低于断点（ 1 / s ）：
d = e / n^2
1 / s
d = (4 * 300) / (300 * 300) d < 1/64 aka 0.0133 < 0.0156
但是，指针的64位可能过度 . 如果您使用16位整数作为指针偏移，我们可以在断点之前最多容纳18个边 .
= 300 / 16 = 18 d = ((18 * 300) / (300^2)) d < 1/16 aka 0.06 < 0.0625
这些示例中的每一个都忽略了邻接列表本身的开销（对于向量和64位指针， 64*2 ） .
64*2
如果您使用哈希表而不是邻接矩阵或列表，您将获得更好或相同的大O运行时和空间用于所有操作（检查边是 O(1) ，获取所有相邻边是 O(degree) 等） .
O(1)
O(degree)
对于运行时和空间都有一些常数因子开销（哈希表没有链表或数组查找那么快，并且需要相当多的额外空间来减少冲突） .
因为其他答案涵盖了其他方面，所以只是谈谈克服常规邻接列表表示的权衡 .
通过利用Dictionary和HashSet数据结构，可以使用EdgeExists查询在分摊的常量时间中表示邻接列表中的图形 . 我们的想法是将顶点保留在字典中，并且对于每个顶点，我们保留一个散列集，引用它具有边缘的其他顶点 .
在该实现中的一个小的权衡是它将具有空间复杂度O（V 2E）而不是O（V E），如在常规邻接列表中那样，因为边缘在这里被表示两次（因为每个顶点具有其自己的边缘散列集） . 但是AddVertex，AddEdge，RemoveEdge等操作可以使用此实现在摊销时间O（1）中完成，但RemoveVertex除外，它采用O（V）之类的邻接矩阵 . 这意味着除了实现简单性邻接矩阵之外没有任何特定的优势 . 我们可以在稀疏图上节省空间，在这个邻接列表实现中具有几乎相同的性能 .
有关详细信息，请查看下面Github C＃存储库中的实现 . 请注意，对于加权图，它使用嵌套字典而不是字典 - 哈希集组合，以便适应权重值 . 类似地，对于有向图，存在用于进出边缘的单独散列集 .
Advanced-Algorithms
注意：我相信使用延迟删除我们可以进一步优化RemoveVertex操作到O（1）摊销，即使我没有测试过这个想法 . 例如，删除时只需在字典中将顶点标记为已删除，然后在其他操作期间懒惰地清除孤立的边缘 .
11 回答
这取决于问题 .
邻接矩阵使用O（n * n）存储器 . 它具有快速查找以检查特定边缘的存在或不存在，但是在所有边缘上迭代的速度很慢 .
邻接列表使用与数字边缘成比例的内存，如果邻接矩阵是稀疏的，则可能节省大量内存 . 迭代所有边缘的速度很快，但找到特定边缘的存在或不存在比使用矩阵稍慢 .
这个答案不只是针对C，因为所提到的一切都是关于数据结构本身的，无论语言如何 . 而且，我的答案是假设你知道邻接列表和矩阵的基本结构 .
记忆
如果内存是您主要关心的问题，您可以按照此公式获得一个允许循环的简单图表：
邻接矩阵占用n2 / 8字节空间（每个条目一位） .
邻接列表占用8e空间，其中e是边数（32位计算机） .
如果我们将图的密度定义为d = e / n2（边数除以最大边数），我们可以找到"breakpoint"，其中列表占用的内存多于矩阵：
8e > n2/8 何时 d > 1/64
因此，对于这些数字（仍然是32位特定的），断点落在 1/64 . 如果密度（e / n2）大于1/64，则如果要节省内存，则最好使用矩阵 .
您可以在wikipedia（关于邻接矩阵的文章）和许多其他网站上阅读此内容 .
Side note ：可以通过使用哈希表来提高邻接矩阵的空间效率，其中密钥是顶点对（仅限于无向） .
迭代和查找
邻接列表是仅表示现有边缘的紧凑方式 . 然而，这是以可能缓慢查找特定边缘为代价的 . 由于每个列表与顶点的程度一样长，因此检查特定边的最坏情况查找时间可以变为O（n），如果列表是无序的 . 然而，查找顶点的邻居变得微不足道，对于稀疏或小图，迭代邻接列表的成本可能可以忽略不计 .
另一方面，邻接矩阵使用更多空间以提供恒定的查找时间 . 由于存在每个可能的条目，因此您可以使用索引在恒定时间内检查是否存在边 . 但是，邻居查找需要O（n），因为您需要检查所有可能的邻居 . 明显的空间缺点是，对于稀疏图形，添加了大量填充 . 有关详细信息，请参阅上面的内存讨论 .
If you're still unsure what to use ：大多数现实世界的问题产生稀疏和/或大图，它们更适合于邻接列表表示 . 它们可能看起来更难实现，但我向你们保证，它们不仅仅是一行代码 . 但请注意，我并不是在推广邻接列表 .
好的，我已经在图表上编译了基本操作的时间和空间复杂性 .
下面的图片应该是不言自明的 .
注意当我们期望图形密集时，邻接矩阵是如何优选的，以及当我们期望图形稀疏时，邻接列表如何更可取 .
我认为En是一个小常数，因为我假设添加一个新顶点只会添加几个边，因为我们希望图形在添加该顶点后仍然保持稀疏 . ）
请告诉我是否有任何错误 .
这取决于你在寻找什么 .
使用 adjacency matrices ，您可以快速回答有关两个顶点之间的特定边缘是否属于图形的问题，还可以快速插入和删除边缘 . 缺点是你必须使用过多的空间，特别是对于有很多顶点的图形，这是非常低效的，特别是如果你的图形很稀疏 .
另一方面，使用 adjacency lists 更难检查给定边是否在图中，因为您必须搜索相应的列表以找到边，但它们更节省空间 .
通常，邻接列表是大多数图形应用程序的正确数据结构 .
如果您正在查看C中的图形分析，可能首先要启动的是boost graph library，它实现了许多算法，包括BFS .
EDIT
关于SO的上一个问题可能会有所帮助：
how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-searc h
最好通过示例回答这个问题 .
以Floyd-Warshall为例 . 我们必须使用邻接矩阵，否则算法会渐近变慢 .
或者如果它是30,000个顶点上的密集图形怎么办？然后一个邻接矩阵可能有意义，因为你将每对顶点存储1位，而不是每边缘16位（你的邻接列表需要的最小值）：那是107 MB，而不是1.7 GB .
但对于像DFS，BFS（以及使用它的那些，如Edmonds-Karp），优先级优先搜索（Dijkstra，Prim，A *）等算法，邻接列表与矩阵一样好 . 好吧，当图形密集时，矩阵可能会有轻微的边缘，但只有不显着的常数因子 . （多少钱？这是试验的问题 . ）
让我们假设我们有一个图表，它有n个节点和m个边，
Example graph
Adjacency Matrix: 我们正在创建一个具有n个行和列的矩阵，因此在内存中它将占用与n2成比例的空间 . 检查名为u和v的两个节点是否在它们之间有边缘将花费Θ（1）时间 . 例如，检查（1,2）是代码中的边缘如下所示：
如果你想识别所有边，你必须迭代矩阵，这将需要两个嵌套循环，它将采用Θ（n2） . （您可以只使用矩阵的上三角部分来确定所有边，但它将再次为Θ（n2））
Adjacency List: 我们正在创建一个列表，每个节点也指向另一个列表 . 您的列表将包含n个元素，每个元素将指向一个列表，该列表的项目数等于此节点的邻居数（为了更好的可视化，请查看图像） . 因此，它将占用内存中与n m成比例的空间 . 检查（u，v）是否为边缘将花费O（deg（u））时间，其中deg（u）等于u的邻居数 . 因为最多，你必须遍历u指向的列表 . 识别所有边缘将采用Θ（n m） .
Adjacency list of example graph
您应该根据自己的需要做出选择 . Because of my reputation I couldn't put image of matrix, sorry for that
根据Adjacency Matrix实现，为了有效实现，应该提前知道图的'n' . 如果图形过于动态并且需要时不时地扩展矩阵，这也可以算作下行？
添加到keyser5053的内存使用情况的答案 .
对于任何有向图，邻接矩阵（每边1位）消耗
n^2 * (1)位存储器 .对于complete graph，邻接列表（具有64位指针）消耗
n * (n * 64)位的内存，不包括列表开销 .对于不完整的图，邻接列表消耗
0位的内存，不包括列表开销 .对于邻接列表，您可以使用以下公式来确定邻接矩阵最适合内存之前的最大边数（
e） .edges = n^2 / s确定最大边数，其中s是平台的指针大小 .如果您的图形是动态更新，则可以使用
n / s的平均边缘计数（每个节点）来保持此效率 .一些例子（64位指针） .
对于有向图，其中
n为300，使用邻接列表的每个节点的最佳边数为：如果我们将其插入keyser5053的公式
d = e / n^2（其中e是总边数），我们可以看到我们低于断点（1 / s）：但是，指针的64位可能过度 . 如果您使用16位整数作为指针偏移，我们可以在断点之前最多容纳18个边 .
这些示例中的每一个都忽略了邻接列表本身的开销（对于向量和64位指针，
64*2） .如果您使用哈希表而不是邻接矩阵或列表，您将获得更好或相同的大O运行时和空间用于所有操作（检查边是
O(1)，获取所有相邻边是O(degree)等） .对于运行时和空间都有一些常数因子开销（哈希表没有链表或数组查找那么快，并且需要相当多的额外空间来减少冲突） .
因为其他答案涵盖了其他方面，所以只是谈谈克服常规邻接列表表示的权衡 .
通过利用Dictionary和HashSet数据结构，可以使用EdgeExists查询在分摊的常量时间中表示邻接列表中的图形 . 我们的想法是将顶点保留在字典中，并且对于每个顶点，我们保留一个散列集，引用它具有边缘的其他顶点 .
在该实现中的一个小的权衡是它将具有空间复杂度O（V 2E）而不是O（V E），如在常规邻接列表中那样，因为边缘在这里被表示两次（因为每个顶点具有其自己的边缘散列集） . 但是AddVertex，AddEdge，RemoveEdge等操作可以使用此实现在摊销时间O（1）中完成，但RemoveVertex除外，它采用O（V）之类的邻接矩阵 . 这意味着除了实现简单性邻接矩阵之外没有任何特定的优势 . 我们可以在稀疏图上节省空间，在这个邻接列表实现中具有几乎相同的性能 .
有关详细信息，请查看下面Github C＃存储库中的实现 . 请注意，对于加权图，它使用嵌套字典而不是字典 - 哈希集组合，以便适应权重值 . 类似地，对于有向图，存在用于进出边缘的单独散列集 .
Advanced-Algorithms
注意：我相信使用延迟删除我们可以进一步优化RemoveVertex操作到O（1）摊销，即使我没有测试过这个想法 . 例如，删除时只需在字典中将顶点标记为已删除，然后在其他操作期间懒惰地清除孤立的边缘 .