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