Przeczytaj
W tej sekcji znajdziesz przykłady implementacji reprezentacji grafów nieskierowanych bez wag oraz skierowanych bez wag w języku Java. Reprezentacje te zostały przedstawione w e‑materiale teoretycznyme‑materiale teoretycznym, są to: macierz sąsiedztwa, lista sąsiedztwa, macierz incydencji.
Grafy nieskierowane
Macierz sąsiedztwa
Dany jest następujący graf spójny nieskierowany bez wag:

Macierz sąsiedztwa zaprezentowanego grafu nieskierowanego bez wag:

Napiszmy teraz program. Na potrzeby implementacji macierz sąsiedztwa będzie dwuwymiarową tablicą o wyrazach typu int
, o n
wierszach i n
kolumnach. Gdybyśmy chcieli rozpocząć od macierzy wypełnionej samymi zerami, wykorzystalibyśmy następujący aspekt języka Java:
Każda zmienna klasy, zmienna instancji lub składnik tablicy są inicjowane wartością domyślną podczas jej tworzenia. Dla typu int
wartością domyślną jest zero, czyli 0
.
Wystarczy zatem tylko zadeklarować operatorem new
dwuwymiarową tablicę o n
wierszach i n
kolumnach.
Dodawanie krawędzi wykonujemy za pomocą funkcji polaczWierzcholki()
, do której przekazujemy trzy argumenty: macierzSasiedztwa
oraz indeksy dwóch wierzchołków, które chcemy połączyć, czyli i
razem z j
.
Przykład użycia takiej reprezentacji przedstawiony jest poniżej. Metoda wypisz()
iteruje po każdym wierszu, a następnie po każdym wyrazie tego wiersza, wypisując macierz w konsoli. Ponieważ tablice w języku Java zawierają pole length
, nie trzeba w naszym przykładzie definiować nowej zmiennej n
przechowującej liczbę wierzchołków.
Wyjście programu:
Lista sąsiedztwa
Lista sąsiedztwa zaprezentowanego grafu nieskierowanego bez wag:

W języku Java listę sąsiadów danego wierzchołka można zaimplementować z użyciem klasy LinkedList
, która jest implementacją listy dwukierunkowej. LinkedList
to klasa generycznaklasa generyczna z parametrem typu, zatem przy deklaracji zmiennej tej klasy musimy określić rodzaj przechowywanych elementów. W omawianym przypadku będziemy przechowywać zmienne typu int
, więc deklaracja takiej listy sąsiadów będzie następująca:
Cała lista sąsiedztwa nie jest pojedynczą listą, lecz zestawem list sąsiadów każdego wierzchołka. Potrzebujemy zatem pewnego rodzaju kontenera na ten zestaw list.
Pomocna tu będzie kolekcja ArrayList
. Klasa ta reprezentowana przez interfejs java.util.list
pozwoli nam tworzyć tablice o zmiennym rozmiarze i to za jej pomocą zaimplementujemy listę sąsiedztwa. Jej główną przewagą nad klasyczną tablicą jest to, że programista nie musi przejmować się rozmiarem, jest ona bowiem automatycznie powiększana wraz z dodawaniem nowych elementów.
Podobnie jak LinkedList
, także ArrayList
jest klasą sparametryzowaną. Aby stworzyć listę tablicową o pojemności n
przechowującą elementy typu LinkedList<Integer>
, dodamy następująca deklarację:
Zmienna listaSasiedztwa
o pojemności n
została już zadeklarowana, ale nie zawiera jeszcze żadnej listy sąsiadów, musimy więc dla każdego wierzchołka stworzyć listę sąsiadów LinkedList
i dodać ją do listy sąsiedztwa. Elementy do listy tablicowej ArrayList
(podobnie jak LinkedList
) dodajemy za pomocą metody add()
. Nowy wyraz znajdzie się na końcu sekwencji.
Do elementów listy tablicowej ArrayList
nie dostaniemy się za pomocą nawiasów kwadratowych. Do tego celu ArrayList
ma zdefiniowaną metodę get()
. Aby uzyskać dostęp do elementu o indeksie i
, do metody przekażemy zmienną i
.
Pełen kod wykorzystujący opisaną implementację znajduje się poniżej. Do iteracji po każdym elemencie listy dwukierunkowej użyto pętli zasięgu, która przy każdym kroku przekazuje zmiennej j
wartość kolejnego elementu listy sąsiadów.
Wyjście programu:
Macierz incydencji
Macierz incydencji zaprezentowanego grafu nieskierowanego bez wag:

