Lezione del 24/3/2010

L'algoritmo di Kruskal per il calcolo del minimo albero ricoprente: correttezza e complessita' di una implementazione ingenua. Verso una implementazione piu' efficiente: Struttura union-find con liste disgiunte. Costo computazionale di una sequenza di operazioni union.

Implementazione delle liste disgiunte in python:

from collections import deque

class elem:
   def __init__(self, nm):
      self.name = nm
      self.list = 0

class disjoinedlist:
   def __init__(self, e):
      self.L = deque()
      self.L.append(e)
      self.len = 1
      self.L[0].list = self
   
def find(x, y):
   if x.list == y.list:
      return True
   else:
      return False

def union(x, y):
   if x.list.len < y.list.len:
      shortest = x.list
      longest = y.list
   else:
      shortest = y.list
      longest = x.list

   for z in shortest.L:
      z.list = longest
      longest.L.append(z)

   shortest.L.clear()
   longest.len = longest.len + shortest.len