Table of Contents

Cvičení 10: Grafy

Quick test 1 - data

slovnik.txt

Reprezentace grafu

G = {}
G [0] = [1 ,2 ,5]
G [1] = [0 ,2]
G [2] = [0 ,1 ,3]
G [3] = [2]

Načtení grafu ze souboru

Mějme orientovaný graf, který má uzly očíslované od 1 do N. Hrany v tomto grafu jsou zadány v souboru, který na jedné řádce obsahuje definici jedné hrany, tedy dvě čísla:

Napište program path.py, který z příkazové řádky načte jméno souboru s definicí hran a číslo startovního uzlu a číslo koncového uzlu. Program vytiskne jednu z nejkratších cest ze startovního uzlu do cílového uzlu.

Program otestujte na tomto souboru:

1 2
1 9
2 3
2 6
3 4
3 8
4 6
4 1
5 4
5 8
6 8
6 9
7 4
7 5
8 7
8 3
9 5
9 1

Výsledek pro cestu z uzlu 2 do uzlu 5 je:

2 6 9 5

Domácí úkol: Lehká varianta Kobylka (Hive)

Tipy

solution = [ [1, 2], [1, -1], [-1, 4] ]   # priklad reseni 
solution.sort()
print(solution)                           # takto vypsane reseni bude akceptovano Brutem

Příklad 1

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 1
3 4 1
3 5 2
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 1
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[[3, 2], [3, 7], [5, 3], [5, 5]]

Komentář: z výchozí pozice (červeně) je možné doskočit na čtyři zelené pozice.

Příklad 2

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 1
0 7 1
0 8 0
0 9 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 1
1 8 0
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 0
2 8 0
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 0
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 1
4 5 1
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 1
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 1
6 3 1
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 1
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[]

Komentář: kobylka nemůže nikam skočit, neboť by došlo k rozpojení hnízda na dvě oddělené části:

Příklad 3

Vstup:

-2 4 0
-1 2 1
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 2
0 4 0
1 0 0
1 1 0
1 2 1
1 3 1
1 4 1
2 0 0
2 1 0
2 2 0
2 3 1
2 4 0
3 0 0
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0

Výstup:

[[0, 1], [2, 1], [3, 3]]

Komentář: kobylka (výchozí pozice je červeně) může skočit na tři zelené buňky:

Domácí úloha, Těžká varianta: Mravenec (Hive)

Příklady pohybu mravence

Tipy

solution = [ [1, 2], [1, -1], [-1, 4] ]   # priklad reseni 
solution.sort()
print(solution)                           # takto vypsane reseni bude akceptovano Brutem

Příklad 1

Vstup:

-2 4 0
-1 2 0
-1 3 0
-1 4 0
0 0 0
0 1 0
0 2 1
0 3 0
0 4 1
1 0 0
1 1 1
1 2 1
1 3 1
1 4 1
2 0 2
2 1 1
2 2 1
2 3 1
2 4 1
3 0 1
3 1 0
3 2 0
3 3 0
4 0 0
4 1 0

Výstup:

[]

Komentář: mravenec se posunem nemůže nikam dostat

Příklad 2

Vstup:

