存储图形的三种方式，优点和缺点 [英] Three ways to store a graph in memory, advantages and disadvantages

问题描述

有三种方法可以将图存储在内存中：

1. 节点作为对象和边作为指针


2. 包含编号节点x和节点y之间的所有边权重的矩阵
   
3. 编号节点之间的边的列表

我知道如何写出所有这三种，但我不确定我是否想过每种方法的优点和缺点。

在存储器中存储图形的每种方法有哪些优缺点？解析方案

解析方法

在内存和时间复杂性方面（这取决于你如何访问图）。

将节点存储为指向彼此的对象

• 这种方法是O（n），因为您拥有的节点数量与您拥有的节点数量一样多。由于每个节点对象可能包含多达n个节点的指针，所以指向（节点）指针的数量最多为O（n ^ 2）。


• 这个数据结构的时间复杂度是O（n），用于访问任何给定的节点。
  
  
  <存储一个边权重矩阵
  
  
  
  
  • 这个矩阵的内存复杂度为O（n ^ 2）。
  >
  
  • 这个数据结构的优点是访问任何给定节点的时间复杂度是O（1）。
    
    
    

    根据您在图上运行的算法以及有多少个节点，您必须选择合适的表示。
    

    There are three ways to store a graph in memory:

    1. Nodes as objects and edges as pointers
    2. A matrix containing all edge weights between numbered node x and node y
    3. A list of edges between numbered nodes

    I know how to write all three, but I'm not sure I've thought of all of the advantages and disadvantages of each.

    What are the advantages and disadvantages of each of these ways of storing a graph in memory?

    解决方案

    One way to analyze these is in terms of memory and time complexity (which depends on how you want to access the graph).

    Storing nodes as objects with pointers to one another

    • The memory complexity for this approach is O(n) because you have as many objects as you have nodes. The number of pointers (to nodes) required is up to O(n^2) as each node object may contain pointers for up to n nodes.
    • The time complexity for this data structure is O(n) for accessing any given node.

    Storing a matrix of edge weights

    • This would be a memory complexity of O(n^2) for the matrix.
    • The advantage with this data structure is that the time complexity to access any given node is O(1).

    Depending on what algorithm you run on the graph and how many nodes there are, you'll have to choose a suitable representation.

    这篇关于存储图形的三种方式，优点和缺点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！