PDA

Visualizza la versione completa : problemi con algoritmo sui grafi


karlagpm
08-04-2004, 18:17
ciao, ho un po di casini con questo algoritmo:

considera un grafo orientato G=(V,E) con vertici V={1,2,3,...n}, e archi specificati dalla matrice nn A[i,j], tale che A[i,j]=1 se (i,j)∈ E o 0 altrimenti.


problema: calcola il numero di tutti i percorsi di lunghezza 3 all'interno del grafo.

pensavo di usare l'algoritmo di chiusura transitiva ma non sono certo che sia giusto. qualcuno sa darmi qualche consiglio??

anx721
08-04-2004, 19:06
Un modo semplice che mi viene in mente di fare 4 cicli for con 4 indici interi da 1 a n: i, j, h, k; per ogni quadrupla i, j, h, k (i va da 1 a n - 2; j da i + 1 a n - 1; k da j + 1 a n, e in piu controlli anche per k = i per considerare i cicli) verifichi se (i, j), (j, h) e (h, k) sono archi del grafo; se questo il caso aggiungi la quadrupla ad una lista, per indicare un nuovo cammino di tre archi.

Loading