什么是最有效的方式来存储一个非有向图？

Question

正如标题所说......在java中存储连通图的最有效方法是什么？

例如可以说我有互相连接的各种方式的多个位置，我必须通过图形来遍历，看看它的连接..任何帮助/意见将是有益的感谢！

Answer 1

一个常用的表示法是由图中所有节点索引的矩阵（二维数组），其中M[i,j] == true是否存在从节点i到j的有向边。主题的一个变体是存储两个节点之间边缘的长度/权重（缺失边缘可能由值-1表示）。

Answer 2

使用adjacency matrix无对称性，从而表示方向，而不是简单的相邻关系。

Answer 3

对于查找效率 - 使用布尔矩阵（真，如果有连接的节点，假如果没有电弧）。为了内存效率，将其中一个对象属性定义为其指向的（动态）对象列表。注意后者只会帮助图表中有很多节点。

Answer 4

使用的incidence或adjacency矩阵将这样的伎俩。

如果您使用的邻接矩阵，一个sparse matrix可能是有效地使用，如果你有很多节点。 Colt提供了一个稀疏矩阵实现。信息取自this SO post。

另外，我之前已经成功地使用了JUNG，因此您可能需要仔细研究一下它们是如何实现有向图的。

Answer 5

我缺少的东西？数据已经是一个图表，只是将其序列化。对于矩阵的书面讨论这个问题是完全不成熟的。