Pessoal estou fazendo um trabalho de busca entre dois vértices de um grafo, no qual o vértice de saída é inserido em uma fila e a cada expansão eles são colocados na fila tb e depois retirado da mesma e inserido em uma lista de vértices visitados onde eu guardo o vértice atual e o de qual ele veio.
O problema é que não estou conseguindo guardar o vértice retirado da fila, ele sempre guarda o ultimo inserido da fila ao invés do primeiro, já alterei o código varias vezes e sempre acontece a mesma coisa, até coloquei uns system.out.printl pra ver se a fila estava sendo formada corretamente , mesmo com a fila tendo seis itens e colocando um getLast e um getFirst ela sempre retorna o mesmo vértice.
Se alguém puder me dar uma dica fico muito agradecido.
/*Metodo para achar o melhor caminho entre dois nós utilizando a busca em
*aplitude, retorna uma lista com o caminho ótimo, caso o no de chegada
*não esteja no grafo retorna um array[0] com valor -1
*/
public int[] BuscaMelhorCaminho(int noSaida, int noChegada) {
//Cria os objetos necessarios para executar o programa
int indice = noSaida;
int tam = matrizAdjacencias.length;
int[][] CopiaMatriz = matrizAdjacencias;
int custo = 0;
int pai = -1;
GuardaNo noEcusto = new GuardaNo(noSaida,pai, custo);
GuardaNo noEcustoTemp = new GuardaNo();
LinkedList listaNos = null;
LinkedList filaNos = null;
//LinkedList pode ser usada como uma fila ou pilha, depende somente do
//inserir no topo ou no fim remover no topo ou no fim.
listaNos = new LinkedList();
filaNos= new LinkedList();
listaNos.add(noEcusto); //insere no começo da lista e da fila
filaNos.add(noEcusto);
System.out.println(" colocando na lista "+noEcusto.noAtual+" "+noEcusto.noPai+" "+noEcusto.custo+" Tamanho da lista "+filaNos.size());
System.out.println(" colocando na fila "+noEcusto.noAtual+" "+noEcusto.noPai+" "+noEcusto.custo+" Tamanho da fila "+filaNos.size());
System.out.println("");
while(!filaNos.isEmpty())
{
custo = custo + 1;
for(int i=0; i<tam; i++)
{
if(CopiaMatriz[indice][i]==1)
{ //Insere os nos filhos na fila de nos (filaNos) e marca como
//*visitados os nos inseridos
noEcusto.noAtual=i;
noEcusto.noPai=indice;
noEcusto.custo= custo;
CopiaMatriz[indice][i]=0;
filaNos.addLast(noEcusto);//insere no final da fila
System.out.println(" colocando na fila "+noEcusto.noAtual+" "+noEcusto.noPai+" "+noEcusto.custo+" Tamanho da fila "+filaNos.size());
//indice serve para controlar o proximo no a ser inserido na fila
indice = noEcusto.noAtual;
}
}
//recupera o primeiro item da fila e remove
noEcustoTemp = (GuardaNo) filaNos.removeFirst();
System.out.println("1*tenta inserir na lista "+noEcustoTemp.noAtual+" "+noEcustoTemp.noPai+" "+noEcustoTemp.custo+" Tamanho da lista "+listaNos.size()+" fila"+filaNos.size());
noEcustoTemp = (GuardaNo) filaNos.removeLast();
System.out.println("2*tenta inserir na lista "+noEcustoTemp.noAtual+" "+noEcustoTemp.noPai+" "+noEcustoTemp.custo+" Tamanho da lista "+listaNos.size()+" fila"+filaNos.size());
//noEcustoTemp = (GuardaNo) filaNos.remove();
listaNos.addLast(noEcustoTemp);
//listaNos = InsereNo(noEcusto,listaNos);
System.out.println("tenta inserir na lista "+noEcustoTemp.noAtual+" "+noEcustoTemp.noPai+" "+noEcustoTemp.custo+" Tamanho da lista "+listaNos.size()+" fila"+filaNos.size());
//teste para verificar se a função funciona(OK), recupera o objeto corretamente
//cria corretamente o melhor caminho
//System.out.println(noEcusto.noAtual+" ** "+noEcusto.noPai+" "+noEcusto.custo);
/*Verifica se o ultimo no inserido e o caminho de chegada , caso seja
*chama o metodo para retornar um array com o caminho
*caso contrario remove o primeiro no da fila e repete o processo até a
*fila ficar vazia
*/
if(noEcusto.noAtual==noChegada)
{
return CaminhoNos(listaNos);
}
else
{
filaNos.removeFirst();
}
}//fim while
return CaminhoNos(listaNos);
}