Problema_das_Chaves

import random


class Graph:
    def __init__(self, vert):
        self.vert = vert
        self.graph = [[0] * vert for i in range(vert)]
        self.key_location = random.randint(0, vert-1)
        self.visited = [False for i in range(vert)]
        self.comodos = {0: "Sala",
                        1: "Cozinha",
                        2: "Corredor",
                        3: "Banheiro",
                        4: "Quarto de casal",
                        5: "Quarto de visita"}

    def show_graph(self):
        col, row = 65, 65
        for i in range(self.vert):
            for j in range(self.vert):
                print("{}\t".format(self.graph[i][j]), end="")
            print("\033[1;31m{}\033[m".format(chr(row)))
            row += 1
        for j in range(self.vert):
            print("\033[1;31m{}\033[m\t".format(chr(col)), end="")
            col += 1
        print("")

    def add_edge(self, vert1, vert2):
        if self.graph[vert1][vert2] != 1 and self.graph[vert2][vert1] != 1:
            self.graph[vert1][vert2] = 1
            self.graph[vert2][vert1] = 1
        else:
            return

    def search_key(self, start):
        # Este algoritmo está usando busca por profundidade (implícito: recursão)
        local = start
        self.visited[local] = True
        if local == self.key_location:
            print("\nChave encontrada! Local: {}.".format(self.comodos[local]))
            return self.key_location
        else:
            for i in range(self.vert):
                if self.graph[local][i] == 1 and self.visited[i] is False and i != local:
                    self.search_key(i)


g = Graph(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(4, 3)
g.show_graph()
g.search_key(0)

SAÍDA:

C:\Users\Oraplas_AutoCard\PycharmProjects\Algoritmos_de_busca\venv\Scripts\python.exe C:/Users/Oraplas_AutoCard/PycharmProjects/Algoritmos_de_busca/Problema_das_chaves.py
0   1   1   0   0   0   A
1   0   0   0   0   0   B
1   0   0   0   1   1   C
0   0   0   0   1   0   D
0   0   1   1   0   0   E
0   0   1   0   0   0   F
A   B   C   D   E   F

Chave encontrada! Local: Cozinha.

Process finished with exit code 0