使用邻接列表与邻接矩阵的图的大小？
假设有 236 个网页，平均每个网页有 24 个超链接。考虑有向图，每个网页有一个顶点，如果顶点表示的网页之间存在超链接，则两个顶点之间有一条边。使用邻接矩阵表示该图需要多少 TB？使用邻接表？我的问题是列表和矩阵之间的主要区别是什么？
Suppose there are 236 web pages and on average each web page has 24 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
回答你的问题，“矩阵的列表表示和矩阵表示之间的主要区别是什么？”
图的列表表示通常是元组列表，其中列表的每个元素都是一个节点，元组是连接到它的节点。假设我们有 3 个节点
A、B、C，因此我们将有一个长度为 3 的列表。假设有一个来自的节点>A->B，则第A位置的元素（即第一个元素）将包含节点B。假设还有一个从A->C的链接，第一个元素将包含B和C。邻接表所需的总空间为（表示节点的空间）*（边数）。另一方面，矩阵表示是一个矩阵，通常实现为二维数组，其中每个节点都列在行轴和列轴上。如果两个节点之间存在链接，则在矩阵中标记该点。例如，如果我们有 3 个节点
A、B、C，我们就有一个 3x3 数组array。我们调用A=index0、B=index1、C=index2，假设我们有一个来自A-> 的链接B，然后在array[0][1]处填写一个1。如果我们的图是无向的，我们还会在array[1][0]处添加一个1。所需的总空间是节点数 N^2 乘以每个链接所需的空间（可以用 1 位、0或1来完成），因此总计 = N^ 2.列表适用于稀疏图表，因为它不需要任何额外的存储空间。也就是说，不存在的链接不由任何东西表示。相比之下，如果我们的图非常密集，那么矩阵表示会更好，因为每个可能的链接仅由 1 位（0 或 1）表示。从上面的示例中可以看出，列表表示所需的总空间是边数的函数，而矩阵表示的空间是边数的函数。节点。
现在考虑一下您的具体问题。您总共有多少个节点？总边数？看起来稀疏还是密集？
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 fromA->B, then element in theAth position, say the first element, will contain the nodeB. Say there is also a link fromA->C, the first element will containBandC. 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 arrayarray. Let's callA=index0,B=index1,C=index2, and suppose we have a link fromA->B, then fill in a1atarray[0][1]. If our graph was undirected, we'd also add a1to the spot atarray[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,0or1), 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?