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