Lezione del 10/3/2010

Correttezza dell'algoritmo di visita: Tutti i nodi della componente connessa C a cui appartiene il nodo di partenza sono visitati; T e' un albero i cui nodi sono quelli della componente connessa C. Implementazione della visita che utilizza una coda pila come insieme di appoggio: complessita' computazionale; visita in profondita'.

Codice python della visita in profondita'.

from collections import deque

def dfs(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.pop() # estrae l'ultimo elemento inserito
      X[u] = True
      for v in G[u]:
         if X[v] == False:
            T[v] = u
             S.append(v)
   return T