MST in Grafi Sparsi
Contrazione
Definizione
Una contrazione id un grafo non orientato
è un grafo tale che:
è una partizione di ; - Ciascuno dei sottografi di G indotti dagli insiemi di vertici
è connesso, - Per ogni coppia
con si ha:
MST-Reduce
Dato un grafo non orientato e connesso
- Un Grafo Contratto
con funzione peso , con partizione di V tale che - Una funzione
tale che: - Un insieme di archi
tale che:
Tali che:
Per ogni MST
Cioè, per ciascun
MST-Reduce: Implementazione
foreach (v in V[G]) do:
mark[v] = FALSE;
MAKE-SET(v);
foreach (u in V[G]) do:
if (mark[u] == FALSE) then:
scegli v in Adj[u] tale che w[u,v] è minimizzato
UNION(u,v);
T = T Unito-a {orig[u,v]};
mark[u] = mark[v] = TRUE;
V[G'] = {FIND-SET(v): v in V[G]};
E[G'] = EMPTY_SET;
foreach (x,y) in E[G] do:
u = FIND_SET(x);
v = FIND_SET(y);
if (u != v) then:
if ((u,v) !in E[G']) then:
E[G'] = E[G'] Unito-a {(u,v)};
orig'[u,v] = orig[x,y];
w'[u,v] = w[x,y];
else if (w[x,y]<w'[u,v]) then:
orig'[u,v] = orig[x,y];
w'[u,v] = w[x,y];
construct lista adiacenza Adj per G'
return (G', orig', w', T)
Complessità
wip