PDA

Visualizza la versione completa : Complessità algoritmo delle componenti connesse


LUCABORRELLI1
06-06-2008, 10:34
Ciao raga.Vi posto lo pseudo codice dell'algoritmo delle componenti connesse mi sapreste dier la complessità precisa??? non sono mai stato ferrato su ste cose se mi potete dare una mano vi ringrazio.Ciao



1. VAR Integer Matrice_label [N,N]
2. VAR Integer Immagine [N,N]
3. VAR Integer Label = 0
4. VAR Integer i,j = 0
5. VAR Integer Soglia

6. for i = 1… N
7. for j = 1… N
8. Matrice_label [ i , j ] = 0
9. end for
10. end for

11. for i = 1… N
12. for j = 1… N
13. if (Immagine [ i , j ] < Soglia)
14. if ( Matrice_label [ i-1 , j ] = 0 AND Matrice_label [ i , j-1 ] = 0 )
15. Label =Label + 1
16. Matrice_label [ i , j ] = Label
17. else
18. if ( Matrice_label [ i-1 , j ] != 0 )
19. Matrice_label [ i , j ] = Matrice_label [ i - 1 , j ]
20. if ( Matrice_label [ i , j-1 ] != 0 )
21. Matrice_label [ i , j ] = Matrice_label [ i , j - 1 ]
22. if ( Matrice_label [ i-1 , j ]!= 0 AND Matrice_label [ i , j-1 ]!= 0 )
23. Matrice_label [ i , j ] = Matrice_label [ i - 1 , j
24. classe_equivalenza( Matrice_label [ i - 1 , j ] , Matrice_label [ i , j - 1 ] )
25. end for
26. end for

27. for i = 1… N
28. for j = 1… N
29. aggiorna_equivalenze
30. end for
31. end for

Loading