存储graphics的三种方法，优点和缺点
在内存中存储graphics有三种方法：
- 节点作为对象和边作为指针
- 包含编号节点x和节点y之间的所有边权重的matrix
- 编号节点之间的边缘列表
我知道如何写出所有三个，但我不知道我已经想到了每个的优点和缺点。
在内存中存储graphics的每种方式有哪些优缺点？
分析这些问题的一种方法是根据内存和时间复杂性（这取决于您如何访问图）。
将节点存储为指向彼此的对象
- 这种方法的内存复杂度是O（n），因为您拥有的节点数量尽可能多。 由于每个节点对象可能包含多达n个节点的指针，因此指向（节点）指针的数量最多为O（n ^ 2）。
- 这个数据结构的时间复杂度是O（n）来访问任何给定的节点。
存储边权重matrix
- 这将是matrixO（n ^ 2）的记忆复杂度。
- 这种数据结构的优点是访问任何给定节点的时间复杂度是O（1）。
根据你在图上运行的algorithm和有多less个节点，你必须select一个合适的表示。
还有几件事要考虑：
-
通过将权重存储在matrix中，matrix模型更容易使其具有加权边的图。 对象/指针模型需要将边权重存储在并行数组中，这需要与指针数组同步。
-
对象/指针模型比有向图更适合于有向图，因为指针需要成对维护，这可能会变得不同步。
对象和指针方法遭遇到search困难，正如一些人所指出的那样，但是对于像构build二叉search树这样的事情来说是非常自然的，因为在那里有很多额外的结构。
我个人喜欢使用邻接matrix，因为他们使用代数图论的工具使各种问题变得更加容易。 （邻接matrix的第k次幂给出从顶点i到顶点j的长度为k的path数目，例如在得到第k次幂前加一个单位matrix得到长度小于等于k的path数目，拉普拉斯的n-1未成年人获得生成树的数量…等等。）
但是大家都说邻接matrix内存很贵！ 他们只是一半的权利：你可以绕过这个使用稀疏matrix，当你的graphics有很less的边缘。 稀疏matrix数据结构只是保持邻接列表的工作，但仍然有全面的标准matrix操作可用，给你两全其美。
我认为你的第一个例子有点模糊 – 节点作为对象和边缘作为指针。 您可以通过只存储一个指向某个根节点的指针来跟踪这些情况，在这种情况下，访问给定的节点可能是效率低下的（例如，您需要节点4 – 如果未提供节点对象，则可能需要search它） 。 在这种情况下，还会丢失无法从根节点访问的graphics部分。 我认为这是f64彩虹所假设的情况，他说访问给定节点的时间复杂度是O（n）。
否则，你也可以保持一个数组（或散列图）充满指向每个节点的指针。 这允许O（1）访问给定的节点，但增加了一些内存使用。 如果n是节点的数量，e是边的数量，那么这种方法的空间复杂度就是O（n + e）。
matrix方法的空间复杂度将沿着O（n ^ 2）的线（假定边是单向的）。 如果你的图很稀疏，你的matrix中就会有很多空单元。 但是，如果你的graphics是完全连接的（e = n ^ 2），这与第一种方法相比是有利的。 正如RG所说，如果将matrix分配为一块内存，可能会减lesscaching未命中的数量，这可能会使graphics中的边沿更加快速。
第三种方法可能是大多数情况下空间效率最高的方法 – O（e） – 但是可以find给定节点的所有边缘为O（e）杂项。 我不能想到这将是非常有用的情况。
看看维基百科上的对照表 。 它能很好地理解何时使用图的每个表示。
好吧，如果边没有权重，matrix可以是一个二进制数组，使用二元运算符可以使事情真的在这种情况下变得非常快。
如果graphics稀疏，对象/指针方法似乎更有效率。 将数据结构中的对象/指针保存在一个特定的数据结构中，可能是一个很好的计划，也可能是任何让它们保持在一起的方法。
邻接列表 – 简单的连接节点列表 – 似乎是目前最有效的内存，但也可能是最慢的。
使用matrix表示方式逆向有向图很容易 ，使用邻接表可以很容易，但对于对象/指针表示则不是那么好。
还有另一种select：节点作为对象，边也作为对象，每个边同时在两个双向链表中：从同一个节点出来的所有边的列表和进入相同节点的所有边的列表。
struct Node { ... node payload ... Edge *first_in; // All incoming edges Edge *first_out; // All outgoing edges }; struct Edge { ... edge payload ... Node *from, *to; Edge *prev_in_from, *next_in_from; // dlist of same "from" Edge *prev_in_to, *next_in_to; // dlist of same "to" }; 内存开销很大（每个节点2个指针，每个边6个指针），但你会得到
- O（1）节点插入
- O（1）边缘插入（给出指向“从”和“到”节点的指针）
- O（1）边缘删除（给出指针）
- O（deg（n））节点删除（给定指针）
- O（deg（n））find节点的邻居
该结构也可以表示一个相当一般的图：带有循环的多重图（即，在相同的两个节点之间可以有多个不同的边，包括多个不同的循环 – 从x到x的边）。
