我有一个bfs方法,它在邻接列表中查找两个节点之间的路径。但是,我注意到如果我索引无序的节点,那么它将找不到路径。
这是我的密码:
public boolean isPath(int vorigin, int vdestiny)
{
boolean result = false;//devuelve si el camino existe
boolean[] visited = new boolean[nodes.size()];//Booleano para marcar nodos como visitados
Queue<Integer> cola = new ArrayDeque<>();//Cola en la que se van guardando los nodos
cola.add(vorigin);
visited[vorigin] = true;
while(!cola.isEmpty()){
int vertice = cola.poll();//Se saca el primer nodo de la cola, y se guarda en vertice
visited[vertice]=true;//vertice se marca como visitado
if(vertice == vdestiny){
result = true;
break;
}
ArrayList<NodeAdj> vecinos = nodes.get(vertice).adjList;
for (NodeAdj vecino : vecinos) {
if(!visited[vecino.data]){//Se verifica que el nodo con este dato no este visitado
cola.add(vecino.data);
}
}
}
return result;
}
以下是节点及其邻接的索引:
public static void main(String[] args) {
Graph_AdjList myGraph = new Graph_AdjList();
myGraph.addNode(0);
myGraph.addNode(1);
myGraph.addNode(3);
myGraph.addNode(2);
myGraph.addAdjacency(0, 1, 2);
myGraph.addAdjacency(1, 3, 4);
myGraph.addAdjacency(3, 2, 5);
if(myGraph.isPath(0,2)==true){
System.out.println("There is a path");
}else{
System.out.println("There is no path");
}
}
为了以防万一,这里有一个函数可以为节点添加连接:
public void addAdjacency(int data_node1, int data_node2, int cost)
{
//
Node node1;
node1 = searchNode(data_node1);
if(node1 != null)
{
node1.addAdjacency(data_node2, cost);
}
}
我可能是一个很简单的东西,我一直忽视,但任何给予的帮助将不胜感激。提前谢谢!
暂无答案!
目前还没有任何答案,快来回答吧!