我一直在学习类中的图，我们刚刚讨论了邻接矩阵结构和邻接列表结构 .
我对这个要求我们推荐列表或矩阵结构的问题有点困惑：
该图有10,000个顶点和20,000,000个边，使用尽可能小的空间很重要 . 你会推荐哪种结构？
我的回答是邻接矩阵将占用更少的空间 . 我们得到了邻接列表使用 j + k 空间，邻接矩阵使用 j2 空格，其中j是顶点数，k是图中边的数量 . 我使用了先前的公式，发现矩阵给了我一个较小的数字 .
然而，答案似乎是
通常，在这种情况下，两种结构都能很好地工作 . 关于空间要求，没有明显的赢家 .
有人可以解释为什么这是答案，我在哪里？
1 回答
否则选择邻接列表表示 . 边缘远小于顶点的平方，否则选择邻接矩阵表示 . 如果我的答案不满足你，请查阅书籍 - cormen对算法的介绍