使用邻接列表和邻接矩阵的图的大小？

Question

假设有2个网页，并且平均每个网页具有2个超链接。考虑如果在顶点所代表的网页之间存在超链接，那么每个网页具有一个顶点和两个顶点之间的边的有向图。使用邻接矩阵表示图表需要多少太字节？使用邻接列表？我的问题是列表和矩阵之间的主要区别是什么？

Answer 1

要回答你的问题，“矩阵的列表表示和矩阵表示之间的主要区别是什么？”

A 列表表示通常是一个元组列表，其中列表的每个元素是一个节点，元组是连接到它的节点。说，我们有3个节点A，B，C，所以我们将具有长度3的列表说存在从A一个节点 - >B，然后在第A位置元件，比方说第一个元素，将包含节点B 。假设还有一个从A - >C的链接，第一个元素将包含B和C。邻接列表所需的总空间是（表示节点的空间）*（边的数量）。

另一方面，矩阵表示是一个矩阵，通常实现为一个二维数组，其中每个节点都列在行和列轴上。如果在2个节点之间存在链接，则在矩阵中标记该点。例如，如果我们有3个节点A，B,C，我们有一个3x3阵列array。让我们把A =指数0，B =指数1，C =指数2，并假设我们有一个链接从A - >B，然后在1在array[0][1]填写。如果我们的图表没有定向，我们还会在array[1][0]处添加一个1。所需的总空间是每个链接所需空间N^2倍的节点数（可以用1位，0或1来完成），因此总数= N^2。

一个列表很适合稀疏图，因为它不需要任何额外的存储空间。也就是说，不存在的链接不代表任何事物。相比之下，如果我们的图表非常密集，则表示更好，因为每个可能的链接仅由1位（0或1）表示。从上面的示例中可以看出，列表表示所需的总空间是的边数的函数，而矩阵表示的空间是节点数的函数。

现在想想你的具体问题。你会有多少个节点？总边缘？这看起来稀疏或密集？