search for depth and width using graphs

Asked

Viewed 2,404 times

-1

I need a code that does a wide and deep search using graphs for the shortest path search, analyzing these aspects mentioned, but I don’t know where to start, I would like someone to help me, serve Github too, in case someone knows.

java python logic

  • can be github too.../ Be the github Too ...

  • 1

    The site is in English, so you don’t need to add English translations. It is recommended that you edit the question, explaining the doubt better, the question is too superficial,

  • Thanks Diego Felipe, I’m new around here, and all help is welcome !!

1 answer

3


I’ll just put one in to help you but it doesn’t seem right to copy it in case I go to a college job or whatever.

WIDTH

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++;

        }

    }

The color indicates that the node has been visited, Black has already been visited . This algorithm is what searches for all nodes using a stack. Accumulating all the next paths from the nodes that are already on this pile, only nodes that are not painted can be added to the pile. Search for depth is much easier and you also use color, but do not need to use stack, you go the way it is possible to go and if the color is already Black you do not go there. 'Pass' means to run the algorithm recursively on that node. You need to pass the amount of steps per parameter in recursive calls with (i+1). The best algorithm for the shortest path is Dijkstra, but the PRIM algorithm is simpler. The problem with the PRIM algorithm is that it finds the 'best location'. It is the good result, but there are better results.

Browser other questions tagged java python logic

You are not signed in. Login or sign up in order to post.