Reprezentacja maszynowa grafu – czym jest graf?

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).

graf schemat metra Paryż

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.
graf nieskierowany mapa miasta

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).

graf skierowany

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).

graf skierowany macierz sąsiedztwa
  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:

graph = [
[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.

graf skierowany macierz incydencji
  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.

graf skierowany lista krawędzi
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):

graph = [(0, 1), (0, 2), (0, 3), (1, 3), (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.

graf skierowany lista następników
Lista następników:
1: 2, 3, 4
2: 4
3: 4
4:
Lista poprzedników:
1:
2: 1
3: 1
4: 1, 2, 3

Przykładowa lista następników jako słownik:

graph = {1:[2, 3, 4], 2:[4], 3:[4],}

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:

graf nieskierowany macierz sąsiedztwa
  1 2 3 4
1 0 1 1 1
2 1 0 0 1
3 1 0 0 1
4 1 1 1 0
graph = [
[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.
miasta na mapie polski jako graf

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:

graf z wagami skierowany macierz 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
graph = [
[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