Lezione del 29/3/2010

Complessita' ammortizzata. Implementazione dell'algoritmo di Kruskal con struttura union-find implementata con liste disgiunte: complessita' dell'algoritmo.

from disjoined_list import *
from heapq import heappush, heappop


def kruskal(G):
   n = len(G)
   heap = []
   X = [-1]*n
   T = []
   for u in range(n):
      for v in G[u]:
         edge = v[0], u,  v[1] # peso, nodo, nodo
         heappush(heap, edge)
      X[u] = elem(u)
      disjoinedlist(X[u])

   while heap:
      edge = heappop(heap) 
      u, v, w = edge[1], edge[2], edge[0]
      if find(X[u], X[v]) == False:
         union(X[u], X[v])
         T.append((u,v))
   
   return T