将边存储在数据结构中

作者: 关于贤的记忆
发布时间: 2024-04-02 12:33:48 (23天前)
转自：

4 条回复

0#
回复此人
！啊啊 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 另一种方法是在您自己的类中包装边集，它提供了您希望支持的接口。 </p> <P> 这是在组合和继承之间进行选择的特定情况。一般来说，组合比继承更受欢迎，尽管它也有它的位置。 </p> <P> 例如，这是一个可能类的粗略草图（编辑：使用地图） </p> <pre> <code> 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 ); } } </code> </pre> </DIV>

编辑
1#
回复此人
别闹 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 一些建议。 </p> <P> 您想要的基础数据结构可能是一个映射（HashMap可能是最好的具体实现），而不是一个集合。键应该是（源，目标）对，值可以是您的Edge对象。如果你非常关心重复，有办法解决这个问题，其中一个方法是实际只存储权重作为值。 </p> <P> 其次，这是为了一个Graph类。如果您设计好接口，它会隐藏内部实现细节。我建议高度使用组合而不是继承。换句话说，您的图表有一个地图，而不是一个地图。 </p> <P> 另请查看现有代码，例如 <a href="http://www.jgrapht.org/" rel="nofollow"> JGraphT </A> ，已经有一个加权有向图，与你上面描述的相同的野兽。有时最好不要从头开始重新制作东西。 </p> <P> 祝好运。 </p> </DIV>

编辑
2#
回复此人
哈哈 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 好吧，Set.add（）方法返回一个布尔值，指示新项是否已成功添加到集合中。如果它返回false是因为该项已经存在。基于此，您可以轻松编写算法。丑陋的部分是必须迭代集合来更新值，对吧？ </p> <pre> <code> 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 } } } </code> </pre> <P> 基于此，我假设您想要的只是一种美化所有迭代样板代码的方法。 </p> <P> 我喜欢的解决方案正在使用 <a href="http://code.google.com/p/lambdaj/" rel="nofollow"> LambdaJ收藏 </A> 更新现有Edge的权重。 </p> <pre> <code> if (!edges.add(newEdge)) { with(edges).first(is(newEdge)).updateWeight(newEdge.getWeight()); } </code> </pre> <P> 我不知道你在找什么，但这种方法只有三行代码。从我的观点来看，这很简单。 </p> <P> 我写了一个小例子来说明这个想法： </p> <pre> <code> 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); </code> </pre> </DIV>

编辑

登录后才能参与评论