dfs com visitados aspirador

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

from collections import deque #Utilizado para formar uma pilha inevertida
dic = {0: 'Esquerdo_E-Sujo_D-Sujo', 1: 'Direito_E-Sujo_D-Sujo', 2: 'Esquerdo_E-Sujo_D-Limpo', 3: 'Direito_E-Sujo_D-Limpo',
 4: 'Esquerdo_E-Limpo_D-Sujo', 5: 'Direito_E-Limpo_D-Sujo', 6: 'Esquerdo_E-Limpo_D-Limpo', 7: 'Direiro_E-Limpo_D-Limpo'}
# Classe para montar a matriz de adjacencia, expandir fronteira, da origem ao destino
class Grafo:
 def __init__(self, vertices):
 self.vertices = vertices
 # Cria uma matriz por verticesXvertices com eleementos zeros
 self.grafo = [[0] * vertices for i in range(vertices)]
 # Cria uma lista com vertices elementos não visitados (False)
 self.visitados = [False] * vertices
 self.borda = deque()
 self.caminho = deque()
 self.node = deque()
 self.node_final = []
 # Adiciona elementos 1 para vertices que fazem fronteira
 def add_aresta(self, u, v):
 self.grafo[u][v] = 1
 self.grafo[v][u] = 1
 # Mostra a matriz adjacente
 def show(self):
 for i in self.grafo:
 for j in i:
 print(j, end=' ')
 print('')
 # Verifica quem faz fronteira com quem
 def tem_ligacao(self, u, v):
 if self.grafo[u][v] == 1:
 return True
 return False
 def expandir(self, u, v):
 if u > v:
 aux = u
 u = v
 v = aux
 self.destino = v
 self.visitados[u] = True
 for i in range(self.vertices):
 if self.grafo[u][i] == 1 and self.visitados[i] == False:
 self.borda.appendleft(i)
 if len(self.borda) > 0:
 self.removido = self.borda.popleft()
 if u != v:
 self.node.append(self.removido)
 self.expandir(self.removido, self.destino)
 return self.node
 def destino(self, u, v):
 self.caminho = self.expandir(u, v)
 if u > v:
 self.caminho.appendleft(v)
 self.caminho.reverse()
 else:
 self.caminho.appendleft(u)
 for i in self.caminho:
 for j in dic:
 if i == j:
 self.node_final.append(dic[j])
 print(self.node_final)
g = Grafo(8)
#g = Grafo(8)
g.add_aresta(0, 1)
g.add_aresta(0, 4)
g.add_aresta(1, 3)
g.add_aresta(2, 3)
g.add_aresta(2, 6)
g.add_aresta(3, 7)
g.add_aresta(6, 7)
g.add_aresta(4, 5)
g.destino(0, 7)