0

我正在尝试使用顶点的“实时提要”在 Java 中创建一个无向图。我有来自 txt 文件的顶点。文件的结构是这样的，

1 2 #connect node 1 with node 2

2 3 #connect node 1 with node 2

等等。我决定创建一个 ArrayList 的 ArrayList（一个 2d ArrayList）来将节点和边存储在一个数组列表中。我的要求是我必须保持恒定的时间来检查两个边缘之间是否存在路径。我还没有真正使用过 2d ArrayList，你们的任何先机将不胜感激。

4

1 回答 1

0

这是我使用图表的观点以及我使用它们的经验。

第一的

图是图，不是数组，不是矩阵，不是这些。我为什么这么说？因为如果要在矩阵中表示关系，图的结构可能非常非常大。表示图的矩阵的增长可能呈指数增长。

与对象一起工作

您可以做的一种表示是使用 java 对象。创建两种类型的对象。一个是节点，另一个是边缘。Node 对象应该有一个边数组。像这样：（我不是Java开发人员，所以这里是python）

class Node:
    def __init__(self, value): #here is the constructor
        self.value = obj #here we are setting the identification of node
        self.edges = []
   def setEdges(self, edge)
        self.edges.append(edge)
   #do other stuffs

边缘将是这样的：

class Edge:
    def __init__(self, node1, node2, value):
        self.value = value
        self.nodes = [node1, node2]
        node1.setEdges(self) #self is the same as this in java
        node2.setEdges(self)

我们现在有什么？我们有一个对象将存储它所拥有的边，而另一个对象只存储一个值并设置他的关系。它可以设置关系。那么如何在主脚本中使用它呢？

主要脚本

这里很容易。看一个例子：

me = Node('Me')
you = Node('You')

那么，如何设置关系呢？

Edge(me, you, 'StackOverflow')

这是通过 StackOverflow 明确我和你的关系的边缘。在这里，您将能够在每个对象中看到它们具有的边缘数组，如下所示：

me.edges

这将返回 Edges 对象的数组，通过这个边，您可以找到您拥有的关系类型以及与谁的关系。

但是……这个边缘怎么不会被gb破坏呢？很简单，两个 Node 类都引用了 Edge 类。如果它们都与边缘类无关，则 gb 将消耗它。

通过 Java 中的参考

我不记得在 Java 中是如何通过 Ref 设置对象的。从大学开始我就没有用 Java 编程。因此，由于 Python byRef 是隐式的，因此要正确检查 java 中的 By Ref。

因此，通过此实现，您可以采用小型数组，并且可以确保您的节点和边沿存在关系。

于 2016-07-16T22:07:35.877 回答