在数据结构中存储边缘

我有一个名为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

在数据结构中存储边缘

回答

相关问题