Depth first search

#Recursiva
def DFS(grafo, n, work):
	work(v)
	for n in grafo.vecinos[v]
	DFS(grafo, n, work)

En este grafo:

Imprimiría:

ABDEGHIFC

Problema: podes tener stack overflow

Uso Stacks(1.0)

def DFS(grafo, v, work):
	Pila = Pila()
	Pila.apilar(v)
	while not pila.vacia():
		v = pila.desapilar()
		work(v)
		for n in grafo.vecinos[v]:
			pila.apilar(n)

• Es lo mismo si imprime primero izquierda o derecha
• VER ABAJO

Puede haber un ciclo que haga que no se termine el stack

Stacks con ciclos

def DFS(grafo, v, work):
	visitados = {}
	Pila = Pila()
	Pila.apilar(v)
	visitados.add(v)
	while not pila.vacia():
		v = pila.desapilar()
		work(v)
		for n in grafo.vecinos[v]:
			if n not in visitados:
				pila.apilar(n)
				visitados.add(n)

Visitados es O(#V) en memoria

Definiciones

b: Branching factor

El grado de salida promedio (cuántas aristas salen en promedio de un vértice del grafo)

d: Profundidad máxima de el vértice inicial al más lejano

Entonces la función DFS definida arriba (la anteúltima) tiene orden O(b.d)

(el recursivo también)