GRAFY

Struktura grafu jest bardzo często potrzebna w programach, algorytmach. Warto nauczyć się ją efektywnie reprezentować.

Graf to zbiór wierzchołków V i zbiór krawędzi E, przy czym krawędzie są to pary wierzchołków. Jeśli graf jest skierowany, wówczas kolejność wierzchołków w tej parze jest istotna. Ja zajmę się właśnie grafami skierowanymi. Niech |V| = N i |E| = K.

Każdy wierzchołek i każda krawędź mogą mieć etykiety - wartości dowolnego ustalonego typu.

Reprezentacje grafów w pamięci programu.

1. Wskaźnikowa:
Każdy wierzchołek jest rekordem, posiada listę wskaźników do swoich sąsiadów (fizycznie do tych rekordów), lub listę par: (wskaźnik do sąsiada, etykieta krawędzi) jeśli krawędzie są etykietowane.
Wszystkie wierzchołki można trzymać na liście.
Ta reprezentacja nadaje się bardziej do "wędrowania po grafie" a mniej do stosowania algorytmów BFS/DFS i na nich opartych. Częściej używa się jej w programowaniu obiektowym, gdzie nienumerowane obiekty w pewnych zależnościach między sobą są czymś zupełnie naturalnym.
Zalety:
- nie nadużywamy pamięci,
- łatwa zmiana grafu (bo nie musimy się troszczyć o numerowanie),
- przechodzenie po grafie po wskaźnikach,
Wady:
- trudne wczytywanie i zapisywanie grafu, 
- podczas przechodzenia gafu musimy zaznaczać odwiedzone wierzchołki w samych rekordach, nie można dopisać rzeczy nie przewidzianych w typie rekordów wierzchołka i krawędzi,

W poniższych reprezentacjach identyfikujemy wierzchołki za pomocą liczb z przedziału 1..N (lub 0..N-1).

2. Macierzowa:
Tablica [N,N], gdzie w komórce (i,j) jest False (brak krawędzi od i do j) lub True (isnieje krawędź od i do j). Jeśli wierzchołki mają być etykietowane, należy zrobić jeszcze tablicę [N] etykiet. Jeśli krawędzie mają być etykietowane - etykiety zapisywać w samej macierzy (określona wartość będzie oznaczać brak krawędzi), lub w macierzy zapisywać wskaźnik do etykiety / NIL jeśli brak krawędzi.
Zalety:
- prostota,
- szybkie sprawdzenie czy istnieje krawędź dla danych wierzchołków,
Wady:
- koszt pamięciowy N^2 nawet jeśli jest mało krawędzi,
- przejrzenie wszystkich sąsiadów jednego wierzchołka zajmuje N nawet jeśli jest mało sąsiadów,
- łatwo zmienia się krawędzie, trudno wierzhołki.
Ta reprezentacja ma sens, jeśli wiadomo, że graf jest bardzo mały, albo jeśli jest bardzo gęsty (krawędzi jest rzędu N^2).
W przypadku grafu nieskierowanego można posłużyć się "macierzą trójkątną" i zaoszczędzić połowę pamięci.

3. Tablica wierzchołków + listy sąsiadów:
Tablica [N] wierzchołków, każdy wierzchołek to rekord z etykietą i listą sąsiadów. Sąsiedzi na tej liście podani jako numery wierzchołków. Jeśli krwędzie mają być etykietowane, na liście powinny być pary (sąsiad, etykieta krawędzi).
Zalety:
- nie nadużywamy pamięci,
- łatwe przechodzenie po grafie,
- można "z boku", w nowej tablicy zapisywać informacje o wierzchołkach, np. znaczniki odwiedzonych wierzchołków,
Wady:
- trzeba przejrzeć listę sąsiadów aby sprawdzić czy istnieje konkretna krawędź,
- trudno zmienia się wierzchołki, w miarę łatwo krawędzie (można po prostu dodać, usunąć z listy).

4. Tylko tablice:
Liczby 1..N reprezentują nam wierzchołki. Liczby 1..K reprezentują krawędzie.
Tablica A[1..N] wiąże wierzchołki z krawędziami w następujący sposób:
Dla wierzchołka i krawędzie wychodzące z i mają numery od A[i] do A[i+1]-1.
Jeśli z i nie wychodzi żadna krawędź to A[i] = A[i+1]. Jeśli chodzi o ostatni wierzchołek to krawędzie mają numery od A[N] do K, można też dodać strażnika A[N+1]=K.
Teraz w tablicy E[1..K] zapisujemy numery wierzchołków, do których prowadzą podane krawędzie, jeśli wierzchołki są etykietowane, używamy tablicy [1..N], jeśli krawędzie są etykietowane, używamy tablicy [1..K].
Zalety:
- bardzo efektywne wykorzytanie pamięci (nie tracimy nawet na wskaźniki na listach),
- można "z boku" zapisywać informacje o wierzchołkach i krawędziach,
- łatwo można zmieniać wartości etykiet,
Wady:
- trzeba przejrzeć wszystkie krawędzie wychodzące aby sprawdzić czy istnieje krawędź (i,j),
- trudno zmienia się strukturę grafu (usuwa, dodaje krawędzie i wierzchołki).

To moja ulubiona reprezentacja, polecam w przypadku zastosowań gdy nie modyfikujemy struktury grafu. Dobrze używa się w językach, gdzie można alokować tablice o zadanym rozmiarze.

-----------------------------

REPREZENTCJA W PLIKU

Opiszę tylko jedną, która przyda się w zadaniu.

Plik tekstowy ma N wierszy, w wierszu i opisany jest wierzchołek i. W jednym wierszu zapiane są ewentualne etkiety wierzchołka, dalej liczba M oznaczająca liczbę krawędzi wychodzących z tego wierzchołka i dalej M razy opis krawędzi, na który składa się numer wierzchołka docelowego i ewentualnie etykieta(etykiety).

Z pewną modyfikacją ten format pliku jest zastosowany w pliku KOLEJ.TXT.

-----------------------------
PLIK KOLEJ.TXT

W tym pliku jest zapisana niespełna połowa polskiej sieci kolejowej. A może już ponad, niestety nie dzięki dopisywaniu nowych linii :( ...

W piewszym wierszu jest liczba - tyle kolejnych wierszy jest komentarzem.
W następnym znaczącym wierszu są liczby: N (wierzchołków) K (krawędzi) i parę innych. Wierzchołki są numerowane od 0 do N-1.

Kolejne wiersze to opisy wierzchołków, kolejno są zapisane:
  liczba i - numer wierzchołka (powinny być to kolejne numery),
  napis w cudzysłowach - nazwa stacji
  liczba M - liczba wyjazdów z tej stacji
następnie M razy opis krawędzi:
  liczba T - numer stacji do której bezpośrednio ten wyjazd prowadzi
  liczba D - odległość taryfowa między tymi stacjami.

-----------------------------------
ZADANIE

Zapisz w Pascalu wybraną reprezentację grafów (zalecam 3. albo 4.). Napisz program wczytujący plik o formacie takim jak SIEC.DAT i, jeśli starczy czasu i zdrowia, wykorzystujący algorytm BFS (lub DFS) do znalezienia drogi między zadanymi stacjami.
Użytkownik może podać stacje przez numery. Program ma odpowiedzieć czy droga istnieje i jaka jest jej długość
- utrudnienie A - niech program wypisuje całą drogę, najlepiej nazwy stacji,
- utrudnienie B - niech znaleziona droga będzie najkrótszą.

Jeśli zadanie okaże się bardzo pracochłonne, nie wymagam jego dokończenia, lepiej robić zadania zaliczeniowe. Ale to zadanie o grafach może być bardzo kształcące i fajnie zobaczyć jak zacznie działać... :)

Patryk Czarnik