-1

Preciso de um código que faça uma busca em largura e em profundidade usando grafos para a busca de caminho mais curto, analisando esse aspectos mencionado, mas não sei por onde começar, gostaria que alguém me ajudasse, serve Github também, caso alguém saiba.

3
  • pode ser o github também.../ Be the github too ... 13/02/2016 às 18:49
  • 1
    O site é em portugues, logo, você não precisa adicionar traduções para o ingles. É recomendado que você edite a pergunta, explicando melhor a dúvida, a pergunta está superficial demais,
    – user28595
    13/02/2016 às 19:03
  • Obrigado Diego Felipe, sou novato por aqui, e toda ajuda é bem vinda !! 13/02/2016 às 19:55

1 Resposta 1

3

Vou colocar só um, para te ajudar mas não parece correto copiar, caso for para um trabalho de faculdade ou sei lá.

LARGURA

public static int BuscaLargura(int ini,int fim){

        Fila f = new Fila(ini);

        int cor[] = new int[vertices];

        Largura = new int[vertices];

        for(int i=0;i<vertices;i++)
            Largura[i]=-1;

        int t = 0;

        while(!f.isEmpty())
        {
            int leitor[] = f.rem();

            for(int i=0;i<leitor.length;i++)
            {
                cor[leitor[i]] = Black;
                Largura[leitor[i]] = t;
                if(leitor[i]==fim)
                    output=t;

            }

            for(int i=0;i<ArestasIni.size();i++)
                for(int j=0;j<leitor.length;j++)
                    if((int)ArestasIni.get(i)==leitor[j] && cor[(int)ArestasFim.get(i)]==White)
                    {
                        cor[(int)ArestasFim.get(i)]=Gray;
                        f.add((int)ArestasFim.get(i));
                    }
            t++;

        }

    }

A cor indica que o nó foi visitado, Black é que já foi visitado . Este algoritmo é o que faz a busca de todos os nós utilizando uma pilha. Vai acumulando todos os próximos caminhos a partir dos nós que já estão nesta pilha, Apenas os nós que não forem pintados podem ser adicionados na pilha. Busca por profundidade é bem mais fácil e você também utiliza cor, mas não precisa utilizar pilha, você vai pelo caminho que for possível ir e se a cor já for Black você não passar por ali. 'Passar' significa executar o algoritmo recursivamente naquele nó. Você precisa passar a quantidade de passos por parâmetro nas chamadas recursivas com (i+1). O melhor algoritmo para menor caminho é o Dijkstra, mas o algoritmo de PRIM é mais simples. O problema do algoritmo de PRIM é que ele encontra o 'melhor local'. É o resulto bom, mas existem resultados melhores.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .