[c] come trovare un albero che collega due vertici di un grafo

[noblex]

ciao, per domani devo consegnare un progetto che non riesco a finire,gestisce un areoporto
la parte che già ho fatto è riempire una matrice delle adiacenze che conta tutti i voli da a ogni città, fatta in questo modo (1 c'è il volo, 0 non c'è
_______R.____T.____M.____L.
_
roma___0_____1____1_____0
_
torino___1____0_____0_____0
_
milano__0_____1____0_____1
_
londra__1_____1____0_____0
_
spero abbiate capito, in pratica l'utente scrive dove vuole partire, dove deve arrivare, e il programma gli dice se esiste il volo, se e quanti deve scali deve fare... chi mi da una mano?

[wingman87]

Devi trovare un cammino, non un albero. Prova a vedere l'algoritmo di Dijkstra

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

[clockover]

Originariamente inviato da wingman87

Devi trovare un cammino, non un albero. Prova a vedere l'algoritmo di Dijkstra

http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra

Ma l'algoritmo di Djkstra non richiede che ogni arco abbia un peso? Questo perchè Djkstra trova i cammini minimi... certo che se hanno un peso va bene lo stesso...
Se invece sono gli archi sono semplici basta anche una DFS o BFS

[noblex]

si gli archi hanno 2 pesi, durata del viaggio e costo, infatti la matrice creata non è semplicemente di int, ma di strutture contententi un int 1-0 per sapere se l'arco c'è, e poi i due valori..

[clockover]

Se hai bisogno di trovare il percorso più breve va bene Djkstra, altrimenti basta una semplice visita in ampiezza o in profondità

[noblex]

Originariamente inviato da clockover

Se hai bisogno di trovare il percorso più breve va bene Djkstra, altrimenti basta una semplice visita in ampiezza o in profondità

daccordo su tutto tranne che sul "semplice"

[clockover]

Una visita in profondità ricorsiva è davvero facile fidati. Devi solo cercare un barbatrucco per segnare i nodi già visitati.

[noblex]

Originariamente inviato da clockover

Una visita in profondità ricorsiva è davvero facile fidati. Devi solo cercare un barbatrucco per segnare i nodi già visitati.

ahah al tempo eh, io sono un modesto studente, la ricorsione mi fa ancora cristonare

mi dite grosso modo come dovrei fare nel mio caso? (non il codice, solo l'algoritmo)

[clockover]

Ricorsivamente io farei così:

1) controllo tutti i nodi adiacenti se qualcuno è uguale alla destinazione
2) se non è nessuno di questi allora per ognuno di questi nodi adiacenti richiamo lo stesso metodo (chiamata ricorsiva)

Ti conviene usare una pila per tenere conto dei passi fatti.. ovviamente dipende tutto dalla struttura dati che usi per rappresentare il grafo

[noblex]

il mio professore mi ha passato il codice della dfs.. ma non ci ho capito una mazza

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).

[clockover]

A te non server il codice.. a te serve capire come funziona quel codice dato che l'algoritmo è uguale, la ma sua realizzazione è vincolata dal modo in cui realizzi la struttura del grafo (matrice delle adiacenze, lista delle adiacenze, ecc..)...
e poi indenta il codice