可以通过三种方式在内存中存储图表：
- 节点作为对象，边作为指针
- 包含编号节点 x 和节点 y 之间的所有边权重的矩阵
- 编号节点之间的边列表
我知道如何写这三个，但我不确定我是否考虑过每个的所有优点和缺点。
这些在内存中存储图形的方法各自的优点和缺点是什么？
分析这些的一种方法是根据内存和时间复杂度（这取决于您想要如何访问图形）。
将节点存储为具有彼此指针的对象
- 这种方法的内存复杂度是 O(n)，因为对象的数量与节点的数量一样多。所需的指针（指向节点）的数量最多为 O(n^2)，因为每个节点对象可能包含最多 n 个节点的指针。
- 对于访问任何给定节点，该数据结构的时间复杂度为 O(n)。
存储边权重矩阵
- 矩阵的内存复杂度为 O(n^2)。
- 这种数据结构的优点是访问任何给定节点的时间复杂度是 O(1)。
根据您在图上运行的算法以及有多少个节点，您必须选择合适的表示形式。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
