Przeczytaj

Struktura grafu

GrafgrafGraf jest strukturą składającą się z obiektów (wierzchołkówwierzchołekwierzchołków) oraz z powiązań między nimi (krawędzikrawędźkrawędzi). Zazwyczaj przedstawiany jest w formie diagramu jako zbiór punktów połączonych odcinkami, gdzie punkty przedstawiają wierzchołki, a odcinki – krawędzie grafu.

RSxiPQWNTHTjy

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Wierzchołki i krawędzie

Podczas implementacji potrzebna jest możliwość rozróżnienia wierzchołków. Osiągnąć to można, na przykład oznaczając poszczególne wierzchołki kolejnymi liczbami naturalnymi, zaczynając od 0. Przechowywać je będziemy w tablicy statycznej typu int[].

int nazwa_tablicy[]

W przypadku krawędzi wykorzystamy szablonszablonszablon struktury pair, który umożliwia przechowywanie dwóch obiektów jako pojedynczej jednostki. Dla naszej implementacji typem krawędzi będzie pair<int, int>. Przypiszmy zatem zmiennej krawedz wartość opisującą krawędź, która łączy wierzchołki 4 i 6:

Ważne!

Klasa pair pozwala traktować dwa obiekty jako pojedynczy obiekt. Obiekty mogą być różnego typu.

pair<first, second> nazwa_pary

pair<int, int> krawedz = {4, 6};

Typ pair zawiera dwa pola składowe: first i second, przechowujące odpowiednio pierwszy i drugi obiekt.

pair<int, int> krawedz = {4, 6};
cout << krawedz.first << ", " << krawedz.second << endl;
// wypisze w konsoli:
// 4, 6

Zbiór krawędzi może być pusty albo składać się z jednej lub więcej krawędzi – pary wierzchołków. Dlatego niezbędna będzie tablica statyczna przechowująca obiekty owej pary. Oto jak możemy zadeklarować tę tablicę:

pair<int, int> krawedzie[3] = {{4, 6}, {5, 7}, {1, 2}};

Na podstawie tablicy krawędzi może przedstawić również tablicę przechowującą numery wierzchołków:

int wierzcholki[] = {4, 6, 5, 7, 1, 2};

Graf opisany za pomocą poniższych tablic:

pair<int, int> krawedzie[3] = {{4, 6}, {5, 7}, {1, 2}};
int wierzcholki[] = {4, 6, 5, 7, 1, 2};

wyglądałby następująco:

R1aqQvQ1QyMEI

Ilustracja przedstawia trzy grafy o połączeniach: pierwszy 7, 5, drugi 4, 6, trzeci 1, 2. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 1

Jak nazywamy graf, którego nie wszystkie wierzchołki połączone są ze sobą krawędziami?

Przykład

W jaki sposób moglibyśmy za pomocą kodu zaprezentować graf zamieszczony na początku tej sekcji?

Zacznijmy od wierzchołków.

int wierzcholki[] = {7, 2, 3, 1, 4, 5, 6, 0};

Mamy do czynienia z grafem spójnym, więc jego wierzchołki połączone są krawędziami.

pair<int, int> krawedzie[7] = {{7, 3}, {2, 3}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {0, 1}};

Wierzchołki w zaprezentowanym grafie deklarujemy zatem za pomocą poniższych tablic:

int wierzcholki[] = {7, 2, 3, 1, 4, 5, 6, 0};
pair<int, int> krawedzie[7] = {{7, 3}, {2, 3}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {0, 1}};

Ćwiczenie 1

Dany jest graf G.

RdcdsO5lgdokK

Ilustracja przedstawia sześciokąt. Nad sześciokątem jest duża litera G. W każdym wierzchołku jest inna litera w okręgu: s, r, q, p, u, t. Pomiędzy okręgami biegną przeciwległe proste przecinające się w środku sześciokąta. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

RP7mshv0CoMuW

Słownik

graf

struktura składająca się z niepustego zbioru wierzchołków oraz ze zbioru krawędzi; dla grafu $G$ zbiór wierzchołków oznaczamy $V(G)$ (ang. verticies – wierzchołki), a zbiór krawędzi – $E(G)$ (ang. edges – krawędzie); liczbę elementów zbioru $V(G)$ oznaczamy literą $n$ , zaś liczbę elementów zbioru $E(G)$ – $m$

graf spójny

graf, w którym każda para wierzchołków połączona jest drogą

izomorfizm

właściwość grafów polegająca na tym, że 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; jeśli graf $G$ jest izomorficzny z grafem $H$ , to gdy jakieś dwa wierzchołki są połączone krawędzią w jednym z grafów, odpowiadające im wierzchołki w drugim grafie również łączy krawędź; izomorfizm grafów zachowuje takie własności jak: liczba wierzchołków, liczba krawędzi, stopnie wierzchołków, czy spójność grafu

krawędź

nieuporządkowana para (niekoniecznie różnych) elementów zbioru wierzchołków, tj. takich, które są ze sobą połączone; w reprezentacji graficznej jest to linia łącząca te wierzchołki; krawędź może łączyć ze sobą jeden wierzchołek (wtedy nazywana jest pętlą)

lista krawędzi

struktura przechowująca wszystkie krawędzie występujące w grafie; choć nazywana jest listą, w konkretnych językach programowania może być realizowana np. za pomocą tablicy

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem (wychodzących z danego wierzchołka)

szablon

konstrukcja, która generuje klasę lub funkcję podczas kompilacji na podstawie argumentów dostarczanych przez użytkownika dla parametrów szablonu; umożliwia definiowanie operacji klasy lub funkcji i pozwala programiście określić, na jakich konkretnie typach operacje te powinny być wykonywane

wierzchołek

inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf

klasa generyczna

klasa w języku Java pozwalająca stworzyć ogólną, uniwersalną klasę, która będzie wykonywała działania z różnymi typami danych, umożliwiając ponowne użycie kodu bez konieczności redefiniowania klasy dla każdego typu

para nieuporządkowana

zbiór złożony jedynie z dwóch różnych elementów: ${a, b}$

ścieżka

skończony ciąg krawędzi, w którym wszystkie krawędzie są różne

droga

ścieżka, w której wierzchołki są różne (z wyjątkiem ewentualnej równości wierzchołków pierwszego i ostatniego – mamy wtedy do czynienia ze szczególnym rodzajem drogi, drogą zamkniętą, tzw. cyklem)

Wprowadzenie

Film samouczek

Struktura grafu

Wierzchołki i krawędzie

Przykład

Słownik