java - 在数据结构中存储边

Question

我有一个名为 Edge 的类，它具有属性源 ID、目标 ID 和权重。我想将这条边存储在一个集合数据结构中，所以在集合中不会有重复的边(即:具有相同源和目标 ID 的边)。

问题是这样的:我想向这个数据结构添加一个边。如果一条边已经存在于数据结构中，我不需要再次添加它，我只需要将现有边的权重与我要添加的边相加。

我很确定我必须重写集合的添加函数。有人可以给我一个指示吗？在 Java 中为此使用的最佳数据结构是什么？

Answer 1

一些建议。

你想要的底层数据结构可能是一个映射(HashMap 可能是最好的具体实现)，而不是一个集合。键应该是 (source, target) 对，值可以是你的 Edge 对象。如果您非常担心重复，有一些方法可以解决这个问题，其中一种方法是实际上只存储权重作为值。

其次，这是调用 Graph 类。如果你把接口(interface)设计的好，它隐藏了内部的实现细节。我强烈推荐使用组合而不是继承。换句话说，您的图表有一个 map ，而不是一个 map 。

另请查看现有代码，例如 JGraphT ，它已经有一个加权有向图，就像你上面描述的一样。有时最好不要从头开始重新发明。

祝你好运。