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

问题描述

在内存中存储图形的三种方式:

There are three ways to store a graph in memory:

1. 节点作为对象，边作为指针
2. 包含编号节点 x 和节点 y 之间所有边权重的矩阵
3. 编号节点之间的边列表

我知道如何写出所有三个，但我不确定我是否考虑过每个的优点和缺点.

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

• 此方法的内存复杂度为 O(n)，因为您拥有的对象与节点的数量一样多.所需的(指向节点的)指针数量最多为 O(n^2)，因为每个节点对象可能包含最多 n 个节点的指针.
• 对于访问任何给定节点，此数据结构的时间复杂度为 O(n).

存储边权重矩阵

• 对于矩阵，这将是 O(n^2) 的内存复杂度.
• 这种数据结构的优点是访问任何给定节点的时间复杂度为 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屋！