ALG$8

248

RozdziałłO. Elementy algorytmiki gratów

10.2.Sposoby reprezentacji grafów

Poznane uprzednio struktury danych, takie jak tablice, listy i drzewa dobrze nadają się do reprezentowania grafów. Dwie reprezentacje można uznać jednak za dominujące: przy pomocy tablicy dwuwymiarowej i tzw. słownika węzłów.

Graf może być reprezentowany przy użyciu tablicy dwuwymiarowej, jeśli umów imy się, że wiersze będą oznaczały węzły początkowe krawędzi grafu, a kolumny ich _;we^lv_/^z\!Źficwe~.Rr7ż'/?Jr.vsij^,OTrtc«i'rvⁿg?f.^,T«Tł'_ifsWi^liW’u¹Pu--^,."tnu-że być przedstawiony w postaci tablicy z rysunku 10 - 4.

Jedynka na pozycji (x, y) oznacza, że pomiędzy węzłami x i y istnieje krawędź skierowana w stronę y. W każdym innym przypadku tablica będzie zawierała na przykład zero.

Zauważmy, że reprezentacja tablicowa ma jedną istotną zaletą: jest bardzo prosta do implementacji programowej w dowolnym w zasadzie języku programowania, a ponadto korzystanie z niej nie jest trudne. Wada: jedynie grafy o ustalonej z góry liczbie węzłów mogą być łatwo reprezentowane w postaci tablic.

Aby przedstawić graf o liczbie węzłów, która może ulegać zmianie w trakcie wykonywania się programu, należy użyć np. reprezentacji przy pomocy słownika węzłów.

Słownik węzłów może dotyczyć dwóch typów' węzłów: następników (węzłów odchodzących) lub poprzedników (węzłów dochodzących) od danego węzła. Idea jest przedstaw iona na rysunku 10-5.

Słownik jest zwykłą tablicą wskaźników do list węzłów, odpowiednio odchodzących (a) lub dochodzących (b) do danego węzła przy pomocy krawędzi. Niektóre algorytmy dotyczące grafów potrzebują właśnie tego typu informacji, stąd celowość dysponowania taką reprezentacją. Biorąc pod uwagę, że słownik węzłów'jest łatwo implcmcntowalny w postaci listy list, znika nam automatycznie problem napotkany przy reprezentacji tablicowej — ilość węzłów grafu może być w zasadzie nieograniczona.