-7 14 0
-6 12 0
-6 13 0
-6 14 0
-5 10 0
-5 11 0
-5 12 0
-5 13 0
-5 14 0
-4 8 0
-4 9 0
-4 10 0
-4 11 0
-4 12 0
-4 13 0
-4 14 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-3 10 0
-3 11 0
-3 12 0
-3 13 0
-3 14 0
-2 4 0
-2 5 0
-2 6 0
-2 7 0
-2 8 0
-2 9 0
-2 10 0
-2 11 0
-2 12 0
-2 13 0
-2 14 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 0
-1 7 0
-1 8 0
-1 9 0
-1 10 0
-1 11 0
-1 12 0
-1 13 0
-1 14 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
0 10 0
0 11 0
0 12 0
0 13 0
0 14 0
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 0
1 9 0
1 10 0
1 11 0
1 12 0
1 13 0
1 14 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 0
2 7 0
2 8 0
2 9 0
2 10 0
2 11 0
2 12 0
2 13 0
2 14 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 0
3 5 0
3 6 0
3 7 1
3 8 1
3 9 0
3 10 0
3 11 0
3 12 0
3 13 0
3 14 0
4 0 0
4 1 0
4 2 0
4 3 0
4 4 0
4 5 0
4 6 1
4 7 0
4 8 1
4 9 1
4 10 0
4 11 0
4 12 0
4 13 0
4 14 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 1
5 7 0
5 8 1
5 9 0
5 10 0
5 11 0
5 12 0
5 13 0
5 14 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 1
6 6 0
6 7 1
6 8 0
6 9 0
6 10 0
6 11 0
6 12 0
6 13 0
6 14 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
7 6 2
7 7 0
7 8 0
7 9 0
7 10 0
7 11 0
7 12 0
7 13 0
7 14 0
8 0 0
8 1 0
8 2 0
8 3 0
8 4 0
8 5 0
8 6 0
8 7 0
8 8 0
8 9 0
8 10 0
8 11 0
8 12 0
8 13 0
9 0 0
9 1 0
9 2 0
9 3 0
9 4 0
9 5 0
9 6 0
9 7 0
9 8 0
9 9 0
9 10 0
9 11 0
10 0 0
10 1 0
10 2 0
10 3 0
10 4 0
10 5 0
10 6 0
10 7 0
10 8 0
10 9 0
11 0 0
11 1 0
11 2 0
11 3 0
11 4 0
11 5 0
11 6 0
11 7 0
12 0 0
12 1 0
12 2 0
12 3 0
12 4 0
12 5 0
13 0 0
13 1 0
13 2 0
13 3 0
14 0 0
14 1 0

Výstup:

[[2, 7], [2, 8], [2, 9], [3, 6], [3, 9], [3, 10], [4, 5], [4, 10], [5, 5], [5, 9], [6, 4], [6, 6], [6, 8], [7, 4], [7, 5], [7, 7]]

Komentář: Mravenec může navštívit následující místa (všimněte si, že do středu hnízda se nedá posunem dostat)

Příklad 3

Vstup:

-4 8 0
-4 9 0
-3 6 0
-3 7 0
-3 8 0
-3 9 0
-2 4 0
-2 5 0
-2 6 1
-2 7 0
-2 8 0
-2 9 0
-1 2 0
-1 3 0
-1 4 0
-1 5 0
-1 6 1
-1 7 1
-1 8 1
-1 9 0
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 1
0 9 1
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
1 7 0
1 8 1
1 9 0
2 0 0
2 1 0
2 2 0
2 3 0
2 4 0
2 5 0
2 6 2
2 7 1
2 8 1
2 9 0
3 0 0
3 1 0
3 2 0
3 3 0
3 4 1
3 5 1
3 6 1
3 7 0
3 8 0
3 9 0
4 0 0
4 1 0
4 2 1
4 3 1
4 4 0
4 5 0
4 6 0
4 7 0
4 8 0
4 9 0
5 0 0
5 1 0
5 2 0
5 3 0
5 4 0
5 5 0
5 6 0
5 7 0
5 8 0
5 9 0
6 0 0
6 1 0
6 2 0
6 3 0
6 4 0
6 5 0
6 6 0
6 7 0
7 0 0
7 1 0
7 2 0
7 3 0
7 4 0
7 5 0
8 0 0
8 1 0
8 2 0
8 3 0
9 0 0
9 1 0

Výstup:

[[-2, 5], [-1, 5], [0, 5], [0, 6], [0, 7], [1, 7], [2, 4], [2, 5], [2, 9], [3, 2], [3, 3], [3, 7], [3, 8], [4, 1], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3]]

Komentář: Mravenec může navštívit následující místa