W codziennym życiu grafy towarzyszą nam wszędzie. Gdy spojrzymy na sieć kolejową i stacje czy linie autobusowe, tramwajowe, czy skomplikowaną mapę paryskiego metra widzimy grafy, których działanie rozumieją już dzieci w przedszkolu. Nikogo nie dziwi fakt, że pociągi mogą jechać od stacji Warszawa do stacji Poznań lub z Poznania do Warszawy (odpowiednik grafu nieskierowanego). Istnieją osiedla, na którym jest kilka skrzyżowań i wiele uliczek jednokierunkowych (graf skierowany).
Dla powyższych przykładów łatwo narysujemy mapę tj. graf i wytłumaczymy drugiej osobie dokąd chcemy dotrzeć. Jednak czy zrozumie nas komputer? Jeżeli przedstawimy mu dane jako reprezentację grafu – tak! I o tym jest dzisiejszy post.
Grafy, jedno z podstawowych pojęć algorytmicznych (dlaczego warto poznać ich podstawy przeczytacie tutaj: algorytmy w nauce programowania), może budzić niechęć, chociaż zupełnie nie ma powodu.
Intuicyjnie wiemy czym jest graf. Ma wierzchołki (czasem zwane węzełem w grafie), które są połączone, a połączenia to krawędzie. Krawędzie mogą być skierowane lub nieskierowane.
Dla przykładu z koleją – stacje to wierzchołki, torowiska między nimi krawędzie 🙂
Nauka zajmująca się grafami nazywa się Teorią Grafów i to zgrubsza tyle, ile potrzebujemy, by zacząć rozmawiać o grafach i ich reprezentacji maszynowej (czyli takiej, którą rozumie komputer).
Reprezentacja maszynowa grafu
Na wstępie potrzebujemy kilka podstawowych pojęć:
Co to jest reprezentacja maszynowa grafu?
To sposób zapisu grafu tak, by informacje w nim zawarte można było przetwarzać za pomocą komputera.
Jak zdefiniować graf?
Graf jest strukturą zapisywaną jako G = (V, E), składającą się z węzłów (wierzchołków, oznaczanych przez V ang. vertex) wzajemnie połączonych za pomocą krawędzi (oznaczonych przez E ang. edge).
Złożoność pamięciowa (ang. space computational complexity /space complexity) – przechowywanie danych zajmuje określoną część w pamięci operacyjnej komputera (myślę, że wiele osób to rozumie, że gdy zabraknie pamięci, programy komputerowe się zawieszają). W przypadku pamięci mówimy o komórkach pamięci, która będzie zajęta przez dane oraz wyniki (także te pośrednie) tworzone w trakcie działania algorytmu.
W uproszczeniu jedna wartość liczbowa, którą musi przechowywać komputer to jedna komórka pamięci, pomoże nam to zrozumieć poniższe przykłady.
Przykładowe reprezentacje grafowe:
| struktura | złożoność |
|---|---|
| macierz sąsiedztwa | V*V |
| macierz incydencji | V*E |
| lista krawędzi | E |
| lista następników | V+E |
| lista poprzedników | V+E |
| macierz grafu | (V+2)^2 |
1) Macierz sąsiedztwa
W tablicy (macierzy) o wymiarach V * V uzupełniamy obecność krawędzi między wierzchołkami – krawędź występuje (1) lub jej nie ma (0).
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 |
Z wierzchołka 1, mamy krawędź do wierzchołków o numerach 2,3,4. Z wierzchołka 2, mamy poprowadzoną krawedź do wierzchołka 4, z wierzchołka 3 istnieje krawędź do wierzchołka 4. Od wierzchołka 4 nie mamy żadnych krawędzi.
Przykładowy kod:
[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
Jeśli byśmy chcieli szybko sprawdzić czy istnieje krawędź od wierzchołka 1 do 4 wystarczy, że wyświetlimy komórkę graph[0][3] – komórki tabeli numerowane są od 0.
2) Macierz incydencji
Tablica zawierająca licznę wierzchołków na liczbę krawędzi w grafie. Bardzo nieopłacalna (zajmuje dużo pamięci) dla grafów rzadkich (mających mało krawędzi). Trzeba sprawdzić każdą krawędź czy istniej podczas gdy de facto tylko kilka istniejących nas interesuje.
| 11 | 12 | 13 | 14 | 21 | 22 | …etc | |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | … |
| 2 | |||||||
| 3 | |||||||
| 4 |
W powyższym przykładzie krawędzie zostały oznaczone jako krawędź 1-1 (wierzchołek 1 do wierzchołka 1 – sam do siebie), 1-2 (wierzchołek 1 do wierzchołka 2), 1-3, 1-4, 2-1 (wierzchołek 2 do wierzchołka 1), 2-2 … i tak dalej.
3) Lista krawędzi
Zapisywana jako tablica 2-wymiarowa, albo lista. Jeśli istnieje krawędź między dwoma wierzchołkami to wpisujemy wierzchołek 'od’ i 'do’ którego krawędź wchodzi.
| od | do |
|---|---|
| 1 | 2 |
| 1 | 3 |
| 1 | 4 |
| 2 | 4 |
| 3 | 4 |
Przykładowy kod jako tablica z krotkami (pamiętając, że wierzchołki numerujemy od zera – 0,1,2,3):
4) Lista następników lub poprzedników
Lista wierzchołków następujących po danym wierzchołku lub poprzedzających dany wierzchołek.
1: 2, 3, 4
2: 4
3: 4
4:
1:
2: 1
3: 1
4: 1, 2, 3
Przykładowa lista następników jako słownik:
Graf nieskierowany?
Powyższe przykłady podałam dla grafów skierowanych (graf digraf). Tzn takich, których każda krawedź ma wierzchołek początkowy i końcowy. Dla grafów nieskierowanych, inaczej zwanych grafami prostymi, reprezentacja grafu będzie bardzo podobna. Brak skierowania, oznacza, że ruch po krawędzi może odbywać się w obie strony, dlatego przykładowo macierz sąsiedztwa będzie symetryczna:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 1 | 1 | 1 | 0 |
[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]
]
Co jeżeli chcemy wprowadzić graf, którego wierzchołki nazywane są A, B, C … etc?
Właściwie nie ma problemu. Dla macierzy sąsiedztwa nie ma to znaczenia, ponieważ, co się kryje pod komórką [0][0] to kwestia zaprojektowania algorytmu.
Lista krawędzi będzie przykładowo wyglądała tak:
graph = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('C', 'D')]
a lista następników dla tego samego grafu:
graph = {'A':['B', 'C', 'D'], 'B':['C'], 'C':['D'],}
Graf z wagami
Wiemy już jak wyglądają grafy i jak rozumie je maszyna, przy czym do tej pory pokazałam wam grafy, o krawędziach bez wag.
Wagi? Jakie znowu wagi?
Zacznijmy od przykładu: wiemy, że z Warszawy do Krakowa trzeba przejechać 296 km, to tyle samo ile jest pomiędzy Warszawą, a Poznaniem. Między Warszawą i Gdańskiem – 323km, Gdańskiem i Poznaniem – 338km, Poznaniem i Wrocławiem – 172km. Gdybyśmy połączyli te miasta na mapie linią prostą i zapisali sobie te transy na liniach łączenia otrzymalibyśmy graf z zapisanymi wartościami nad krawędziami. Tym właśnie są wagi w grafie.
Powyższy graf przedstawia trasy jako równe w obie strony – graf nieskierowany. Oczywiście, graf z wagami może być grafem skierowanym. Trasa z miasta A do miasta B wynosi 45km. Powrót z miasta B do A nie jest możliwy tą trasą przez remont i wymaga dodatkowe 7 km objazdu.
Wagi w grafie
To wartości przypisane krawędziom w grafie.
Mogą opisywać np.:
- koszt przejścia między wierzchołkami
- przepustowość połączenia
- częstotliwość kontaktów
Spójrz na graf skierowany z wagami na krawędziach. Przykładowo możemy te wartości zapisać w macierzy sąsiedztwa:
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 16 | 0 | 0 |
| 2 | 10 | 0 | 18 | 0 |
| 3 | 35 | 0 | 0 | 20 |
| 4 | 10 | 16 | 0 | 0 |
[0, 16, 0, 0],
[10, 0, 18, 0],
[35, 0, 0, 20],
[10, 16, 0, 0]
]
Wpis powstał w ramach wprowadzenia i nie streszcza całej wiedzy o grafach (tylko podstawę, która przyda się w kolejnych postach, ale pewnie będzie rozbudowywany 😉 )
Ćwiczenia
Jeżeli nie macie dość i chcecie sobie poćwiczyć oto przykładowe zadania do rozwiązania w dowolnym języku programowania:
1) *Rozgrzewka, narysuj na kartce poniższe grafy:
graphA = {1:[2, 3, 5], 2:[1, 3, 4], 3:[2, 4], 4: [1, 5]}
graphB = [('A', 'B'), ('A', 'C'), ('A', 'E'), ('B', 'A'), ('B', 'C'), ('B', 'E'), ('C', 'A'), ('C', 'C'), ('C', 'D'), ('D', 'A'), ('E', 'C')]
graphC = [
[0, 0, 12, 8, 4],
[6, 0, 16, 7, 5],
[13, 5, 0, 9, 0],
[0, 0, 22, 0, 0],
[21, 7, 5, 4, 0]
]
2) Stwórz prosty program, który zawiera i wyświetla przykłady z dzisiejszego posta.
3) Stwórz program, który przyjmuje pary wierzchołków w grafie wpisane z klawiatury jako dowolne pary odzieone znakiem specjalnym (np. może być to myślnik 1-2, 2-3, 2-4), zapisuje je jako: (a) macierz sąsiedztwa, (b) listę krawędzi i (c) listę następników, a następnie wyświetla te struktury.
Dodatkowo niech programo pozwala na:
- sprawdzenie czy krawędź, o którą pyta użytkownik programu istnieje
- dodanie nowej krawędzi po wyświetleniu grafu
- usunięcie krawędzi
- odczytanie par krawędzi zamiast z klawiatury z pliku txt
- zapis grafu wprowadzonego z klawiatury do pliku w formacie, który pozwala odczytać graf ponownie
Dobry tekst, dzięki 🙂
Jakie będą złożoności obliczeniowe wyszukiwania jednego dowolnego oraz wszystkich następników wierzchołka dla powyższych reprezentacji?
PS świetna strona! 😉
Zależy od przyjętego sposobu przeszukiwania, ale najprawdopodobniej będziesz mieć złożoność zależną od liczby wierzchołków i krawędzi do przeszukania, więc analogicznie jak lista następników -> O(E+V).
zrobiłam wyświetlanie pierwszego, ale reszta tak se
graph = [(0, 1), (0, 2), (0, 3), (1, 3), (2, 3)] for pair in graph: print("krawedz od:", pair[0], "do:", pair[1]