Dynamické datové struktury; prohledávání do šířky a do hloubky

• Úlohy
  • Grafová třída (1 bod)
  • Nejkratší cesta v neohodnoceném grafu (3 body)
  • Bludiště (5 bodů)
  • Cykly (4 body)
  • Komponenty souvislosti (4 body)
  • Cesta králem (6 bodů)
• Co jsme dnes dělali?

Úlohy

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 dělali?