Lezione del 15/3/2010

Utilizzo di una coda nella visita: visita in ampiezza. Le proprieta' dell'albero di visita in ampiezza.

L'algoritmo di visita in ampiezza:

from collections import deque

def bfs(G,s):
   n = len(G)
   S = deque()
   S.append(s) # aggiunge un elemento alla fine della struttura

   X = [False]*n
   T = [-1]*n

   while len(S)>0:
      u = S.popleft() # estrae il primo elemento
      if X[u]== False:
         X[u] = True
         for v in G[u]:
            if X[v] == False and T[u] == -1:
               T[v] = u
                S.append(v)
   return T