Lezione del 31/3/2010

La struttura Union-Find con foresta di alberi bilanciati: costo computazionale logaritmico delle due operazioni (si veda l'esercizio 3 del 2008-09-15). Esercizio: Un grafo pesato connesso e non diretto con pesi distinti ha un unico minimo albero coprente. Esercizio per casa: Dimostrare che il minimo albero coprente minimizza l'arco di costo massimo rispetto tutti gli alberi coprenti del grafo.


Descrizione python della struttura Union-Find con alberi:

class unionfind:
   def __init__(self, n):
      self.T = [-1]*n
      self.H = [0]*n
   
   def root(self, x):
      px = x
      while self.T[px] != -1:
         px = self.T[px]
      return px   
   
   def find(self, x, y):
      if self.root(x) == self.root(y):
         return True
      else:
         return False

   def union(self, x, y):
      px = self.root(x)
      py = self.root(y)

      if self.H[px] > self.H[py]:
         self.T[py] = px
      else:
         self.T[px] = py
         if self.H[px] == self.H[py]:
            self.H[px] = self.H[px] + 1

L'algoritmo di Kruskal modificato per utilizzare la nuova struttura

from union_find import *
from heapq import heappush, heappop


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

   UF = unionfind(n)

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