Arbol de Expansion, en Python

[Lisandro Dalcin]

En el archivo anexado tienen dos ejemplos para grafos tomados del libro.

def depth_first(G, r):
"Arbol de Expansion - Busqueda en Profundidad"
def visit(G, v, T):
for w in G[v]:
if w not in T:
T[w] = [v]
T[v].append(w)
T = {r: []}
visit(G, r, T)
return T

def breadth_first(G, r):
"Arbol de Expansion - Busqueda a lo Ancho"
T = {r: []}
L = [r]
while L:
v = L.pop(0)
for w in G[v]:
if w not in T and w not in L:
L.append(w)
T[w] = [v]
T[v].append(w)
return T

--
Lisandro Dalcin
---------------
CIMEC (INTEC/CONICET-UNL)
Predio CONICET-Santa Fe
Colectora RN 168 Km 472, Paraje El Pozo
Tel: +54-342-4511594 (ext 1011)
Tel/Fax: +54-342-4511169