Grafo Pesato Java!

di
ilgattonero1921
il
3 risposte
I
ilgattonero1921
Pochi posts
Iscritto da
giu, 2020
Messaggi:
2

Grafo Pesato Java!

Salve, sto cercando di risolvere un compito di Algortmi del mio corso. Ma non riesco a risolvere un punto dell'esame. Mi potreste dare un piccolo aiuto?
Si vuole rappresentare una rete di trasporto che collega diversi punti di interesse di una metropoli. Ogni punto di interesse è individuato da una denominazione e un indirizzo (via e numero civico), e ha associate alcune informazioni quali, la lista delle attrazioni turistiche limitrofe, la lista degli uffici pubblici limitrofi, la presenza di un info point turistico, la presenza di un parcheggio taxi.
Tra i punti di interesse possono esistere collegamenti diretti. Vi sono due tipi di collegamenti: autobus e metropolitana. Sia assume che tra due punti di interesse può esistere al massimo un collegamento diretto.
Due punti di interesse A e B si dicono connessi ad alta velocità, se esiste un percorso che li collega che attraversa solo collegamenti di tipo metropolitana.
Si rappresenti la situazione sopra descritta, supposta a regime (il candidato non si deve occupare quindi dell’inizializzazione). Il candidato deve, inoltre, implementare i seguenti metodi e valutarne la complessità computazionale:
Dalla traccia ho creato una classe "Punto" con all'interno i valori sopra indicati. Il Grafo è Diretto,Pesato e Sparso. Però mi sorge il dubbio su come creare la classe per il peso degli archi e per il seguente metodo:
metodo connessiAV, che riceve due punti di interesse A e B e restituisce true se i due punti di interesse sono connessi ad alta velocità, false altrimenti.
Io sono arrivato a questo punto ma suppongo che non sia totalmente corretto.
[CODE=java]public boolean m3(String a, String b){ boolean esito = false; DirectedWeightedSparse<Punto,Peso> = g.clone(); for(String c : g.clone()){ }

3 Risposte

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21552

    Re: Grafo Pesato Java!

    E g cosa è?
  • I
    ilgattonero1921
    Pochi posts
    Iscritto da
    giu, 2020
    Messaggi:
    2

    Re: Grafo Pesato Java!

    Sta per il grafo originale che è un DirectedWeightedSparseGraph. Sinceramente pensandoci credo che sia giusto usare Dijkstra. Ma sinceramente non capisco come distinguere la ricerca tra autobus e metropolitana.
  • Sh3dir
    Sh3dir
    Pochi posts
    Iscritto da
    lug, 2020
    Messaggi:
    41

    Re: Grafo Pesato Java!

    Purtroppo temo di non aver ben inteso la tua traccia.
    Ciò che ho inteso è che esistono soltanto due pesi per gli archi, che rispecchiano il fatto che sia un collegamento di tipo metropolitana o autobus.
    La classe arco potresti farla così: 
    
public class Arco{
     private byte peso;
     private Punto p_arrivo;

     public Arco (Punto destinazione, byte peso){
          p_arrivo = destinazione;
          this.peso = peso;
     }
     //più i getter necessari
}
    Ed all'interno della classe Punto avere una lista di questi archi USCENTI. 
    
public class Punto{
    LinkedList<Arco> archiUscenti = new LinkedList<Arco>();
    ...
    ...   
    ...
    public LinkedList<Arco> getArchi(){  return archiUscenti;  } 
 
}
    A questo punto il metodo "connessiAV" sarebbe un qualsiasi algoritmo di ricerca di un percorso in un grafo tra due punti, considerando però soltanto gli archi di tipo metropolitano. Se questo percorso esiste ritorna true, false altrimenti.
Devi accedere o registrarti per scrivere nel forum
3 risposte