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
martedì 30 marzo 2010
Lezione del 29/3/2010
Complessita' ammortizzata. Implementazione dell'algoritmo di Kruskal con struttura union-find implementata con liste disgiunte: complessita' dell'algoritmo.
mercoledì 24 marzo 2010
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:
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
martedì 23 marzo 2010
Lezione del 22/3/2010
Il problema del minimo albero coprente (MST): perturbare i pesi degli archi in modo che questi risultino tutti distinti e l'MST dell'istanza perturbata sia un MST dell'istanza originale; regola del taglio e regola del ciclo.
giovedì 18 marzo 2010
Lezione del 17/3/2010
Esercizio: I grafi a torneo sono Hamiltoniani. Algoritmo per la verifica della forte connessione di un grafo diretto: si veda l'esercizio 3 della prova scritta del 10/6/2008.
martedì 16 marzo 2010
Lezione del 15/3/2010
Utilizzo di una coda nella visita: visita in ampiezza. Le proprieta' dell'albero di visita in ampiezza.
L'algoritmo di visita in ampiezza:
L'algoritmo di visita in ampiezza:
from collections import deque
def bfs(G,s):
n = len(G)
S = deque()
S.append(s) # aggiunge un elemento alla fine della struttura
X = [False]*n
T = [-1]*n
while len(S)>0:
u = S.popleft() # estrae il primo elemento
if X[u]== False:
X[u] = True
for v in G[u]:
if X[v] == False and T[u] == -1:
T[v] = u
S.append(v)
return T
giovedì 11 marzo 2010
Lezione del 10/3/2010
Correttezza dell'algoritmo di visita: Tutti i nodi della componente connessa C a cui appartiene il nodo di partenza sono visitati; T e' un albero i cui nodi sono quelli della componente connessa C. Implementazione della visita che utilizza una coda pila come insieme di appoggio: complessita' computazionale; visita in profondita'.
Codice python della visita in profondita'.
Codice python della visita in profondita'.
from collections import deque
def dfs(G, s):
n = len(G)
S = deque()
S.append(s) # aggiunge un elemento alla fine della struttura
X = [False]*n
T = [-1]*n
while len(S)>0:
u = S.pop() # estrae l'ultimo elemento inserito
X[u] = True
for v in G[u]:
if X[v] == False:
T[v] = u
S.append(v)
return T
martedì 9 marzo 2010
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:
Il grafo G e' rappresentato come una lista (indicizzata) di liste di adiacenza. Per esempio
Il nodo 0 ha per vicini i nodi 1, 2, 3 e 4 e cosi' via.
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.
giovedì 4 marzo 2010
mercoledì 3 marzo 2010
Lezione del 3/3/2010
Operatori su grafi; Rappresentazione dei grafi con lista di archi, liste di adiacenza e matrice di adiacenza; Complessita' computazionale degli operatori nelle tre rappresentazioni; Esercizi sulle proprieta' dei grafi: un grafo connesso di n nodi ha almeno n-1 archi; un grafo aciclico di n nodi ha massimo n-1 archi; un albero di n nodi ha n-1 archi; Il quadrato della matrice di adiacenza di un grafo rappresenta cammini di lunghezza due: come estendere il risultato.
martedì 2 marzo 2010
Lezione del 1/3/2010 (Prima lezione a.a. 2009-2010)
Concetti e definizioni preliminari sui grafi: grafi diretti e non diretti; vicinato di un nodo; cammini e cicli; grafi pesati; connettivita' e componenti connessi.
Iscriviti a:
Post (Atom)