0

假设我正在编写一个 Java 类来表示无向图的边。这个类Edge包含两个顶点to和from。

类边缘<顶点> {

  私人最终顶点到，从

  公共边缘（顶点到，顶点来自）{
    这.to = to;
    this.from = 从；
  }
  ... // getter, equals, hashCode ...
}

显然e1 = new Edge(v1, v2)，e2 = new Edge(v2, v1)在无向图中实际上是相同的。是否有意义？您将如何实施课程Edge以满足该要求？

4

4 回答 4

2

根据一些唯一标识符对构造函数中的顶点执行排序。这样，无论顺序如何，它们都可以一致地存储。

我发现这比 noMAD 的解决方案更可取，因为与这些对象交互的所有代码都会以相同的方式对待它们，而不仅仅是您的equals.

此外，调用您的班级成员to并且from令人困惑，因为它听起来像一个有向图。我会将它们重命名为更通用的名称，例如vertex1and vertex2。

  public Edge(Vertex x, Vertex y) {
      if (vertex2.getId() > vertex1.getId()) {
          this.vertex1 = x;
          this.vertex2 = y;
      } else {
          this.vertex1 = y;
          this.vertex2 = x;
      }
  }
于 2012-12-17T16:59:05.500 回答
2

实际上，我的Edge课堂上不会有这种逻辑，而是某种监督类，例如Graph类。这样做的原因是因为 anEdge只是一个有 2 个顶点的对象。它对图中的其余边一无所知。

因此，为了扩展@noMad 的答案，我实际上会将他的checkIfSameEdge方法放在我的Graph课堂上：

public class Graph {
    private List<Edge> edges;
    ....
    public void addEdge(Edge e) {
        for (Edge edge : edges) {
            if (isSameEdge(edge, e) {
                return; // Edge already in Graph, nothing to do
        }
        edges.add(e);
    }
    private boolean isSameEdge(Edge edge1, Edge edge2) {
        return ((edge1.to.equals(edge2.to) && edge1.from.equals(edge2.from))
             || (edge1.to.equals(edge2.from) && edge1.from.equals(edge2.to)))
    }
}

顺便说一句：我会重命名toand fromto vertex1andvertex2因为它是一个无向图，并且 to 和 from 指示方向，但这只是我的意见。

于 2012-12-17T16:59:21.043 回答
1

推测节点包含某种标量值 - 根据这些值对参数进行排序（使用 compareTo 方法）并使用工厂创建新实例或返回现有实例。

于 2012-12-17T16:58:24.263 回答
1

好吧，在我看来，最天真的方法是：

protected boolean checkIfSameEdge(Vertex to, Vertex from) {
  if(to.equals(this.from) && from.equals(this.to) || to.equals(this.to) && from.equals(this.from)) {
    return true;
  return false;
}

显然你将不得不覆盖equals和hashcode

于 2012-12-17T16:51:00.133 回答