<jupyter_start><jupyter_text>Grafo - <NAME>  Grafo<jupyter_code>class Vertice:

  def __init__(self, rotulo, distancia_objetivo):
    self.rotulo = rotulo
    self.visitado = False
    self.distancia_objetivo = distancia_objetivo
    self.adjacentes = []

  def adiciona_adjacente(self, adjacente):
    self.adjacentes.append(adjacente)

  def mostra_adjacentes(self):
    for i in self.adjacentes:
      print(i.vertice.rotulo, i.custo)
class Adjacente:
  def __init__(self, vertice, custo):
    self.vertice = vertice
    self.custo = custo
class Grafo:
  porto_uniao = Vertice('Porto União', 203)
  paulo_frontin = Vertice('Paulo Frontin', 172)
  irati = Vertice('Irati', 139)
  canoinhas = Vertice('Canoinhas', 141)
  tres_barras = Vertice('Três Barras', 131)
  sao_mateus_do_sul = Vertice('São Mateus do Sul', 123)
  curitiba = Vertice('Curitiba', 0)
  palmeira = Vertice('Palmeira', 59)
  mafra = Vertice('Mafra', 94)
  campo_largo = Vertice('Campo Largo', 27)
  balsa_nova = Vertice('Balsa Nova', 41)
  lapa = Vertice('Lapa', 74)
  tijucas_do_sul = Vertice('Tijucas do Sul', 56)
  araucaria = Vertice('Araucária', 23)
  contenda = Vertice('Contenda', 39)
  sao_jose_dos_pinhais = Vertice('São José dos Pinhais', 13)

  porto_uniao.adiciona_adjacente(Adjacente(paulo_frontin, 46))
  porto_uniao.adiciona_adjacente(Adjacente(sao_mateus_do_sul, 87))
  porto_uniao.adiciona_adjacente(Adjacente(canoinhas, 78))

  paulo_frontin.adiciona_adjacente(Adjacente(porto_uniao, 46))
  paulo_frontin.adiciona_adjacente(Adjacente(irati, 75))

  sao_mateus_do_sul.adiciona_adjacente(Adjacente(porto_uniao, 87))
  sao_mateus_do_sul.adiciona_adjacente(Adjacente(tres_barras, 43))
  sao_mateus_do_sul.adiciona_adjacente(Adjacente(irati, 57))
  sao_mateus_do_sul.adiciona_adjacente(Adjacente(palmeira, 77))
  sao_mateus_do_sul.adiciona_adjacente(Adjacente(lapa, 60))

  canoinhas.adiciona_adjacente(Adjacente(porto_uniao, 78))
  canoinhas.adiciona_adjacente(Adjacente(tres_barras, 12))
  canoinhas.adiciona_adjacente(Adjacente(mafra, 66))
  
  irati.adiciona_adjacente(Adjacente(paulo_frontin, 75))
  irati.adiciona_adjacente(Adjacente(sao_mateus_do_sul, 57))
  irati.adiciona_adjacente(Adjacente(palmeira, 75))

  tres_barras.adiciona_adjacente(Adjacente(sao_mateus_do_sul, 43))
  tres_barras.adiciona_adjacente(Adjacente(canoinhas, 12))

  palmeira.adiciona_adjacente(Adjacente(sao_mateus_do_sul, 77))
  palmeira.adiciona_adjacente(Adjacente(irati, 75))
  palmeira.adiciona_adjacente(Adjacente(campo_largo, 55))

  lapa.adiciona_adjacente(Adjacente(sao_mateus_do_sul, 60))
  lapa.adiciona_adjacente(Adjacente(contenda, 26))
  lapa.adiciona_adjacente(Adjacente(mafra, 57))

  mafra.adiciona_adjacente(Adjacente(canoinhas, 66))
  mafra.adiciona_adjacente(Adjacente(lapa, 57))
  mafra.adiciona_adjacente(Adjacente(tijucas_do_sul, 99))

  contenda.adiciona_adjacente(Adjacente(lapa, 26))
  contenda.adiciona_adjacente(Adjacente(balsa_nova, 19))
  contenda.adiciona_adjacente(Adjacente(araucaria, 18))

  campo_largo.adiciona_adjacente(Adjacente(palmeira, 55))
  campo_largo.adiciona_adjacente(Adjacente(balsa_nova, 22))
  campo_largo.adiciona_adjacente(Adjacente(curitiba, 29))

  balsa_nova.adiciona_adjacente(Adjacente(curitiba, 51))
  balsa_nova.adiciona_adjacente(Adjacente(contenda, 19))
  balsa_nova.adiciona_adjacente(Adjacente(campo_largo, 22))

  araucaria.adiciona_adjacente(Adjacente(curitiba, 37))
  araucaria.adiciona_adjacente(Adjacente(contenda, 18))
  
  tijucas_do_sul.adiciona_adjacente(Adjacente(sao_jose_dos_pinhais, 49))
  tijucas_do_sul.adiciona_adjacente(Adjacente(mafra, 99))

  sao_jose_dos_pinhais.adiciona_adjacente(Adjacente(curitiba, 15))
  sao_jose_dos_pinhais.adiciona_adjacente(Adjacente(tijucas_do_sul, 49))

  curitiba.adiciona_adjacente(Adjacente(campo_largo, 29))
  curitiba.adiciona_adjacente(Adjacente(balsa_nova, 51))
  curitiba.adiciona_adjacente(Adjacente(araucaria, 37))
  curitiba.adiciona_adjacente(Adjacente(sao_jose_dos_pinhais, 15))
