指定された2つの頂点の間にウェイト付きの有向グラフ内にパスが存在するかどうかを調べる

Question

isReachable(E fromKey, E toKey)メソッドを実装して、グラフ内の指定された2つの頂点の間にパスがあるかどうかを調べようとしています。私は、VertexとEdgeという2つの内部データ構造を使ってグラフの頂点と辺を表現するジェネリッククラスGraph<E>を持っています。ここではそのためのコードは次のとおりです。

public class Graph<E extends Comparable<E>> implements GraphAPI<E> 
{ 
    /* 
    * number of vertices (size of this graph) 
    */ 
    private long order; 
    /** 
    * pointer to the list of vertices 
    */ 
    private Vertex first; 

    /** 
    * A vertex of a graph stores a data item and references 
    * to its edge list and the succeeding vertex. The data 
    * object extends the comparable interface. 
    */ 
    private class Vertex 
    { 
     /** 
     * pointer to the next vertex 
     */ 
     public Vertex pNextVertex; 
     /** 
     * the data item 
     */ 
     public E data; 
     /** 
     * indegree 
     */ 
     public long inDeg; 
     /** 
     * outdegree 
     */ 
     public long outDeg; 
     /** 
     * pointer to the edge list 
     */ 
     public Edge pEdge; 
     /** 
     * Field for tracking vertex accesses 
     */ 
     public long processed; 
    } 

    /** 
    * An edge of a graph contains a reference to the destination 
    * vertex, a reference to the succeeding edge in the edge list and 
    * the weight of the directed edge. 
    */ 
    private class Edge 
    { 
     /** 
     * pointer to the destination vertex 
     */ 
     public Vertex destination; 
     /** 
     * weight on this edge 
     */ 
     public Double weight; 
     /** 
     * pointer to the next edge 
     */ 
     public Edge pNextEdge; 
    } 
    /** 
    * Constructs an empty weighted directed graph 
    */ 
    public Graph() 
    { 
     first = null; 
     order = 0; 
    } 
} 

これは私の思考プロセスである：指定fromKeyを含む頂点に到達するまで （1）頂点のリストを歩きます。 （2）隣接する各頂点をfromKeyにキューに追加する。 （3）キューが空でない間に、キューの先頭にある頂点を取り出して削除し、そのキーをtoKeyと比較します。 （4）一致する場合は真を返し、そうでない場合は、隣接する各頂点のエッジリストを検索し続ける。

はここで、これまでの方法のために私のコードです：

/** 
* Determines whether there is an outdirected path between two 
* vertices. 
* @param fromKey - search key of the originating vertex. 
* @param toKey - search key of the destination vertex. 
* @return true on success or false on failure. 
*/ 
public boolean isReachable(E fromKey, E toKey) 
{ 
    ArrayList<Vertex> queue = new ArrayList<Vertex>(); 
    E tmpKey = fromKey; 
    Edge tmpEdge; 
    Vertex tmp = first; 
    while (tmp != null) 
    { 
     if (tmp.data.equals(tmpKey)) 
     { 
      tmpEdge = tmp.pEdge; 
      while (tmpEdge != null) 
      { 
       queue.add(tmpEdge.destination); 
       tmpEdge = tmpEdge.pNextEdge; 
      } 
      tmp = first; 
      tmpKey = queue.remove(0).data; 
      if (tmpKey.equals(toKey)) 
       return true; 
     } 
     tmp = tmp.pNextVertex; 
    } 
    return false; 
} 

これは、指定された2つのキーの間のパスが存在する場合に動作しますが、そこにいない場合に境界エラーのうち、インデックスがスローされます。

これは私が持っているサンプルデータのためにトレース隣接リストである：私はisReachable(5, 3)を呼び出すと

1 -> null 
2 -> 1 -> 11 -> 12 -> null 
3 -> 2 -> 4 -> null 
4 -> null 
5 -> 4 -> null 
6 -> 5 -> 7 -> 13 -> 14 -> 15 -> null 
7 -> 12 -> null 
8 -> 7 -> 9 -> 10 -> 11 -> 12 -> null 
9 -> 1 -> null 
10 -> null 
11 -> 1 -> 12 -> null 
12 -> null 
13 -> null 
14 -> 2 -> 3 -> null 
15 -> 3 -> 5 -> 14 -> null 

、例えば、私は境界例外外のインデックスを取得します。しかし、（15,2）のメソッドを呼び出すとtrueを返します。

ここからどこに行くのかはわかりません。友人は問題へのBFSのアプローチを試みることを提案しましたが、私は彼の説明に本当に従っていませんでした。正しい軌道にいるのですか？どんな助けもありがとうございます。

Answer 1

これは基本的なグラフ検索アルゴリズムで、googleの「幅優先探索」を出発点としています。訪問したノードを把握する必要がありますが、これはまだ完了していません。

また、ArrayListをキューを維持するために使用しないでください。remove操作は遅いです。特に、すべてを1つずつコピーする必要があるため、配列の先頭にある要素を削除するのが遅いです。直接Queueを使用してください（https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html）