我有一个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+" ---> ");
}
}
我们应该忽略注释行吗? –
我现在要去调试这个。首先,我在Main的'let create nodes'位发现了两个未关闭的文字。如果您将该代码复制粘贴到StackOverflow,您可能需要先解决这些问题。它还用三个参数而不是两个调用了'g.connectNode'。 – Ghostkeeper
耶稣男人/女人,你可以完成一些工作,至少可以显示出错的地方。 –