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