bfs javaの2つの頂点の間のすべての辺を取得する方法

Question

現在、私は2つの頂点の間に1対1の関係しかありません。 2つの頂点の間の複数の関係を処理したいだけです。どうやってやるの？

私の現在のコードは次のとおりです。

public Collection<Vertex<V, E>> bfs() { 

    Queue<Graph.Vertex<V, E>> queue = new ArrayBlockingQueue<>(this.getVertices().size()); 
    Collection<Vertex<V, E>> queryVertices = new LinkedList<>(); 
    Vertex<V, E> source = this.vertices.get(0); 
    Set<Vertex<V, E>> visited = new HashSet<>(); 

    visited.add(source); 
    queue.add(source); 
    queryVertices.add(source); 

    while (!queue.isEmpty()) { 
     Graph.Vertex<V, E> v = queue.remove(); 
     Graph.Vertex<V, E> w; 
     while ((w = getAdjUnvisitedVertex(v, visited)) != null) { 
      visited.add(w); 
      queue.add(w); 
      queryVertices.add(w); 
     } 
    } 

    return queryVertices; 
} 

private Vertex<V, E> getAdjUnvisitedVertex(Vertex<V, E> v, Set<Vertex<V, E>> visited) { 

    for (Graph.Edge<V, E> edge : v.edges) { 
     if (!visited.contains(edge.getTo())) { 
      return edge.getTo(); 
     } 
    } 
    return null; 
} 

Answer 1

あなたの頂点クラス内の対応するノードのHashMapのか、ArrayListのを追加してみてください。エッジを追加すると、ids（またはVertexの他の識別機能）がArrayList/HashMapに追加され、各Vertexが接続されているノードを表示するたびにArrayList/HashMapをチェックするだけです。これは、ノード間にすでに存在するエッジを追加しない効率的なaddEdgeアルゴリズムの実装にも役立ちます。また、有向グラフNode A→Node B！= Node B→Node Aを実装しているかどうかを覚えているので、実装にエッジを残さないように注意してください。