• Lekce 08
  • Úlohy
  • Co jsme dnes probrali

Lekce 08

Úlohy

Úloh je hodně. Na odevzdání máte 3 týdny, tedy do 13. listopadu.

Grafová třída (1 bod)

Napište si třídu, která bude uchovávat graf jako seznam sousedů. Na instanci třídy chceme mít tři metody:

• add_v přidá nový vrchol, pokud ještě neexistuje
• add_e přidá hranu mezi dvěma vrcholy, pokud ještě neexistuje
• neighbors vrátí seznam sousedů vrcholu

Nejkratší cesta v neohodnoceném grafu (3 body)

Na vstupu očekávejte graf zadaný v tomto formátu:

1 4 8 29 4 75 10
1 8
4 29
10 1
29 75
75 10
-
4 75

První řádek určuje počet a "názvy" vrcholů. Další řádky určují hrany mezi definovanými vrcholy. Můžete vždy očekávat korektní vstup. Po definovaných hranách následuje znak spojovníku (-) a poté dva vrcholy. Vstup končí, pokud narazíte na prázdný řádek.

Najděte nejkratší cestu mezi těmito vrcholy a vypište, jak bychom se z počátečního vrcholu dostali do koncového.

Bludiště (5 bodů)

Na vstupu dostanete bludiště 5 na 5:

S0010
11010
00000
01100
0001E

S označuje začátek, E konec, 1 reprezentuje stěnu, 0 volné pole na které můžeme vstoupit. Pokud existuje cesta, vypište cestu danou posloupností souřadnic ve formátu (x, y), kde x a y jsou čísla od 0 do 4. Pokud cesta neexistuje, program nevypíše nic.

Cykly (4 body)

Na vstupu očekávejte graf zadaný v tomto formátu:

1 4 8 29 4 75 10
1 8
4 29
10 1
29 75
75 10

První řádek určuje počet a "názvy" vrcholů. Další řádky určují hrany mezi definovanými vrcholy. Můžete vždy očekávat korektní vstup. Výčet hran končí, pokud narazíte na prázdný řádek.

Napište program, který zjistí, zdali je v grafu cyklus.

Komponenty souvislosti (4 body)

Na vstupu očekávejte graf zadaný v tomto formátu:

1 4 8 29 4 75 10
1 8
4 29
10 1
29 75
75 10

První řádek určuje počet a "názvy" vrcholů. Další řádky určují hrany mezi definovanými vrcholy. Můžete vždy očekávat korektní vstup. Výčet hran končí, pokud narazíte na prázdný řádek.

Napište program, který zjistí, kolik má graf komponent souvislosti.

Cesta králem (6 bodů)

Napište program, který najde nejkratší cestu králem na šachovnici 8x8. Na šachovnici jsou ale některá políčka, na které nelze vstoupit.

Výstup je buď prázdný (pokud neexistuje cesta) nebo posloupnost souřadnic políček, která král musí projít. Posloupnost vždy začíná počátečním a končí cílovým políčkem. Pokud existuje více nejkratších cest, vypište jen jednu z nich.

Vstup programu vypadá následovně:

• První řádek určuje počet překážek
• Následuje tolik řádků, kolik je počet překážek.
• Souřadnice výchozího políčka
• Souřadnice cílového políčka

Příklad vstupu:

1
2 1
1 1
3 3

Příklad výstupu:

1 1
2 2
3 3

Co jsme dnes probrali

Zásobník (datová struktura!!!) a fronta

• Dvě důležité obecné datové struktury, které se hojně používají
  • Není závislá na implementaci, respektive si ji můžeme naimplementovat, jak chceme
• Zásobník (stack)
  • Princip LIFO - last in, first out
  • Klasický příklad - představte si na sebe naskládané talíře. Abychom žádné nerozbili, můžeme buď přidávat talíře na vrch nebo odebírat talíře z vrchu.
  • Pro zásobník definujme (kromě inicializace) dvě operace
    • PUSH - přidaní na vrchol zásobníku
    • POP - odebrání a vrácení hodnoty z vrcholu zásobníku
  • Se zásobníkem se ještě potkáme, až se budeme zabývat vyhodnocováním aritmetického výrazu
  • Implementace polem (pokud budeme fixovat velikost), spojovým seznamem
• Fronta (queue)
  • Princip FIFO - first in, first out
  • Můžeme si ji představit, mno, jako frontu (lidí). Ti, co se do fronty zařadí dříve, přijdou dříve na řadu.
  • Pro frontu budeme definovat dvě operace
    • ENQUEUE - přidání na konec fronty
    • DEQUEUE - odebrání a vrácení hodnoty z konce fronty
  • Implementace stejná, jako u zásobníku

