bfs Romenia

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

# encoding: utf-8
# Busca em Largura
# Curso.: Ciência da Computação_IFCE
# Disciplina.: Inteligência Artificial
#Professor Ajalmar
# Autor: Romulo Cesar C. Lima, Mat.:2015104505062
#Dicionário das cidades da Romênia, para estudo
dic = {0: 'Arad', 1: 'Timisora', 2: 'Sibiu', 3: 'Zarid', 4: 'Lugoj', 5: 'Mehadia', 6: 'Drobeta', 7: 'Caiova',
 8: 'Pitest', 9: 'Vilcea', 10: 'Fagaras', 11: 'Oradea', 12: 'Bucareste', 13: 'Giurgiu', 14: 'Urzienni',
 15: 'Hisorva', 16: 'Eforia', 17: 'Vaslui', 18: 'Iasi', 19: 'Neamt'}
cidade=list(dic.values())
certo=False
# Entrar com a Origem e Destino(Solução)
def informar(certo):
 while certo == False:
 pos = (str(input('Digite a cidade de origem:')).title())
 if pos in cidade and pos.isalpha():
 a = cidade.index(pos)
 dest = str(input('Digite a cidade de destino: ')).title()
 if dest in cidade and dest.isalpha():
 b = cidade.index(dest)
 certo = True
 return a+1, b
# 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)]
 # Adiciona elementos 1 para vertices que fazem fronteira,
 def add_aresta(self, u, v):
 self.grafo[u - 1][v - 1] = 1
 self.grafo[v - 1][u - 1] = 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 - 1][v - 1] == 1:
 return True
 return False
 #Busca em largura inclui todos os visitados
 def bfs(self, v, u):
 visitados = [False] * self.vertices
 visitados[v - 1] = True
 borda = [v - 1]
 node = []
 while len(borda) > 0 and v != u:
 v = borda[0]
 for i in range(self.vertices):
 if self.grafo[v][i] == 1:
 if visitados[i] == False:
 visitados[i] = True
 borda.append(i) # Adiciona no final
 a = borda.pop(0) # Reita o primeiro (Fila)
 node.append(a)
 return node
 #Mostrar o caminho encontrado
 def parada(self, lista):
 cont = 0
 lista01 = []
 x = lista[0]
 lista01.append(x)
 while len(lista) > cont:
 for i in lista:
 if self.grafo[x][i] == 1 and x != lista[-1]:
 x = i
 lista01.append(x)
 cont += 1
 return (lista01)
 # Mostrar um lista alfanumerica das cidade que fazem o caminho
 # (origem-destino)
 def destino(self, lista):
 lista_02 = []
 for j in lista:
 for i in dic:
 if i == j:
 lista_02.append(dic[i])
 print(lista_02)
g = Grafo(22)
g.add_aresta(1, 2)
g.add_aresta(1, 3)
g.add_aresta(1, 4)
g.add_aresta(2, 5)
g.add_aresta(3, 10)
g.add_aresta(3, 11)
g.add_aresta(3, 12)
g.add_aresta(4, 12)
g.add_aresta(5, 6)
g.add_aresta(6, 7)
g.add_aresta(7, 8)
g.add_aresta(8, 9)
g.add_aresta(8, 10)
g.add_aresta(9, 13)
g.add_aresta(11, 13)
g.add_aresta(13, 14)
g.add_aresta(13, 15)
g.add_aresta(15, 16)
g.add_aresta(15, 18)
g.add_aresta(16, 17)
g.add_aresta(18, 19)
g.add_aresta(19, 20)
a,b=informar(certo)
lista = g.bfs(a, b)
lista.reverse()
res=g.parada(lista)
res.reverse()
print(res)
g.destino(res)