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