Jaké mají operace na zásobníku a ve frontě časovou složitost?

Doplňující pojmy (z předchozí lekce)

Z jednoho do druhého vrcholu můžeme dojít několika způsoby. Pokud vybereme jakoukoli posloupnost hran, říkáme této posloupnosti sled. Pokud se ve sledu neopakují hrany, této posloupnosti říkáme tah. Pokud se vrcholy neopakují, řekneme, že jde o cestu.

To, že lze z každého vrcholu dojít do každého jiného po cestě neznamená, že spolu vrcholy sousedí.

Slovo cesta je v teorii grafů dvojznačné. Jednak nám může říkat po jaké trase se vydat, abychom došli z jednoho vrcholu do druhého. Tato trasa nám ale také tvoří samostatný graf. Tento graf je jistě podgrafem grafu původního.

Reprezentace grafu

• Matice sousednosti (adjacency matrix)
  • Pro graf o $n$ vrcholech si vytvoříme matici $A$ velikosti $n \times n$. Na pozici $(k,j)$ v matici $A$ bude 1 nebo 0 podle toho, jestli mezi vrcholy $k$ a $j$ vede hrana.
• Seznam sousedů (adjacency list)
  • Implementace polem nebo hashmapou (slovníkem)
  • Klíče jsou vrcholy, hodnoty jsou seznamy vrcholů, se kterými je vrchol v klíči spojený

  adj = {
    "A": ["B", "C"], # A je spojený s B a C
    "B": ["A", "C"], # B je spojený s A a C
    "C": ["A", "B"]  # C je spojený s A a B
  } # reprezentuje kružnici o třech vrcholech
  

  • Můžeme také použít obyčejné pole, pokud nemáme speciální jména vrcholů

  adj = [
    [1, 2],    # Vrchol 0 je spojený s vrcholy 1 a 2
    [0, 3, 4], # Vrchol 1 je spojený s vrcholy 0, 3 a 2
    [0, 5, 6], 
    [1, 4], 
    [1, 3], 
    [2], 
    [2]
  ]
  

Prohledávání do šířky

• Anglicky Breadth-First Search (BFS)

• Říká se mu prohledávání do šířky, protože prohledává "po vrstvách"

  • Začneme na vrcholu, z něj prohledáme následníky, z nich jejich následníky, a tak dále
  • Prohledáme všechny vrcholy, které jsou dosažitelné z počátečního vrcholu

• Implementace BFS by vypadala asi nějak takto:

  # `graph` is an adjacency list
  def BFS(graph, start):
    q = deque()
  
    visited = [False] * len(graph)
  
    visited[start] = True
    q.append(start)
  
    while q:
      current = q.popleft()
      print(current) # Tiskne, který vrchol právě zpracováváme
  
      for v in graph[current]:
        if not visited[v]:
          visited[v] = True
          q.append(v)
  

• Jakou má tento kód časovou složitost?

• Typické úlohy na použití algoritmu

  • Nalezení nejkratší cesty v neohodnoceném grafu
  • Prohledávání stavového prostoru hry
    • Na kolik nejměné tahů mohu posunout figurkou v šachách tak, abych se dostal z jednoho do druhého pole? Jak vypadá taková posloupnost tahů?

Prohledávání do hloubky

• Anglicky Depth-First Search (DFS)

• Implementace by vypadala asi nějak takto

  def DFS(graph, start):
    s = deque()
  
    visited = [False] * len(graph)
  
    visited[start] = True
    s.append(start)
  
    while s:
        current = s.pop()
        print(current) # Tiskne, který vrchol právě zpracováváme
  
        for v in graph[current]:
            if not visited[v]:
                visited[v] = True
                s.append(v)
  

• Vzhledem k tomu, že nám procesor již zásobník poskytuje (ten volací), můžeme DFS elegantně naprogramovat rekurzivně

  def DFS(graph, current, visited):
    visited[current] = True
    print(current) # Tiskne, který vrchol právě zpracováváme
  
    for v in graph[current]:
        if not visited[v]:
            DFS(graph, v, visited)
  
  # ...
  
  visited = [False] * len(graph)
  # call to DFS with visited as argument
  # DFS(graph, 0, visited)
  

  • Tento průchod může vypadat jinak oproti předchozímu, ale je také správný.

• Aplikace DFS

  • Hledání komponent souvislosti
  • Detekce cyklů v grafu
  • Hledání cesty v bludišti

Poznámky na konec

• Pro pole visited můžeme také použít Pythoní set