| Autore |
 Discussione  |
|
|
jhix
Utente giovane
Regione: Puglia
Prov.: Bari
|
 Inserito il - 14/12/2007 : 15:04:04
|
Scusate ho un dubbio sui grafi.
i grafi non hanno un ingresso particolare, giusto?
bisogna, tramite un nodo, continuare l'esplorazione, giusto?
ma allora come posso passare ad una funzione solo un grafo senza alcun nodo di partenza?
vi prego risp.
|
|
|
noname
Utente medio
Regione: Puglia
Prov.: Bari
Città: Città dell'Ammmore
|
Inserito il - 14/12/2007 : 19:07:05
|
I grafi non hanno un ingresso particolare, giustissimo.
Quando tramite un nodo devi proseguire l'esplorazione, devi passare ai nodi adiacenti. A questi ci passi controllando la matrice di adiacenza, oppure le liste di adiacenza a seconda della realizzazione.
Perchè alla funzione devi passare solo il grafo?
Se devi fare una funzione di ricerca (stai facendo l'ultimo esonero di lab? :) ) hai bisogno del grafo da esplorare, il nodo da cercare e ovviamente un nodo da cui partire.
In un grafo ogni nodo è identificato dall'etichetta, ovvero dal valore contenuto nel nodo. E anche nel caso in cui i nodi non hanno etichetta, li puoi identificare da qualcosa, tipo la posizione nel vettore, o l'indirizzo.
Quindi se devi cercare il nodo 4, devi cercare il nodo che contiene il valore 4. Infatti il grafo è un insieme di nodi, e un insieme di archi. E in un insieme non ci sono valori duplicati.
Se stai facendo l'esonero, hai pure il nodo da cui partire: la radice.
In teoria se devi esplorare tutto il grafo, dovresti farlo da ogni nodo o al massimo non da quelli che raggiungi a partire dal primo nodo. Infatti se hai un grafo non connesso non raggiungerai mai partendo da un nodo di una parte, i nodi della parte separata.
Se hai un grafo orientato, vale la stessa cosa anche se è connesso, a causa dei versi degli archi.
Per cui se devi esplorare il grafo per trovare un cammino da un nodo di partenza ad un altro, ok, ti muovi sui nodi adiacenti, li marchi e se non trovi il cammino amen.
Se invece devi esplorare velocemente tutti i nodi, magari per controllare che non ci sono duplicati, ti conviene mantenere una lista di nodi, che puoi scorrere senza badare alle adiacenze. Insomma una vera e propria lista.
Un saluto!
P.S.: spero di aver capito bene i grafi, altrimenti potrei aver scritto caz....
|
 |
|
|
DartFener
Utente medio
Regione: Estero
Prov.: Estero
Città: Flatulandia
|
Inserito il - 15/12/2007 : 09:12:23
|
Citazione:
Messaggio inserito da noname
Se invece devi esplorare velocemente tutti i nodi, magari per controllare che non ci sono duplicati, ti conviene mantenere una lista di nodi, che puoi scorrere senza badare alle adiacenze. Insomma una vera e propria lista.
Tutte le realizzazioni dei grafi prevedono un elenco dei nodi contenuto, o in un vettore, o in una lista dinamica. E non puoi scorrerle da funzioni esterne alla realizzazione.
Per jhix, se la funzione è esterna alla dichiarazione della classe grafo, bisogna passare, ovviamente, un oggetto di tipo grafo (o una funzione che restituisce un oggetto di tipo grafo).
Ricordate che le funzioni che non fanno parte della dichiarazione della classe non devono vedere la realizzazione perchè devono funzionare per qualsiasi realizzazione venga utilizzata per creare la classe.
Per utilizzare un grafo ti serve un nodo di partenza e, se non lo passi alla funzione, allora deve essere questa a creare un valore che sia un nodo. Ma tutto dipende da che cosa deve fare questa funzione... |
Giocate al browsergame che sto aiutando a sviluppare: NoirGame
Visitate il mio blog!
Date un'occhiata e diffondete per favore: 11 settembre
FORZA INTER facciamo 5!
Se siete bloccati in un qualsiasi gioco per una qualsiasi consolle e conoscete l'inglese cliccate qui
___
 |
|
|
|
noname
Utente medio
Regione: Puglia
Prov.: Bari
Città: Città dell'Ammmore
|
Inserito il - 15/12/2007 : 10:41:30
|
Citazione:
Messaggio inserito da DartFener
Tutte le realizzazioni dei grafi prevedono un elenco dei nodi contenuto, o in un vettore, o in una lista dinamica. E non puoi scorrerle da funzioni esterne alla realizzazione.
Giustissimo, non ho specificato che la lista deve essere usata internamente al grafo.
Parlando di realizzazioni mi sorge un dubbio.
Si dice che le varie realizzazioni devono implementare le stesse interfacce, date dalle specifiche.
Ora, se io realizzo un grafo con liste dinamiche di adiacenza, mi troverò a lavorare con puntatori a nodi quindi nodo=puntatore a nodo.
Se lo realizzo con matrici di adiacenza il nodo non sarà un puntatore a nodo ma un intero.
Quindi tra le due realizzazioni, anche se le chiamate sono le stesse, le firme dei metodi cambiano.
Sto sbagliando qualcosa?
A voi a che livello arriva l'interscambiabilità delle realizzazioni?
Se a me per la lista, bastava cambiare il file d'include, per passare tra due realizzazioni senza modificare algoritmi esterni, con i grafi non è più così...
|
|
|
|
genius
dott. ing. cav. ...FN
Regione: Puglia
Prov.: Bari
Città: Molfetta - Caput Mundi
|
Inserito il - 15/12/2007 : 10:58:01
|
| In teoria dovresti usare come tipo di dato "nodo"... quindi se in un algoritmo usi questo piuttosto ke puntatori o interi, dovresti avere l'astrazione ke ti serve... |
"...e se non hai morale
e se non hai passione
se nessun dubbio ti assale
perché la sola ragione che ti interessa avere
è una ragione sociale
soprattutto se hai qualche dannata guerra da fare
non farla nel mio nome
non farla nel mio nome
che non hai mai domandato la mia autorizzazione
se ti difenderai non farlo nel mio nome
che non hai mai domandato la mia opinione..."
Un blog farlocco |
|
|
|
noname
Utente medio
Regione: Puglia
Prov.: Bari
Città: Città dell'Ammmore
|
Inserito il - 15/12/2007 : 11:23:44
|
Si questa è una soluzione.
Ma ora leggendo il Bertossi trovo scritto:
"nelle realizzazioni che verranno proposte si supporà che gli n nodi siano individuati da numeri compresi tra 1 e n"
Quindi i nodi sono identificati da numeri da 1 a n!
E quindi anche nella realizzazione a puntatori!
Ora mi è tutto più chiaro, mi era sfuggito questo particolare!
Il nodo nella versione a puntatori è comunque identificato da un numero, quindi nelle firme il nodo è sempre il nodo numero n e non un puntatore.
Dunque i puntatori li uso solo internamente per la memorizzazione di celle che hanno un campo n = numero_nodo che lo identifica.
|
|
|
|
boom2112
Utente medio
Regione: Puglia
Prov.: Bari
Città: Molfetta
|
Inserito il - 15/12/2007 : 16:33:28
|
| scusatemi ragazzi ma avendo le specifiche dei grafi come ha detto il prof non e possibile sapere a che nodo appartiene l'etichetta che viene passata quindi possiamo anche ampliare le specifiche mettendo una operazione che dato in input un tipoelem mi dia il nodo a cui corrisponde??? |
AlartZero deve morire il prima possibile...mandato nella perfida Albione |
|
|
|
noname
Utente medio
Regione: Puglia
Prov.: Bari
Città: Città dell'Ammmore
|
Inserito il - 15/12/2007 : 20:41:50
|
Mah, credo che se comunque realizzi le funzioni delle specifiche, puoi aggiungere qualche altra funzione. Non credo che il sommo si incavoli.
Oppure la realizzi come funzione esterna.
Occhio però, ci possono essere più nodi con la stessa etichetta...
|
|
|
|
jhix
Utente giovane
Regione: Puglia
Prov.: Bari
|
Inserito il - 16/12/2007 : 10:38:40
|
grazie mi siete stati molto utili. cmq risp a l'ultima domanda:
se stai facendo l'esonero dovresti partire dalla radice e trovare il nodo in cui, come etichetta trovi il valore passato, io sto facendo cosi.
ciao |
|
|
|
boom2112
Utente medio
Regione: Puglia
Prov.: Bari
Città: Molfetta
|
Inserito il - 16/12/2007 : 11:01:41
|
| si si infatti e proprio quello che sto facendo pure io. |
AlartZero deve morire il prima possibile...mandato nella perfida Albione |
|
|
| |
Discussione |
|
Dubbio sui grafi
