Java中無向圖的邊緣

假設我正在編寫一個Java類來表示無向圖的邊。此類Edge包含兩個頂點to和from。Java中無向圖的邊緣

 
class Edge<Vertex> { 

    private final Vertex to, from 

    public Edge(Vertex to, Vertex from) { 
    this.to = to; 
    this.from = from; 
    } 
    ... // getters, equals, hashCode ... 
}

顯然e1 = new Edge(v1, v2)和e2 = new Edge(v2, v1)實際上是無向圖是相同的。是否有意義？你將如何實現類Edge以滿足這一要求？

來源

2012-12-17 Michael

你是否想對有向邊和無向邊使用這一個實現？我會重新考慮這一點。 – bowmore

好了，我的頭頂部，該naivest方法是：

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-17 16:51:00 noMAD

另請參見：http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html –

想必節點包含某種標量值 - 排序基於這些值的參數（使用compareTo方法）並使用工廠創建新實例或返回現有實例。

來源

2012-12-17 16:58:24 symcbean

根據某個唯一標識符對構造函數中的頂點執行排序。這種方式，不管順序如何，它們都是一致的。

我覺得這比noMAD的解決方案更合適，因爲與這些對象交互的所有代碼都會以相同的方式處理它們，而不僅僅是您執行的equals。

此外，打電話給您的班級成員to和from令人困惑，因爲它聽起來像是有向圖。我會重新命名這些更通用的東西，如vertex1和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-17 16:59:05 dbyrne

我喜歡這個解決方案，但它假設'Vertex'有一些可比較的'Id'。然而，數學中的圖並不假設。 – Michael

我其實不會有這種邏輯在我Edge類，而是某種過度眼見類如Graph類。原因是因爲Edge只是一個有2個頂點的對象。它不知道圖中其餘邊的任何內容。

所以，爲了擴大對@牧民的回答，我真的把他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))) 
    } 
}

BTW：我會重新命名to和from到vertex1和vertex2，因爲它是一個無向圖並指示方向，但這只是我的觀點。

來源

2012-12-17 16:59:21

Java中無向圖的邊緣

回答

相關問題