用戶輸入顯示最短路徑

Question

我有一個ArrayOutOfBounds異常，我不知道爲什麼。我試圖讓用戶輸入他們希望程序從哪個城市開始，然後讓我的程序從這一點執行廣度優先搜索。

我的程序在一個小時內到期，所以任何快速幫助都會很棒！

真的很快，我的程序在鄰接矩陣上執行廣度優先搜索！

謝謝你們，這是我的主：

 import java.util.*; 
import java.io.BufferedReader; 
import java.io.FileReader; 
import java.io.IOException; 
import java.util.Collection; 
import java.io.File; 
import java.io.FileNotFoundException; 

public class Main { 


    public static void main(String[] args) 
    { 



     //Lets create nodes 
     Node Seattle = new Node("Seattle"); 
     Node Vancouver=new Node("Vancouver"); 
     Node Portland = new Node("Portland"); 
     Node Houston = new Node("Houston"); 
     Node New_Orleans = new Node("New_Orleans"); 
     Node Miami = new Node("Miami"); 
     Node Omaha = new Node("Omaha"); 
     Node Louisville=new Node("Louisville"); 
     Node Boston = new Node("Boston"); 
     Node Boise = new Node("Boise "); 
     Node Chicago = new Node("Chicago"); 
     Node Jacksonville = new Node("Jacksonville"); 
     Node Baltimore = new Node("Baltimore"); 
     Node Detroit = new Node("Detroit"); 
     Node Nashville =new Node("Nashville "); 
     Node Oakland = new Node("Oakland "); 
     Node Denver= new Node("Denver "); 
     Node Olympia = new Node("Olympia"); 
     Node Memphis = new Node("Memphis"); 

// 
     //Create the graph, add nodes, create edges between nodes 
     g.addNode(Seattle); 
     g.addNode(Vancouver); 
     g.addNode(Portland); 
     g.addNode(Houston); 
     g.addNode(New_Orleans); 
     g.addNode(Miami); 
     g.addNode(Omaha); 
     g.addNode(Louisville); 
     g.addNode(Boston); 
     g.addNode(Boise); 
     g.addNode(Chicago); 
     g.addNode(Jacksonville); 
     g.addNode(Baltimore); 
     g.addNode(Detroit); 
     g.addNode(Nashville); 
     g.addNode(Oakland); 
     g.addNode(Denver); 
     g.addNode(Olympia); 
     g.addNode(Memphis); 

//  Scanner sc = new Scanner(System.in); 
//  String shortPath = sc.next(); 
//  Node spath = new Node(shortPath); 


     g.connectNode(Louisville,Memphis); 

     g.connectNode(Houston,Seattle); 

     g.connectNode(Boston,Vancouver); 

     g.connectNode(Boise,Seattle); 
     g.connectNode(Boise,Detroit); 
     g.connectNode(Boise,Oakland); 

     g.connectNode(Chicago,Olympia); 

     g.connectNode(Portland,Seattle); 

     g.connectNode(Jacksonville, Vancouver); 

     g.connectNode(Baltimore, Vancouver); 

     g.connectNode(Detroit, Boise); 

     g.connectNode(Seattle, Portland); 
     g.connectNode(Seattle, Houston); 
     g.connectNode(Seattle, Vancouver); 
     g.connectNode(Seattle, Denver); 
     g.connectNode(Seattle, Boise); 

     g.connectNode(Nashville, Memphis); 

     g.connectNode(Oakland, Boise); 
     g.connectNode(Oakland, Vancouver); 

     g.connectNode(Vancouver, Seattle); 
     g.connectNode(Vancouver,Olympia); 
     g.connectNode(Vancouver,Jacksonville); 
     g.connectNode(Vancouver,Baltimore); 
     g.connectNode(Vancouver,Oakland); 
     g.connectNode(Vancouver,Boston); 

     g.connectNode(Denver, Seattle); 

     g.connectNode(Olympia,Vancouver); 
     g.connectNode(Olympia,Omaha); 
     g.connectNode(Olympia,Chicago); 

     g.connectNode(Memphis,Nashville); 
     g.connectNode(Memphis,Louisville); 
     g.connectNode(Memphis,Omaha); 

     g.setRootNode(Houston); 
     //Perform the traversal of the graph 
     System.out.println("Shortest path is ------------->"); 
     g.bfs(); 
     ; 
//  } 
//  else { 
//   throw new InvalidInputException(); 
//  } 

     long lEndTime = System.currentTimeMillis(); 
     long difference = lEndTime - lStartTime; 
     System.out.println("\nElapsed Time: " + difference + " ms"); 



    } 

} 

