il mio professore mi ha passato il codice della dfs.. ma non ci ho capito una mazza :D
void bfs(Graph G, Edge e)
{ int v, w;
QUEUEput(e);
pre[e.w] = cnt++;
while (!QUEUEempty())
{
e = QUEUEget();
w = e.w;
st[e.w] = e.v;
for (v = 0; v < G->V; v++)
if ((G->adj[e.w][v] == 1) && (pre[v] == -1))
{
QUEUEput(EDGE(e.w, v));
pre[v] = cnt++;
}
}
}
questo è il mio programma fino alla parte di ricerca, come potrei implementarlo?
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 50
typedef struct voli{
int p;
int prezzo;
float durata;
}voli;
int trovavolo(voli **v, int tot, char **city);
int dijkstra(voli **v, int par, int arr, int tot);
int main()
{
int i,j,k=0, prov, cmp, indice, ctrl, pr, kk, jj;
float du;
int totc;
voli **v;
char *citt[max], nome[max], c1[max], c2[max];
FILE *input;
printf("inserire il nome del file di input");
scanf("%s", nome);
input=fopen(nome, "r");
fscanf(input, "%d", &totc);
for(i=0;i<totc;i++)
{
citt[i]=(char*)malloc(totc*sizeof(char));
}
v=(voli**)malloc(totc*sizeof(voli*));
for(i=0;i<totc;i++)
{
v[i]=(voli*)malloc(totc*sizeof(voli));
}
for(i=0;i<totc;i++)
{
for(j=0;j<totc;j++)
{
v[i][j].p=0;
v[i][j].prezzo=0;
v[i][j].durata=0;
}
}
indice=0;
while(!feof(input))
{
fscanf(input, "%d", &prov);
for(i=0;i<prov;i++)
{
for(j=0;j<totc;j++)
{
fscanf(input, "%s %s %*d %*f", c1, c2);
ctrl=0;
for(k=0;k<totc;k++)
{
cmp=strcmp(c1, citt[k]);
if(cmp==0)
{
ctrl=1;
break;
}
}
if (ctrl==0)
{
strcpy(citt[indice], c1);
indice++;
}
ctrl=0;
for(k=0;k<totc;k++)
{
cmp=strcmp(c2, citt[k]);
if(cmp==0)
{
ctrl=1;
break;
}
}
if (ctrl==0)
{
strcpy(citt[indice], c2);
indice++;
}
}
}
}
fclose(input);
input=fopen(nome, "r");
fscanf(input, "%*d");
while(!feof(input))
{
fscanf(input, "%d", &prov);
for(i=0;i<prov;i++)
{
fscanf(input, "%s %s %d %f", c1, c2, &pr, &du);
for(j=0;j<totc;j++)
{
cmp=strcmp(c1, citt[j]);
if(cmp==0)
{
jj=j;
for(k=0;k<totc;k++)
{
cmp=strcmp(c2, citt[k]);
if(cmp==0)
{
kk=k;
v[jj][kk].p=1;
v[jj][kk].prezzo=pr;
v[jj][kk].durata=du;
}
}
}
}
}
}
//stampo la maatrice di adiacenza
for(i=0;i<totc;i++)
{
for(j=0;j<totc;j++)
{
printf("%d ", v[i][j].p);
}
printf("\n");
}
trovavolo(v, totc, citt);
return 0;
}
int trovavolo(voli **v, int tot, char **city)
{
int i, j, cmp, ctrl, ii, jj;
char c1[max], c2[max];
printf("inserire citta' di partenza\n");
scanf("%s", c1);
printf("inserire citta' di arrivo\n");
scanf("%s", c2);
for(i=0;i<tot;i++)
{
cmp=strcmp(c1, city[i]);
if(cmp==0)
{
ii=i;
ctrl=1;
}
}
if(ctrl!=1)
{
printf("volo non trovato\n");
return 1;
}
for(j=0;j<tot;j++)
{
cmp=strcmp(c2, city[2]);
if(cmp==0)
{
jj=j;
ctrl=1;
}
}
if(ctrl!=1)
{
printf("volo non trovato\n");
return 1;
}
if (v[ii][jj].p==1)
{
printf("il volo costa %d e ha una durata di %f", v[ii][jj].prezzo, v[ii][jj].durata);
return 1;
}
else
{
dijkstra(v, ii, jj, tot);
}
return 1;
}
int dijkstra(voli **v, int par, int arr, int tot)
{
return 1;
}
ah certo, questa era la consegna
acquisizione e visita di un grafo.
È dato un file contenente un elenco di voli aerei, secondo il formato seguente:
la prima riga contiene il numero totale NC delle città (aeroporti di partenza o arrivo dei voli);
le righe successive contengono l’elenco dei voli, in ragione di uno per riga, secondo il formato:
<partenza> <arrivo> <costo> <durata>
essendo <partenza>, <arrivo>, <costo> e <durata> la città di partenza, la città di arrivo, il costo in euro (intero) e la durata in ore (reale) del volo, rispettivamente.
I voli sono ordinati secondo città di partenza (in ordine alfabetico crescente). Inoltre, prima di ogni gruppo di voli in partenza dalla stessa città, il file contiene una riga indicante il numero totale di questi voli. Si supponga, infine, che i nomi delle città siano delle stringhe di lunghezza massima pa-ri a 20 caratteri e non contengano spazi.
Un possibile esempio di contenuto del file è il seguente:
7
2
Londra Francoforte 220 1.5
Londra Milano 280 2.5
2
Milano Londra 250 2.2
Milano NewYork 950 12.4
2
NewYork Londra 820 8.2
NewYork Parigi 900 9.0
1
Parigi Milano 230 2.1
3
Roma Francoforte 300 2.8
Roma Londra 400 3.5
Roma Parigi 350 2.6
2
Torino Milano 200 0.5
Torino Roma 150 1.5
Si scriva un programma in linguaggio C che legga il file in ingresso e memorizzi le informazioni in esso contenute come grafo (si rappresenti il grafo tramite matrice di adiacenza, oppure tramite liste di adiacenza).
Una volta memorizzato il grafo, il programma acquisisca da input il nome di una città C, e stampi a video l’elenco di tutte le città che è possibile raggiungere da C (direttamente e/o indirettamente). Si proponga una soluzione che effettui sia una visita in ampiezza che una visita in profondità.
Il programma, infine, verifichi se nel grafo acquisito sia presente, oppure no, almeno un ciclo.
VINCOLI E RESTRIZIONI
Indipendentemente dalla rappresentazione scelta (matrice/liste di adiacenza), è OBBLIGATORIO costruire ogni arco del grafo in maniera tale da avere un accesso diretto dalla città di partenza alla città di arrivo collegate dal volo in considerazione. Si noti che questo vuol dire, in particolare, che le stringhe per i nomi delle città (di partenza e/o arrivo) NON devono essere duplicate e che, inoltre, durante l’esecuzione dell’algoritmo di visita del grafo NON deve essere eseguita nessuna ricerca sulle città (ad eccezione della prima, per determinare il vertice corrispondente alla città C).