java - 存储无向图最有效的方法是什么？

Question

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

例如，假设我有多个位置以各种方式相互连接，我必须遍历图表以查看它是否已连接..任何帮助/评论都会有所帮助，谢谢！

score 5 · Accepted Answer

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

score 1 · Accepted Answer

1

使用没有对称性的邻接矩阵，从而表示方向而不是简单的邻接。

于 2011-02-14T21:26:22.543 回答

score 1 · Accepted Answer

使用关联或邻接矩阵可以解决问题。

如果您使用邻接矩阵，如果您有很多节点，则使用稀疏矩阵可能会很有效。Colt提供了一个稀疏矩阵实现。信息取自此 SO 帖子。

另外，我之前已经成功使用过JUNG，所以你可能想看看他们是如何实现有向图的。

score 0 · Accepted Answer

为了查找效率 - 使用布尔矩阵（如果有弧连接节点，则为 true，如果没有，则为 false）。为了提高内存效率，将您的对象属性之一定义为其指向的对象的（动态）列表。请注意，只有当您的图中有很多节点时，后者才会有所帮助。

score 0 · Accepted Answer

我错过了什么吗？数据已经是一个图，只需序列化它。对于书面讨论矩阵的问题完全为时过早。

5 回答 5