Node類：

public class Node 
{ 


    public String label; 
    public String label2; 
    public boolean visited=false; 
    //public Object equals; 
    public Node(String name) 
    { 
     this.label= name; 
//  this.label2 = name2; 
    } 
} 

和我的圖類：

import java.io.FileNotFoundException; 
import java.util.*; 


public class Graph 
{ 
    //added 
// Vertex[] adjLists; 

    public Node rootNode; 
    public ArrayList nodes=new ArrayList(); 
    public int[][] adjMatrix;//Edges will be represented as adjacency Matrix 
    int size; 

    public void setRootNode(Node city) 
    { 
     this.rootNode=city; 
    } 

    public Node getRootNode() 
    { 
     return this.rootNode; 
    } 

    public void addNode(Node city) 
    { 
     nodes.add(city); 
    } 

    //This method will be called to make connect two nodes 
    public void connectNode(Node start,Node end) 
    { 
     if(adjMatrix==null) 
     { 
      size=nodes.size(); 
      adjMatrix=new int[size][size]; 
     } 

     int startIndex=nodes.indexOf(start); 
     int endIndex=nodes.indexOf(end); 
     adjMatrix[startIndex][endIndex]=1;  //initializing matrix with size 1 by 1 
     adjMatrix[endIndex][startIndex]=1; 
    } 

    private Node getUnvisitedChildNode(Node n) 
    { 

     int index=nodes.indexOf(n);    //index is = to index of nodes 
     int j=0; 
     while(j<size) 
     { 
      if(adjMatrix[index][j]==1 && ((Node)nodes.get(j)).visited==false) 
      { 
       return (Node)nodes.get(j); 
      } 
      j++; 
     } 
     return null; 
    } 

    //BFS traversal of a tree is performed by the bfs() function 
    public void bfs() 
    { 

     //BFS uses Queue data structure 
     Queue q=new LinkedList(); 
     q.add(this.rootNode); 
     printNode(this.rootNode); 
     rootNode.visited=true; 
     while(!q.isEmpty()) 
     { 
      Node n=(Node)q.remove(); 
      Node child=null; 
      while((child=getUnvisitedChildNode(n))!=null) 
      { 
       child.visited=true; 
       printNode(child); 
       q.add(child); 
      } 
     } 
     //Clear visited property of nodes 
     clearNodes(); 
    } 


    //Utility methods for clearing visited property of node 
    private void clearNodes() 
    { 
     int i=0; 
     while(i<size) 
     { 
      Node n=(Node)nodes.get(i); 
      n.visited=false; 
      i++; 
     } 
    } 

    //Utility methods for printing the node's label 
    private void printNode(Node rootNode2) 
    { 
     System.out.print(rootNode2.label+" ---> "); 
    } 





} 

Answer 1

看來，在Graph.getUnvisitedChildNode，你通過搜索nodes陣列與nodes.indexOf(n)。這是首先在隊列的第一個元素上完成的，這是根節點，這是很好的。

但是，在Main（第130行，請參閱編輯）中將根節點設置爲new Node(shortPath)。這個新節點永遠不會被添加到數組中。 Java看起來不在這個節點內的標籤可能是什麼，但是當前看起來只有它是Node的同一個實例。

你可以嘗試通過添加下面的方法將Node類來解決這個問題：

@Override 
public boolean equals(Object o) { 
    if(o == null) return false; 
    if(!(o instanceof Node)) return false; 
    return label.equals(((Node)o).label); 
} 

這種方法會說，兩個節點都是平等的，如果他們的標籤是相等的。我希望這會修復你的樹。我會馬上嘗試，而你試圖解釋我的代碼實際上做了什麼。

編輯：你在這裏修改了代碼，它現在被註釋掉了，並且在不同的行上。

編輯2：添加覆蓋equals方法似乎工作，對我來說。