|
| Precedente :: Successivo |
| Autore |
Messaggio |
belledetta
Comune mortale
Registrato: 13/09/10 13:14
Messaggi: 3
|
 Inviato: 05 Ott 2010 19:04 Oggetto: [C] aiuto grafo pesato |
 |
|
ciao sto creando un programma che utilizzi la struttura di grafo pesato, sono una studentessa di matematica e non sono molto esperta. ho cercato qualcosa in rete e ho trovato delle assurde(nel senso di complicate) librerie utente...qualcuno può aiutarmi a capirle o meglio adattarle per fare il mio semplice(per voi) programma?
ho anke un piccolo codice implementato ma purtroppo e' in c++ e non so decifrarlo in c... così potrei tradurlo...
se qualcuno m aiuta posto i miei codici. in alternativa se qualcuno avesse delle librerie sulla gestione grafi già implimentate m farebbe un grandissimo favore.
grazie infinite. |
|
| Top |
|
 |
SverX
Supervisor Macchinisti
Registrato: 25/03/02 12:16
Messaggi: 11806
Residenza: Tokelau
|
| Inviato: 06 Ott 2010 10:35 Oggetto: |
|
|
la cosa migliore per imparare, a mio avviso, è scriversi da soli le librerie...
il grafo pesato è alla fine solo un grafo nel quale le relazioni tra i nodi sono dotate di un valore, che per semplicità puoi immaginare sia il 'costo' del percorrere la relazione, come ad esempio la distanza tra due città collegate da una strada.
tipicamente i grafi si implementano usando una lista multipla, in questo modo nella lista principale elenchi tutti i nodi e nelle sottoliste elenchi le relazioni con i nodi. ovviamente poi dovrai poi scrivere gli algoritmi di visita del grafo e -credo- anche quelli di ricerca dei percorsi più brevi... |
|
| Top |
|
|
belledetta
Comune mortale
Registrato: 13/09/10 13:14
Messaggi: 3
|
| Inviato: 06 Ott 2010 11:56 Oggetto: |
|
|
grazie...allora a quanto ho capito devo utilizzare delle liste ricorsive e concatenate anke se non le so ben usare.
cmq ha azzeccato il fine per cu devo creare il grafo...cioè la gestione di città con distanze. putroppo devo acquisire i dati input da file di questo genere...
4
AOSTA MILANO TORINO GENOVA
0 1 186
0 2 115
1 2 142
2 3 169
1 3 140
EOF
in questo caso creo una struttura grafo che ha
V come insieme d vertici
E insieme di archi
W insieme dei pesi (che è il codominio di una funzione)
quindi devo creare una struttura ad hoc per l'input e la modifica del file con immissioni di città archi o rimozioni. hai suggerimenti? |
|
| Top |
|
|
SverX
Supervisor Macchinisti
Registrato: 25/03/02 12:16
Messaggi: 11806
Residenza: Tokelau
|
| Inviato: 06 Ott 2010 13:57 Oggetto: |
|
|
| belledetta ha scritto: | | allora a quanto ho capito devo utilizzare delle liste ricorsive e concatenate anke se non le so ben usare. |
non sei obbligata a implementare il grafo con delle liste, ma secondo me è la soluzione più flessibile, e forse anche quello che ci si aspetta da uno studente (per contro si potrebbe implementare usando degli array e sarebbe più performante, ma sicuramente meno flessibile...)
| Citazione: | | hai suggerimenti? |
dal file indovino il formato... la prima riga indica il numero di nodi, la seconda i nomi dei nodi separati da uno spazio, le righe successive indicano il peso di ogni arco insistente sui due nodi di partenza e arrivo...
leggendo le prime 2 righe crei la lista dei nodi, e fino a qui è semplice.
poi per ogni riga successiva devi inserire nella lista degli archi di ognuno dei due nodi un elemento (arco) che punti all'altro. Attenzione che
ad esempio, è in realtà da duplicare in
perché (almeno credo che) gli archi non sono orientati...
in pratica fai una funzione
| Codice: | | creaArco (nodoDA, nodoA, peso) |
e poi la richiami due volte
| Codice: | creaArco (primo_nodo, secondo_nodo, peso)
creaArco (secondo_nodo, primo_nodo, peso) |
per gli algoritmi di ricerca dei percorsi dai una lettura a Wikipedia, ci sono buoni esempi... |
|
| Top |
|
|
belledetta
Comune mortale
Registrato: 13/09/10 13:14
Messaggi: 3
|
| Inviato: 07 Ott 2010 09:46 Oggetto: |
|
|
| Citazione: | | non sei obbligata a implementare il grafo con delle liste, ma secondo me è la soluzione più flessibile, e forse anche quello che ci si aspetta da uno studente (per contro si potrebbe implementare usando degli array e sarebbe più performante, ma sicuramente meno flessibile... |
purtroppo nel programma devo implementare 2 funzioni, di cui una carichi il file con liste di adiacenza(che sarebbero le liste ricorsive giusto?) e con una matrice di adiacenza (e ho delle domande da farti a proposito perchè non so se creare una matrice di dim massime e poi riempirla con i miei dati o se sia possibile creare una matrice dinamica che cresca o decresca in base ai dati del file)
dopo aver creato queste 2 letture devo creare delle funzioni creanodo, crea collegamento, eliminanodo, eliminacollegamento...
ti chiedo...queste funzioni dipendono dal modo in cui carico i dati??? cioè devo fare 2 funzioni per ogni rappresentazione???
| Citazione: | | dal file indovino il formato... la prima riga indica il numero di nodi, la seconda i nomi dei nodi separati da uno spazio, le righe successive indicano il peso di ogni arco insistente sui due nodi di partenza e arrivo.. |
un'ennesima domanda...come faccio a leggere gli archi se sono separati da spazio?? purtroppo non sono molto pratica e so effettuare solo una lettura sequenzia..
grazie mille |
|
| Top |
|
|
SverX
Supervisor Macchinisti
Registrato: 25/03/02 12:16
Messaggi: 11806
Residenza: Tokelau
|
| Inviato: 07 Ott 2010 12:41 Oggetto: |
 |
|
la lista di adiacenza è una lista dove ogni elemento rappresenta un arco che va dal nodo proprietario della lista intera al nodo indicato dall'elemento della lista, e di solito questa lista viene implementata utilizzando delle liste (scusa, la parola è la stessa ma il concetto nella prima parola è generico, nella seconda è specifico nel campo dell'informatica, vedi http://it.wikipedia.org/wiki/Lista_(informatica) )
la matrice di adiacenza è un altro modo per rappresentare le adiacenze: hai una tabella con tante righe e tante colonne quanti sono i nodi del grafo e nella tabella scrivi se i due nodi sono collegati, eventualmente anche il costo.
puoi creare delle matrici dinamiche, l'approccio puù semplice comunque è creare una matrice statica dopo avere definito un numero massimo di nodi gestibile (la matrice sarà quindi MAX_NODI x MAX_NODI)
poi le funzioni che creerai saranno diverse, ovviamente. Un set di funzioni lavorerà con le liste e un altro set con la matrice di adiacenza...
per la lettura dell'input formattato da file guarda fscanf()
 |
|
| Top |
|
|
|
|
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