grafo = Grafo()<jupyter_output><empty_output><jupyter_text>Vetor ordenado<jupyter_code>import numpy as np
class VetorOrdenado:
  
  def __init__(self, capacidade):
    self.capacidade = capacidade
    self.ultima_posicao = -1
    # Mudança no tipo de dados
    self.valores = np.empty(self.capacidade, dtype=object)

  # Referência para o vértice e comparação com a distância para o objetivo
  def insere(self, vertice):
    if self.ultima_posicao == self.capacidade - 1:
      print('Capacidade máxima atingida')
      return
    posicao = 0
    for i in range(self.ultima_posicao + 1):
      posicao = i
      if self.valores[i].distancia_objetivo > vertice.distancia_objetivo:
        break
      if i == self.ultima_posicao:
        posicao = i + 1
    x = self.ultima_posicao
    while x >= posicao:
      self.valores[x + 1] = self.valores[x]
      x -= 1
    self.valores[posicao] = vertice
    self.ultima_posicao += 1

  def imprime(self):
    if self.ultima_posicao == -1:
      print('O vetor está vazio')
    else:
      for i in range(self.ultima_posicao + 1):
        print(i, ' - ', self.valores[i].rotulo, ' - ', self.valores[i].distancia_objetivo)  
vetor = VetorOrdenado(5)
vetor.insere(grafo.porto_uniao)
vetor.insere(grafo.tres_barras)
vetor.insere(grafo.palmeira)
vetor.insere(grafo.paulo_frontin)
vetor.imprime()
vetor.insere(grafo.araucaria)
vetor.imprime()
vetor.valores[0], vetor.valores[0].rotulo<jupyter_output><empty_output><jupyter_text>Busca gulosa<jupyter_code>class Gulosa:
  def __init__(self, objetivo):
    self.objetivo = objetivo
    self.encontrado = False

  def buscar(self, atual):
    print('-------')
    print('Atual: {}'.format(atual.rotulo))
    atual.visitado = True

    if atual == self.objetivo:
      self.encontrado = True
    else:
      vetor_ordenado = VetorOrdenado(len(atual.adjacentes))
      for adjacente in atual.adjacentes:
        if adjacente.vertice.visitado == False:
          adjacente.vertice.visitado == True
          vetor_ordenado.insere(adjacente.vertice)
      vetor_ordenado.imprime()

      if vetor_ordenado.valores[0] != None:
        self.buscar(vetor_ordenado.valores[0])  

busca_gulosa = Gulosa(grafo.curitiba)
busca_gulosa.buscar(grafo.porto_uniao)<jupyter_output>-------
Atual: Porto União
0  -  São Mateus do Sul  -  123
1  -  Canoinhas  -  141
2  -  Paulo Frontin  -  172
-------
Atual: São Mateus do Sul
0  -  Palmeira  -  59
1  -  Lapa  -  74
2  -  Três Barras  -  131
3  -  Irati  -  139
-------
Atual: Palmeira
0  -  <NAME>  -  27
1  -  Irati  -  139
-------
Atual: <NAME>
0  -  Curitiba  -  0
1  -  <NAME>  -  41
-------
Atual: Curitiba
{'fraction_non_alphanumeric': 0.11451539511603216, 'fraction_numerical': 0.027605035643864705, 'mean_word_length': 4.674698795180723, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '448940', 'license': 'MIT', 'n_tokens_mistral': 3058, 'n_tokens_neox': 2858, 'n_words': 395, 'path': 'Grafo_Busca_Gulosa_Curitiba.ipynb', 'repo_name': 'GabrielLourenco12/python_algoritmo_de_busca', 'size': '6613'}