2

私はGraphクラスを書いています、

HashMapノードの ID (int 値) が関連付けられたノードにマップされている を保持し、アプローチを使用してadjacency list、ノードから開始するエッジを保持します (それらを の形式に保持しますHashSet) 。

注意: このグラフは有向で重み付けされていません。

class のオブジェクトに対してイテレータを返すメソッドを実装したいEdge:

この iterator で次に取得すると、トラバースされているときに作成されるクラス Edge のオブジェクトが取得されます。ノードの隣接ノードがなくなった場合は、次のノードに移動し (順序は重要ではありません)、存在しない場合はより多くの開始ノード (すべてがトラバースされます)、終了します。

以前にエッジを Edge クラス オブジェクトに保持せずに、このイテレータをエッジに実装する方法についてのアイデアはありますか?

class Graph{
    HashMap<Integer , GraphNode> nodes;
    public Graph(){
        nodes = new HashMap<Integer ,GraphNode>();
    }
    public boolean addEdge(GraphNode n1 , GraphNode n2){
        if (!nodes.containsKey(n1) || !nodes.containsKey(n2))
            return false;
        return n1.addNeighbor(n2);
    }
    public boolean addNode(int id){
        if (nodes.containsKey(id))
            return false;
        nodes.put(id , new GraphNode(id));
        return true;
    }
    public boolean removeNode(GraphNode n1){
        if (!nodes.containsKey(n1.content))
            return false;
        for (GraphNode m : n1.neighbors)
            m.removeNeighbor(n1);
        nodes.remove(n1);
        return false;
    }
    public boolean removeEdge(GraphNode n1 , GraphNode n2){
        if (!nodes.containsKey(n1) || !nodes.containsKey(n2))
            return false;
        return n1.removeNeighbor(n2);
    }
    public Iterator<GraphNode> NodeIterator(){
        return nodes.values().iterator();
    }


   public Iterator<Edge> EdgeIterator(){
        Iterator<GraphNode> itr = this.NodeIterator();
        while (itr.hasNext){
            GraphNode n = itr.next();
            //......

        }
    }

}
class GraphNode{
    HashSet<GraphNode> neighbors;
    int content;
    public GraphNode(int content){
        this.content = content;
        neighbors = new HashSet<GraphNode>();
    }
    boolean addNeighbor(GraphNode n){
        if (neighbors.contains(n))
            return false;
        neighbors.add(n);
        return true;
    }
    boolean removeNeighbor(GraphNode n){
        if (!neighbors.contains(n))
            return false;
        neighbors.remove(n);
        return true;
    }


   }

class Edge{
    Node start , end;
    public Edge(Node start , Node end){
        this.start = start;
        this.end = end;
    }
}
4

2 に答える 2

1

私はこのようなものがうまくいくと思います:

public Iterator<Edge> EdgeIterator(){
    Iterator <Edge> edgeIter = new Iterator<Edge>() {

        private Iterator<GraphNode> itr = this.NodeIterator();
        private GraphNode currentNode;
        ... // additional private members as required

        public void remove()
        {
          // you don't have to implement this method if you don't need to support
          // this operation
        }

        public Edge next()
        {
          if (!hasNext())
            throw new NoSuchElementException ();

          return new Edge (x , y); // where you find x & y based on the current state 
                                   // of the iterator (kept in the private members of 
                                   // this instance)
        }

        public boolean hasNext()
        {
            return ?; // you return a boolean value based on the current state 
                      // of the iterator (kept in the private members of 
                      // this instance)
        }
    };

    return edgeIter;
}

EdgeIteratorメソッドは を作成し、インターフェイスのIterator<Edge>メソッドを定義しIteratorます (これらのメソッドの実装はあなたに任せました)。インスタンスにはのIteratorインスタンスが含まれておりIterator<GraphNode>、これを使用してノードを反復処理します。

現在のノード (ノード イテレータによって返された最後のノード) と反復処理中の現在のエッジを追跡する、いくつかの追加のプライベート メンバーをイテレータに追加する必要があります。ノードのエッジの反復処理が終了するたびに、次のノードを使用して次のノードを取得しますitr.next()(次のノードが使用可能であることを確認した後)。エッジ イテレータのは、それらのプライベート メンバーに基づいnext()て次のイテレータを構築できます。Edge

于 2013-06-27T21:19:15.867 に答える