使用邻接列表和邻接矩阵的图的大小？ [英] Size of a graph using adjacency list versus adjacency matrix?

问题描述

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

解决方案

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

列表表示通常是一个元组列表，列表中的每个元素都是一个节点，元组是连接到它的节点。假设我们有3个节点 A ， B ， C ，所以我们将有一个长度为3的列表。假设有一个来自 A - > B 的节点，则元素in A th位置，比如第一个元素，将包含节点 B 。假设还有一个从 A - > C 的链接，第一个元素将包含 B 和 C 。相邻列表所需的总空间是（表示节点的空间）*（边的数量）。另一方面，矩阵表示 / strong>是一个矩阵，通常以2-d数组的形式实现，其中每个节点都列在行和列轴上。如果在2个节点之间存在链接，则在矩阵中标记该点。例如，如果我们有3个节点 A ， B ， C ，我们有一个3x3的数组 array 。让我们调用 A = index 0 ， B = index 1 ， C = index 2 ，假设我们有从 A - > B 链接，然后填写 1 at array [0] [1] 。如果我们的图是无向的，我们还会在 array [1] [0] 处添加一个 1 。所需的总空间是每个链接所需空间的N ^ 2倍（可以用1位完成， 0 或 1 ），所以total = N ^ 2。

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

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

Suppose there are 2³⁶ web pages and on average each web page has 2⁴ hyperlinks. Consider the directed graph with one vertex per web page and an edge between two vertices if there is a hyperlink between the web pages the vertices represent. How many terabytes would it take to represent the graph using an adjacency matrix? Using an adjacency list? My question is what would be the main difference between the list and the matrix?

解决方案

To answer your question, "What is the main difference between a list representation and matrix representation of a matrix?"

A list representation of a graph is usually a list of tuples, where each element of the list is a node, and the tuples are the nodes connected to it. Say we have 3 nodes A, B, C, so we will have a list of length 3. Say there is a node from A->B, then element in the Ath position, say the first element, will contain the node B. Say there is also a link from A->C, the first element will contain B and C. The total space required for an adjacency list is (space to represent a node) * (number of edges).

On the other hand, a matrix representation is a matrix, usually implemented as a 2-d array, where every node is listed on both the row and column axis. If there is a link between 2 nodes, then mark that spot in the matrix. For example, if we have 3 nodes A, B, C, we have a 3x3 array array. Let's call A=index 0, B=index 1, C=index 2, and suppose we have a link from A -> B, then fill in a 1 at array[0][1]. If our graph was undirected, we'd also add a 1 to the spot at array[1][0]. Total space required is the number of nodes N^2 times the space required by each link (can be done with 1 bit, 0 or 1), so total = N^2.

A list is good for sparse graphs because it doesn't require any extra storage. That is, links that don't exist aren't represented by anything. By contrast, if our graph is very dense, then a matrix representation is better because every possible link is denoted by only 1 bit (0 or 1). As you can see from the examples above, the total space required by a list representation is a function of the number of edges, while the space for a matrix representation is a function of the number of nodes.

Now think about your specific problem. How many total nodes would you have? Total edges? Does that seem sparse or dense?

这篇关于使用邻接列表和邻接矩阵的图的大小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！