java - 编码图中的连接节点

Question

我正在尝试在 java 中制作一个具有不同节点的图形。有些节点会连接到其他节点，有些则不会。如果它们已连接，则该节点的某个布尔值将为真，另一个变量将保存它所连接的节点的值。

...关于你们认为最好的解决方法有什么建议吗？

Answer 1

表示图的两种最常见的方法是邻接矩阵和邻接表。设 n 为节点数。

邻接矩阵 A 是一个 nxn 布尔值矩阵，如果节点 i 和 j 连接，则 A(i, j) = 1，如果不连接，则为 0。

在每个节点的邻接列表表示中，您维护一个它连接到（相邻）的节点列表。

现在的问题是您想对图表做什么。如果它很简单，那么自己动手可能是有意义的。如果没有，您可能想在网上寻找一个 java 库来处理图形。 JGraphT已被提及。

如果您想使用邻接矩阵，那么您可以在 Java 中轻松地将其表示为 bool 或 int 的二维数组。您需要给每个节点一个索引。最简单的方法是将您的 Node 对象保存在一个数组中，并且始终保持相同的顺序。所以你真的会有两个数据结构：一个节点数组，它是代表你的节点实际是什么的对象，以及邻接矩阵，它通过它们的索引来引用节点。

填充矩阵后，您是否可以通过将所有列（或行）中的值（0 和 1）相加并找到最大值来轻松找到连接到大多数其他节点的节点。希望这可以帮助。

Answer 2

存储图形有两种标准模型。Tom 描述的是Adjacency List。另一个是独立的邻接矩阵。

如果您关心效率，请研究您的情况的稀疏性（边越多，矩阵版本对性能越友好）。如果性能不是问题，请使用您更愿意使用的程序...

Answer 3

创建一个Node类并给它一个类型的实例变量Node。将其初始化为 null - 如果所述节点连接到另一个节点，则此实例变量将引用它；否则，它将保持为空。

如果节点可能连接到许多节点（这对于图来说很常见），则使用 anArrayList来存储该节点连接到的所有节点。

Answer 4

可能是“好的 Java 图形算法库”的副本？'。简短的回答是看JGraphT。