在數據結構中存儲邊緣

我有一個名爲Edge的類，它具有屬性源ID，目標ID和權重。我想將這個邊存儲在一個集合數據結構中，所以在這個集合中不會有重複的邊（即：具有相同源和目標ID的邊）。在數據結構中存儲邊緣

問題是這樣的：我想添加一個邊緣到這個數據結構。如果數據結構中已經存在一條邊，我不需要再添加它，我只需要用我想要添加的邊添加現有邊的權重。

我非常確定，我必須重寫集合的add函數。有人能給我一個指針嗎？什麼是最好的數據結構在Java中使用呢？

2011-04-16 aherlambang

我寫這篇博客文章而回有關使用節點和邊緣找到代表倫敦地鐵圖的路線，大約包含HashMap會談，這樣的事情：http://digitalist-alex.blogspot.com/2011/01/breadth-first-implementation-for.html – Alex 2011-04-16 01:37:24

幾點建議。

你想要的基礎數據結構可能是一個映射（HashMap可能是最好的具體實現），而不是一個集合。鍵應該是（源，目標）對，並且該值可以是您的Edge對象。如果你非常關心重複，有辦法處理，其中之一是實際只存儲重量的價值。

其次，這是一個Graph類的調用。如果您設計的界面很好，它會隱藏內部實現細節。我建議高度使用組合而不是繼承。換句話說，你的圖有一張地圖，而不是一張地圖。

還可以看看現有的代碼，如JGraphT，它已經有一個加權有向圖，與上面描述的相同。有時候最好不要從頭開始重新創新。

祝你好運。

來源

2011-04-16 01:25:17

好吧，如果我打算使用HashMap，那麼源，目標對將是另一個類？你可以給我一個具體的代碼示例，因爲我從來沒有這樣做過.. – aherlambang 2011-04-16 01:30:28

你可以創建自己的班級。如果id只是int的話，那可能是最輕量級的方法。但請記住，您必須重寫.equals（）和.hashCode（）。有關更爲一般的示例，請參閱http://stackoverflow.com/questions/156275/what-is-the-equivalent-of-the-c-pairl-r-in-java。 – 2011-04-16 01:48:45

如果關鍵字只是將兩個字符串連接在一起，那麼我不必重寫equals？因爲鍵是字符串 – aherlambang 2011-04-16 01:50:22

另一種方法是在自己的類中包裝邊緣集合，該集合提供了您希望支持的接口。

這是在構圖和繼承之間進行選擇的特定情況。總的來說，作曲作品比繼承作品更受歡迎，儘管它也有其地位。

例如，這裏有一個可能的類的草圖（編輯：使用地圖）

public class Edge { ... } 

    public class EdgeData { 
     public Edge getEdge() { ... } 
     public float getWeight() { ... } 
    } 

    public class Edges { 
     private Map<Edge,EdgeData> m_edges = new HashMap<Edge,EdgeData>(); 
     public addEdge(EdgeData edge) { 
      // Do what you've said above. 

     } 
     public Map<Edge,EdgeData> getEdges() { return Collections.unmodifiableMap(m_edges); } 
    }

來源

2011-04-16 01:19:56

所以邊緣類的邊集？ – aherlambang 2011-04-16 01:25:49

這組邊緣本身可以是一個類 - 例如上面的Edges類。順便說一句，這只是一個例子。如果你開發自己的類，你控制暴露給客戶端的接口 - 不是我，而不是Set類。 – 2011-04-16 01:30:25

，但然後在addEdge裏面，我必須遍歷m_edges並檢查源目標是否已經存在？ – aherlambang 2011-04-16 01:33:06

那麼，Set.add（）方法返回一個布爾值，指示新項目是否已成功添加到集合中。如果它返回false是因爲該項目已經存在。基於此，您可以輕鬆編寫您的算法。醜陋的部分是不得不迭代集合來更新值，對吧？

if(!edges.add(newEdge)){ 
    Iterator<Edge> iter = edges.iterator(); 
    while(iter.hasNext()){ 
    Edge edge = iter.next(); 
    if(edge.equals(newEdge)){ 
     edge.updateWeight(newEdge.getWeight()); //this.weight+=moreWeight 
    } 
    } 
}

基於此，我假設你想要的只是一種美化所有這種迭代樣板代碼的方法。

我喜歡的解決方案是使用LambdaJ Collections來更新現有Edge的權重。

if (!edges.add(newEdge)) { 
    with(edges).first(is(newEdge)).updateWeight(newEdge.getWeight()); 
}

我不知道你在找什麼，但這種方法只是三行代碼。從我的觀點來看非常簡單。

我寫了一個小例子來說明更好的想法：

Jedi obiwan = new Jedi("Obiwan", 30, 40); // name, age and power 
Jedi luke = new Jedi("Luke", 18, 25); 
Jedi mace = new Jedi("Mace-Windu", 100, 450); 
Jedi yoda = new Jedi("Yoda", 150, 1000); 

Jedi obiAgain = new Jedi("Obiwan", 11, 40); 

Set<Jedi> jedis = new HashSet<Jedi>(asList(obiwan, luke, mace, yoda)); 

if (!jedis.add(obiAgain)) { 
    with(jedis).first(is(obiAgain)).updatePower(obiAgain.getPower()); 
} 

System.out.println(jedis);

來源

2011-04-16 05:38:26

在數據結構中存儲邊緣

回答

相關問題