2017-12-04 4 views
-1

重み付けされていないグラフから最短経路を見つけて印刷する方法を見つけるには、特定の位置から開始し、次に2番目の整数が見つかるまで進みます。私はたくさんのことを試しましたが、何も私が探している結果を与えるものではありません。あなたの時間をありがとう、私は下のクラスを含めることになります。あなたが見てみる場合は重み付けされていないグラフの最短経路

public class graph { 
     int Vertices; 
     LinkedList<Integer> adjListArray[]; 
     Hashtable hs; 
     Hashtable hs2; 

     graph(int vertices) 
     { 
      this.Vertices = vertices; 
      adjListArray = new LinkedList[vertices]; 
      for(int i = 0; i < vertices ; i++){ 
       adjListArray[i] = new LinkedList<>(); 
      } 
     } 
    public void getHastables(Hashtable hs, Hashtable hs2) { 
     this.hs = hs; 
     this.hs2 = hs2; 
    } 

    public void addEdge(int v1, int v2) 
    { 
     adjListArray[v1].addFirst(v2); 


     adjListArray[v2].addFirst(v1); 
    } 

    public void printGraph() 
    {  
     for(int v = 0; v < Vertices; v++) 
     { 
      System.out.println("Adjacency list of vertex "+ v); 
      System.out.print("self"); 
      for(Integer pCrawl: adjListArray[v]){ 
       System.out.print(" -> "+pCrawl); 
      } 
      System.out.println("\n"); 
     } 
    } 
    ///////=================================================================================////////// 
///////=================================================================================////////// 
///////=================================================================================////////// 


    public void BFS(int start, int finish) 
    { 
     Map<Integer, Integer> prev = new HashMap<Integer, Integer>(); 
     int s = start; 

     boolean visited[] = new boolean[Vertices]; 
     LinkedList<Integer> queue = new LinkedList<Integer>(); 
     LinkedList<Integer> parent = new LinkedList<Integer>(); 
     visited[start]=true; 
     queue.add(start); 
     while (queue.size() != 0) 
     { 

       start = queue.poll(); 


       if(start == finish) { 

        break; 
      } 
      else { 

      Iterator<Integer> i = adjListArray[start].listIterator(); 
      while (i.hasNext()) 
      { 
       int n = i.next(); 
       if (!visited[n]) 
       { 
        visited[n] = true; 
        queue.add(n); 

        prev.put(n,start); 
       } 
      } 
      parent.add(start); 
      } 

     } 

    if(start != finish) { 
    System.out.println("there is no path between" + hs2.get(s) + " and " + hs2.get(finish)); 
    } 
    else { 
    System.out.println("Path between " + hs2.get(s) + " and "+ hs2.get(finish)); 
    System.out.print(hs2.get(s) + "-->"); 


    while(parent.size() != 0) { 
     System.out.println(hs2.get(parent.poll())); 
    } 

    ////////////////////////////////////////////// 

    int pos = finish; 
    while(prev.get(pos)!=null) { 
     System.out.println("try2 for prev " + hs2.get(pos)); 
     pos --; 
    } 

答えて

0

あなたが最短経路としてparentリストを印刷している、このリストは基本的に、あなたはおそらく欲しいものではありませんqueueから削除されたすべての要素のコピーです。

ノードaからノードbに到着したことを伝えるためにprevマップがある場合、この情報を逆方向に使用して最短パスを再構築できるはずです。 prevに存在しない値が見つかるまで、宛先からprevマップをトラバースするだけです。

ちょうどあなたのアイデアを与えるために、可能でテストされていない実装は次のようになります。

int current = finish; 
Stack<Integer> stack = new Stack<>(); 
stack.push(current); // finish should go in the path 
while (prev.containsKey(current)) { 
    current = prev.get(current); 
    stack.push(current) 
} 
// now stack contains the shortest path 
+0

私が参照してください!それは多くの意味がある、私はまだ私の反復はそのように見えるのですか?私は私のエッジに問題があるかもしれません。あなたの時間をありがとう! – DJM555

+0

まあ、私はあなたのコードの唯一の間違った部分は、最短パスの回復であると仮定して、私が指定したロジックを取り、あなたのユースケースに適応させて、試した後に特定の質問があるかどうか尋ねることができます。 – AlexITC

関連する問題