disiodj

VISITEDIGRAFI_Esercizi

Jan 10th, 2016
262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //scrivi lo pseudocodice della procedura BFS nel caso in cui il grafo sia rappresentato tramite una matrice di adiacenza
  2.  
  3. BFS-MATRICE(A,v) -------------------Fatti corregere---------------------
  4. //color è un array di colori degli indici di A
  5. for i =0  to A.lenght-1
  6.     color[i] = 0;
  7. q = QUEUE-EMPTY()
  8. color[v][0] = 1
  9. ENQUEUE(q, v);
  10. for i =0 to A.lenght-1{
  11.     k = DEQUEUE(q);
  12.     for(j=0 to A.lenght-1){
  13.         if(A[k][j]==0)
  14.             color[k][j]=1
  15.             ENQUEUE(q,j)
  16.     }
  17.     color[k][0]=2
  18. }
  19. //Modifica per connected
  20. return color;
  21.  
  22.  
  23.  
  24.  
  25.  
  26. //scrivi lo pseudocodice della procedura IS-CONNECTED(A) che restituisce TRUE se il grafo è connesso
  27. Color = BFS(A, 1)
  28. for i=0 to A.lenght-1)
  29.     if(color[i]==0)
  30.         return FALSE
  31. return TRUE
  32.  
  33.  
  34.  
  35.  
  36. scrivi lo pseudocodice della procedura DISTANZA(A,v) che restituisce un array delle distanze di tutti i nodi dal nodo con indice v
  37. DISTANZA(A, v)
  38. for i =0  to A.lenght-1
  39.     color[i] = 0;
  40. q = QUEUE-EMPTY()
  41. color[v] = 1
  42. distanza[v]=0
  43. ENQUEUE(q, v);
  44. while Queue-not-empty
  45.     x = Dequeue(q)
  46.     k = x.key
  47.     if(k==0)
  48.         color[k] == 1
  49.         distanza[] = --------------------------finisci-------------------è come color--------------------
Add Comment
Please, Sign In to add comment