PDA

View Full Version : [C] Problema sui grafi

Qwertid
15-12-2006, 18:49
Ciao a tutti!
Dovrei svolgere un problema sui grafi che consiste nel trovare tutti i vertici entranti in un certo nodo. Avevo pensato ad usare una visita tipo una BFS, ma non so dove mettere le mani... Come posso riuscire nell'impresa? Grazie :)
mostec
16-12-2006, 03:45
il grafo come è rappresentato? come lista di adiacenza o come matrice di adiacenza?
Gandalf_BD
16-12-2006, 11:57
rappresenta il grafo come matrice di adiacenze e poi, per ogni colonna, guardi quali celle sono a 1 (oppure per ogni riga, a seconda di come l'hai memorizzato).
questa (http://it.wikipedia.org/wiki/Matrice_delle_adiacenze) è una breve spiegazione di cos'è una matrice di adiacenze, nel caso tu non lo sappia :)
Qwertid
16-12-2006, 17:31
Il grafo è rappresentato mediante lista d'adiacenza, questo è il problema... Perciò penso si debba modificare un algoritmo di visita.. Pensavo alla DFS così da non dover costruire routine di gestione di una coda, indispensabili nella BFS
mostec
16-12-2006, 18:25
non serve tirare in ballo una ricerca tipo bfs o dfs..

se il grafo è non orientato il problema è banale.
se il grafo è orientato al momento non mi viene in mente niente di meglio che una ricerca in tutta la lista di adiacenza..
TempestaT400
17-12-2006, 05:17
la cosa non è difficile.. anzi..!..

Considerando un'implementazione a lista di adiacenza secondo me potresti strutturare un algoritmo in questo modo:


//il codice è java..

public int[] gradoEntrata(GrafoOrientato G){
int [] vettore = new int[G.n()];

//iterando sul grafo.. cioè scandendo ogni nodo
for(int i = 0; i<G.n(); i++)
{
vettore[i] = 0;

for(int j = 0; j<G.n(); j++)
if(G.esisteArco(j, i))
vettore[i]++;
}
return vettore;
}

/* piccole considerazioni....
G.n() ritorna il numero di nodi presenti nel grafo
G.esisteArco(j,i) controlla se nel grafo esiste un arco che parte da j e
finisce in i
Nel vettore ritornato hai il grado di entrata di ogni nodo...
*/


PS: nella struttura dati che ho implementato per me uso questo metodo...
poi non so... potresti sempre adattarlo!!!
Spero però di averti aiutato sul concetto almeno!!!