[c] pseudo codice bfs con matrice delle adiacenze

[noblex]

data una matrice v[i][i] che contiene 1 o 0 se è presente l'arco in un grafo di i nodi, orientato, qualcuno sarebbe così gentile da darmi lo pseudo codice della dfs? perchè l'ho trovato solo con le liste, e non riesco a farmelo da me
esit nel titolo ho scrigtto bfs, ma intendevo la dfs

[starfred]

Sinceramente non ho capito la corrispondenza tra la matrice e gli archi. Io ho intuito, ma potrei tranquillamente sbagliarmi, che il primo indice della matrice rappresenta l'id nodo di partenza ed il secondo indice l'id del nodo di arrivo.
Esempio:
v[7][4]=1 indica che è presente un arco orientato dal nodo 7->4

E' esatto?

[noblex]

Originariamente inviato da starfred

Sinceramente non ho capito la corrispondenza tra la matrice e gli archi. Io ho intuito, ma potrei tranquillamente sbagliarmi, che il primo indice della matrice rappresenta l'id nodo di partenza ed il secondo indice l'id del nodo di arrivo.
Esempio:
v[7][4]=1 indica che è presente un arco orientato dal nodo 7->4

E' esatto?

si è esatto

esempio:
_______T.___M.___R.
torino__0____1____0
_
milano__0____0____1
_
roma___1____1____0

tu da torino puoi andare solo a milano, da milano solo a roma e da roma puoi andare sia a torino che a milano, ovviamente la diagonale della matrice è tutti 0 perchè da torino non c'è un arco che porta a se stesso

[__ZERO_UNO__]

Concettualmente lista e matrice di adiacenza sono la stessa cosa. La lista di adiacenza la puoi vedere come una matrice dove sono memorizzati fisicamente solo le celle utilizzare. Se in una matrice vuoi identificare la lista di adiacenza di un nodo v, rispetto agl'archi uscenti da v, andrai semplicemente a prendere tutta la v-esima riga o colonna, è uguale.

Quindi, se propio non vuoi sfogliare un bel manuale di strutture dati e algoritmi prova con Wikipedia.

[noblex]

Originariamente inviato da __ZERO_UNO__

Quindi, se propio non vuoi sfogliare un bel manuale di strutture dati e algoritmi prova con Wikipedia.

non colgo l'ironia... comunque un manuale non ce l'ho. ho solo delle slide ma da li non l'ho capito.. se non hai voglia di aiutarmi e pensi che venga a cercare la pappa pronta puoi evitare di rispondere

[__ZERO_UNO__]

Non voglio entrare in polemica ma non è ironia. Trovo buffo il fatto che pensi di trovare una migliore spiegazione su un forum che in un libro apposito che non hai ancora provato a sfogliare, la cui prima spiegazione che mi sovviene è pigrizia. Volevo spronarti a farlo. Però posso sbagliare come ogni essere umano.

[noblex]

ma no ma no! se era pigrizia non mi iscrivevo al poli! è tasche vuole semmai!
ho delle slide e gli appunti, e su 1000mila cose questa (e non solo) non mi viene proprio, così ho chiesto qui

[starfred]

Ammesso che la matrice non sia ciclica per la dfs procederei così:

1) trova una colonna nulla, il suo indice sarà l'indice del rigo di partenza
2)

fun (vettore[], ind_riga){
   for (int next_node=0; i<N; next_node++)
if (vettore[ind_riga][next_node]==1) fun(next_node)
return "nodo ind_riga visitato"}

Questa soluzione visita può visitare più volte la stessa leaf a seconda del tipo di grafo.