[C] Problema sui grafi

[Qwertid]

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]

il grafo come è rappresentato? come lista di adiacenza o come matrice di adiacenza?

[Gandalf_BD]

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 è una breve spiegazione di cos'è una matrice di adiacenze, nel caso tu non lo sappia

[Qwertid]

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]

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]

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!!!