Pro pochopení prohledávání do hloubky

• Zeptejte se, rád vysvětlím :)
• Visualizace prohledávání

Z minula

• Hledání dosažitelných políček
• Výpočet nejkratší vzdálenosti
• Hledání nejkratší cesty

Vstupní soubory:

• Vzorové bludiště

Úkol A

Spočítejte, kolik je v bludišti místností (souvislých oblastí, ze kterých nejde utéci).

Úkol B

Spočítejte, kolik má která místnost políček.

Prohledávání v grafu

Reprezentace grafu

Projdeme společně

Základní implementace

• Seznam sousedů
• Matice sousednosti

Pomocí tříd

• Seznam sousedů
• Matice sousednosti

Dnešní úkoly

• Najděte v grafu dva nejvzdálenější vrcholy.
• Najděte všechny vrcholy, které leží na některé z nejkratších cest mezi zadnou dvojicí vrcholů.
• Spočítejte, kolik má neorientovaný graf komponent souvislosti.
• Nalezněte pomocí BFS kostru grafu (tvoří ji ty hrany, které vedly do nově objevených vrcholů).

Iterátory

• Zdroj

#!/usr/bin/python3
# Příklad na iterátory: vlastní implementace range(n)

class MyRange:

    def __init__(self, n):
        self.n = n

    # Touto magickou metodou objektu řekneme, aby vyrobil iterátor
    def __iter__(self):
        return MyIter(self)

class MyIter:

    # Iterátoru při inicializaci říkáme, ke kterému MyRange patří
    def __init__(self, rng):
        # Iterátor si pamatuje range a poslední vygenerované číslo
        self.rng = rng
        self.i = -1

    # Touto magickou metodou po iterátoru chceme, aby vydal další prvek,
    # nebo vyvolal výjimku StopIteration, pokud už žádný další neexistuje.
    def __next__(self):
        self.i += 1
        if self.i < self.rng.n:
            return self.i
        else:
            raise StopIteration

for x in MyRange(10):
    print(x)

# Uvnitř for-u se stane toto:
#
#   r = MyRange(10)
#   it = r.__iter__()    <- řekneme objektu MyRange, aby vyrobil iterátor
#   while True:
#       x = it.__next__()   <- řekneme iterátoru, aby vydal další prvek
#       pokud nastala výjimka StopIteration, skonči
#       print(x)         <- tělo cyklu