Macierz incydencji zdefiniujemy jako dwuwymiarową tablicę o n
wierszach i maxM
kolumnach. Zmienna maxM
jest równa maksymalnej liczbie krawędzi dla grafu o n
wierzchołkach. Jako że rozmiar macierzy incydencji zależy od liczby krawędzi, to w celu zapamiętania aktualnej liczby krawędzi zdefiniujemy nową zmienną m
. Wartość ta będzie wskazywała, ile kolumn macierzy ma zostać wyświetlonych lub w którym miejscu należy wstawić nową krawędź.
Na początku macierz będzie wypełniona zerami – nie ma potrzeby inicjowania tablicy. Dodawanie krawędzi odbywa się za pomocą funkcji polaczWierzcholki()
, do której przekazujemy trzy argumenty: macierzIncydencji
oraz indeksy dwóch wierzchołków, które chcemy połączyć, czyli i
razem z j
. Funkcja sprawdza, czy nie wykorzystaliśmy maksymalnej pojemności macierzy, a jeśli tak, to kończy swoje działanie. W przeciwnym wypadku następuje wpisanie jedynek odpowiednim wyrazom, po czym zmienna m
zostaje zwiększona o 1.
Pełen kod implementacji macierzy incydencji przedstawiony jest poniżej. Funkcja wypisz()
iteruje tylko do wyrazu o indeksie m - 1
, wypisując tym samym macierz o rozmiarze n
na m
.
Wyjście programu:
Grafy skierowane
Dany jest następujący graf spójny skierowany bez wag:

Macierz sąsiedztwa
Macierz sąsiedztwa zaprezentowanego grafu skierowanego bez wag:

Przejdźmy do implementacji programu.
Deklarujemy operatorem new
dwuwymiarową tablicę o n
wierszach i n
kolumnach.
Dodajemy krawędzie za pomocą funkcji polaczWierzcholki()
, do której przekazujemy trzy argumenty: macierzSasiedztwa
oraz indeksy dwóch wierzchołków, które chcemy połączyć, czyli i
razem z j
.
Zwróć uwagę na to, że w przypadku grafów skierowanych znaczenie ma kierunek krawędzi. Dodawana krawędź zaczyna się w wierzchołku i
, natomiast kończy w wierzchołku j
. Dlatego w przypadku macierzy sąsiedztwa element o indeksach [i][j]
przyjmuje wartość 1, natomiast element o indeksach [j][i]
przyjmuje wartość 0.
Zapoznajmy się z przykładem użycia takiej reprezentacji.
Wyjście programu:
Lista sąsiedztwa
Lista sąsiedztwa zaprezentowanego grafu skierowanego bez wag:

Implementujemy listę sąsiadów wierzchołka:
Ponieważ cała lista sąsiedztwa nie jest pojedynczą listą, a zestawem list, ponownie wykorzystamy kolekcję ArrayList
.
Tworzymy listę tablicową o pojemności n
przechowującą elementy typu LinkedList<Integer>
:
Dotychczas zadeklarowaliśmy zmienną listaSasiedztwa
o pojemności n
, nie zawiera ona jednak jeszcze żadnej listy sąsiadów. Dla każdego wierzchołka tworzymy listę sąsiadów LinkedList
i dodajemy ją do listy sąsiedztwa. Do listy tablicowej ArrayList
(podobnie jak LinkedList
) elementy dodajemy za pomocą metody add()
. Nowy wyraz znajdzie się na końcu sekwencji.
Aby dostać się do elementów listy tablicowej ArrayList
, zastosujemy metodę get()
. Aby uzyskać dostęp do elementu o indeksie i
, do metody przekażemy zmienną j
.
Element o indeksie i
to wierzchołek, w którym zaczyna się krawędź. Zmienna j
przechowuje informację na temat wierzchołka, w którym krawędź się kończy (zgodnie z jej kierunkiem).
Prześledźmy kod, w którym zastosowano opisaną implementację.
Wyjście programu:
Macierz incydencji
Macierz incydencji zaprezentowanego grafu skierowanego bez wag:

Definiujemy macierz incydencji jako dwuwymiarową tablicę o n
wierszach i maxM
kolumnach.
Początkowo macierz będzie wypełniona zerami, więc nie musimy inicjować tablicy.
Dodajemy krawędzie, używając funkcji polaczWierzcholki()
, do której przekazujemy trzy argumenty: macierzIncydencji
oraz indeksy dwóch wierzchołków, które chcemy połączyć, czyli i
razem z j
. Funkcja weryfikuje, czy nie wykorzystaliśmy maksymalnej pojemności macierzy. Jeśli tak – kończymy działanie funkcji. Jeśli nie, w przypadku tej reprezentacji, wierzchołkowi i
przypisujemy wartość 1 (tam krawędź się zaczyna), natomiast wierzchołkowi, w którym się kończy (zgodnie z kierunkiem krawędzi) przypisujemy wartość -1.
Przeanalizujmy kod implementacji macierzy incydencji.
Wyjście programu:
Słownik
struktura składająca się z niepustego zbioru wierzchołków oraz rodziny krawędzi; dla grafu G zbiór wierzchołków oznaczamy (ang. verticies – wierzchołki), a rodzinę krawędzi – (ang. edges – krawędzie); liczbę elementów zbioru oznaczamy literą ; liczbę elementów rodziny –
graf, którego nie można przedstawić w postaci sumy dwóch grafów
graf którego krawędzie mają przypisane wagi
nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków
relacja między wierzchołkami a łączącą je krawędzią grafu; mówimy, że dwa sąsiednie wierzchołki połączone pewną krawędzią są incydentne z tą krawędzią
właściwość grafów polegająca na tym, że między grafami występuje wzajemnie jednoznaczna odpowiedniość wierzchołków; liczba krawędzi łączących dane dwa wierzchołki jednego grafu jest równa liczbie krawędzi łączących odpowiadające im wierzchołki drugiego grafu
zestaw uporządkowanych list, gdzie lista o indeksie jest listą wszystkich sąsiadów wierzchołka
dwuwymiarowa tablica elementów (zwykle liczbowych), licząca wierszy i kolumn
macierz zerojedynkowa rozmiaru , dla której każda krawędź grafu musi mieć unikatowy indeks; wyraz jest równy , o ile krawędź o indeksie jest incydentna do wierzchołka
macierz zerojedynkowa rozmiaru , w której wyraz jest równy , jeśli wierzchołki oraz są sąsiednie, a w przeciwnym przypadku; macierz sąsiedztwa jest symetryczna dla grafów nieskierowanych
liczba krawędzi incydentnych z danym wierzchołkiem
klasa lub interfejs sparametryzowany względem typów podanych przy deklaracji; do określenia parametrów typu używamy nawiasów ostrych (<>
); typy generyczne umożliwiają napisanie ogólnej definicji, która działa z różnymi typami, pozwalając tym samym na ponowne użycie kodu bez konieczności definiowania nowych definicji klas lub interfejsu działających na innym typie zmiennych
wartość przypisana krawędzi grafu
element należący do zbioru wierzchołków