Lezione del 8/3/2010

Verifica della connessione di un grafo calcolando le potenze della matrice di adiacenza. Verifica della connettivita' utilizzando gli algoritmi di visita di un grafo. Codice python di un algoritmo di visita:

def visit(G):
   n = len(G)
   A = set()
   A.add(0)

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

   while len(A)>0:
      u = A.pop()
      X[u] = True
      for v in G[u]:
         if X[v] == False:
            T[v] = u
             A.add(v)
   return T

Il grafo G e' rappresentato come una lista (indicizzata) di liste di adiacenza. Per esempio

G = [[1,2,3,4], [0,2], [0,1,4], [0,4], [0,2,3]]

Il nodo 0 ha per vicini i nodi 1, 2, 3 e 4 e cosi' via.