Pages: [1]   Go Down
Print
Author Topic: Cammino di un grafo matrice adiacenza  (Read 1871 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« on: 02-12-2010, 17:17:59 »

Come da oggetto, qualcuno sa come trovare un cammino da un nodo start a un nodo finale?
Logged
matteobuffa
Administrator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 258


Why so serious?


« Reply #1 on: 02-12-2010, 17:27:16 »

Dijkstra è una possibilità. Ma questo ti trova il cammino minimo e si basa su un grafo orientato e pesato. Forse te cerchi un algoritmo che cerca solo di capire se esiste un percorso da S a F (Sorgente e Fine).

Matteo
« Last Edit: 02-12-2010, 17:34:15 by matteobuffa » Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #2 on: 02-12-2010, 17:48:37 »

Dijkstra è una possibilità. Ma questo ti trova il cammino minimo e si basa su un grafo orientato e pesato. Forse te cerchi un algoritmo che cerca solo di capire se esiste un percorso da S a F (Sorgente e Fine).

Matteo
Appunto, già avevo visto l'algortimo di Dijkstra, ma non mi serve calcolare il cammino minimo, bensì dovrei stampare il percorso da un nodo start a un nodo fine, una sorta di dfs modificata.
Logged
matteobuffa
Administrator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 258


Why so serious?


« Reply #3 on: 02-12-2010, 17:58:51 »

Questo link dovrebbe esserti utile allora.

Matteo
« Last Edit: 02-12-2010, 18:04:11 by matteobuffa » Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #4 on: 02-12-2010, 18:02:09 »

Questo link dovrebbe esserti utile allora.

Matteo
Non funziona il link
Logged
matteobuffa
Administrator
Apprendista Forumista
*****
Offline Offline

Gender: Male
Posts: 258


Why so serious?


« Reply #5 on: 02-12-2010, 18:04:44 »

Ora si  pray

Matteo
Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #6 on: 02-12-2010, 18:19:36 »

Grazie ora gli do un'occhiata
Logged
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #7 on: 02-12-2010, 22:10:44 »

Questo link dovrebbe esserti utile allora.

Matteo
Non funziona il link
Secondo te questo codice potrebbe funzionare?
Code:
public void cammino(NodoMA start,NodoMA end)
        {
            if(isEmpty())
            {
                System.out.println("Grafo vuoto");
            }
            else
            {
                NodoL aux=nodi.getHead();
                for(;aux!=null;aux=aux.next)
                    ((NodoMA)aux.getInfo()).setStato(0);
                System.out.println("INIZIO cammino da "+start+" a "+end);
                ListaL lista=new ListaL();
                boolean cammino=stampaCammino(start,end,lista);
                lista.printList();
                if(lista.getSize()<=1)
                    System.out.println("FINE. Peso cammino: infinito");
                else
                    System.out.println("FINE. Peso cammino: ");

            }
        }
        public boolean stampaCammino(NodoMA n,NodoMA end,ListaL lista)
        {
            if(n.compareTo(end)==0)
            {
                lista.insertTail(n);
                return true;
            }
            if(n.getStato()==0)
            {
                lista.insertTail(n);
                n.setStato(1);
                NodoL aux=this.nodiAdiacenti(n).getHead();   //vado a prendere i nodiadiacenti a n e prendo la testa di questa lista
                for(;aux!=null;aux=aux.getNext())
                    if((stampaCammino((NodoMA)aux.getInfo(),end,lista)))  //se è vera tale istruzione, ritorno true esiste cammino
                    {
                       
                        return true;
                    }
                lista.deleteTail();
            }
            return false;
        }

Grazie
Logged
Pages: [1]   Go Up
Print
Jump to: