dfs sem visitado aspirador

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

from collections import deque #Utilizado para formar uma pilha inevertida
import random as ra
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'}
cidades = list(dic.values())
correto = False
# Classe para montar a matriz de adjacencia, expandir fronteira, da origem ao destino
class Grafo:
 def __init__(self, vertices):
 self.vertices = vertices
 self.grafo = [[0] * vertices for i in range(vertices)]
 self.node = deque()
 self.borda = deque()
 self.bordas =deque()
 self.node_final = []
 self.cont = 0
 def add_aresta(self, u, v):
 self.grafo[u][v] = 1
 self.grafo[v][u] = 1
 def show(self):
 for i in self.grafo:
 for j in i:
 print(j, end=' ')
 print('')
 def tem_ligacao(self, u, v):
 if self.grafo[u][v] == 1:
 return True
 return False
 def expandir(self,a, b):
 self.node.append(a)
 self.cont = 0
 while a!=b:
 for i in range(self.vertices):
 if g.grafo[a][i] == 1:
 self.borda.appendleft(i)
 ra.shuffle(self.borda)
 if len(self.borda)>0:
 for i in self.borda:
 self.bordas.appendleft(i)
 self.borda.clear()
 a = self.bordas.popleft()
 self.node.append(a)
 return self.node
 def destino(self, u, v):
 self.caminho = self.expandir(u, v)
 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.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)
print('Esquerdo_E-Sujo_D-Sujo até Direiro_E-Limpo_D-Limpo')
g.destino(0, 7)
print('Esquerdo_E-Sujo_D-Sujo até Direiro_D-Limpo_D-Limpo')
g.destino(0, 6)