-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs_m.py
32 lines (24 loc) · 943 Bytes
/
dfs_m.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from time import time
import sys
def dfs(graph, origem, destino, tempo_limite=10):
tempo_execucao = time()
pilha = [(origem, [origem], 0)]
visitados = set()
no_filho_exp = 0
no_expandidos = 0
while pilha:
no, caminho, profundidade = pilha.pop()
visitados.add(no)
if no == destino:
break
# if profundidade < limite_profundidade:
for dest, _ in graph[no]:
if dest not in visitados:
pilha.append((dest, caminho + [dest], profundidade + 1))
no_filho_exp += 1
no_expandidos = no_expandidos + 1
if (time() - tempo_execucao) > tempo_limite:
break
fator_ramificacao = no_filho_exp / no_expandidos if no_expandidos > 0 else 0
memoria_usada = sys.getsizeof(pilha) + sys.getsizeof(visitados)
return visitados, no_expandidos, memoria_usada, fator_ramificacao, (time() - tempo_execucao)