-
Notifications
You must be signed in to change notification settings - Fork 0
/
implement_encontrar_circuito_matriz.py
35 lines (29 loc) · 1.16 KB
/
implement_encontrar_circuito_matriz.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
33
34
35
def tem_circuito(v, grafo, estado, visitados):
estado[v] = "no_caminho"
# marcamos o vértice como "no_caminho".
visitados[v] = True
# marcamos o vértice como visitado.
for vizinho in grafo[v]:
# percorrendo os vizinhos de saida.
if estado[vizinho] == "no_caminho":
# se estiverem no caminho, entao encontramos um ciclo.
return True
# encontramos um ciclo.
if estado[vizinho] == "nao_atingido" and tem_circuito(vizinho, grafo, estado):
# aqui checando se nao foi atingido, e o chamado recursivo retorna verdadeiro.
return True
# se sim, tem circuito.
estado[v] = "finalizado"
# marcamos o vértice como "finalizado".
return False
def encontrar_circuito(grafo):
n = len(grafo)
estado = ["nao_atingido"] * n
# inicializamos todos os vértices como "nao_atingido".
visitados = [False] * n
# inicializamos todos os vértices como não visitados.
for v in range(n):
if estado[v] == "nao_atingido" and tem_circuito(v, grafo, estado, visitados):
return True
# tem circuito.
return False