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
Ilustracja interaktywna przedstawia graf o połączeniach: 7, 3. 3, 2. 3, 1. 1, 4. 1, 5. 1, 6. 1, 0. 1. Wierzchołek oznaczony jako "3", 2. Krawędź łącząca wierzchołki "3" i "1", 3. Sąsiad wierzchołka "1".
Ilustracja interaktywna przedstawia graf o połączeniach: 7, 3. 3, 2. 3, 1. 1, 4. 1, 5. 1, 6. 1, 0. 1. Wierzchołek oznaczony jako "3", 2. Krawędź łącząca wierzchołki "3" i "1", 3. Sąsiad wierzchołka "1".
Ź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[].
Linia 1. int nazwa podkreślnik tablicy otwórz nawias kwadratowy zamknij nawias kwadratowy.
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.
Linia 1. pair otwórz nawias ostrokątny first przecinek second zamknij nawias ostrokątny nazwa podkreślnik pary.
pair<first, second> nazwa_pary
Linia 1. pair otwórz nawias ostrokątny int przecinek int zamknij nawias ostrokątny krawedz znak równości otwórz nawias klamrowy 4 przecinek 6 zamknij nawias klamrowy średnik.
pair<int, int> krawedz = {4, 6};
Typ pair zawiera dwa pola składowe: first i second, przechowujące odpowiednio pierwszy i drugi obiekt.
Linia 1. pair otwórz nawias ostrokątny int przecinek int zamknij nawias ostrokątny krawedz znak równości otwórz nawias klamrowy 4 przecinek 6 zamknij nawias klamrowy średnik.
Linia 2. cout otwórz nawias ostrokątny otwórz nawias ostrokątny krawedz kropka first otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów przecinek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny krawedz kropka second otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik.
Linia 3. prawy ukośnik prawy ukośnik wypisze w konsoli dwukropek.
Linia 4. prawy ukośnik prawy ukośnik 4 przecinek 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ę:
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
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Propozycja rozwiązania:
Linia 1. int wierzcholkiG otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy apostrof t apostrof przecinek apostrof s apostrof przecinek apostrof r apostrof przecinek apostrof q apostrof przecinek apostrof p apostrof przecinek apostrof u apostrof zamknij nawias klamrowy średnik.
Linia 2. pair otwórz nawias ostrokątny int przecinek int zamknij nawias ostrokątny krawedzieG otwórz nawias kwadratowy 9 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy otwórz nawias klamrowy apostrof t apostrof przecinek apostrof s apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof t apostrof przecinek apostrof q apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof t apostrof przecinek apostrof u apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof s apostrof przecinek apostrof p apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof s apostrof przecinek apostrof r apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof r apostrof przecinek apostrof u apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof r apostrof przecinek apostrof q apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof q apostrof przecinek apostrof p apostrof zamknij nawias klamrowy przecinek otwórz nawias klamrowy apostrof p apostrof przecinek apostrof u apostrof zamknij nawias klamrowy zamknij nawias klamrowy średnik.
struktura składająca się z niepustego zbioru wierzchołków oraz ze zbioru krawędzi; dla grafu zbiór wierzchołków oznaczamy (ang. verticies – wierzchołki), a zbiór krawędzi – (ang. edges – krawędzie); liczbę elementów zbioru oznaczamy literą , zaś liczbę elementów zbioru –
graf spójny
graf spójny
graf, w którym każda para wierzchołków połączona jest drogą
izomorfizm
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 jest izomorficzny z grafem , 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ź
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
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
stopień wierzchołka
liczba krawędzi incydentnych z danym wierzchołkiem (wychodzących z danego wierzchołka)
szablon
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
wierzchołek
inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf
klasa generyczna
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
para nieuporządkowana
zbiór złożony jedynie z dwóch różnych elementów:
ścieżka
ścieżka
skończony ciąg krawędzi, w którym wszystkie krawędzie są różne
droga
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)