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 za pomocą listy.
Linia 1. List otwórz nawias ostrokątny Wierzcholek zamknij nawias ostrokątny wierzcholki.
List<Wierzcholek> wierzcholki
Podobnie w przypadku krawędzi:
Linia 1. List otwórz nawias ostrokątny Krawedz zamknij nawias ostrokątny krawedzie.
List<Krawedz> krawedzie
Klasa grafu będzie wyglądać następująco:
Linia 1. class Graf otwórz nawias klamrowy.
Linia 2. private List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki średnik.
Linia 3. private List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie średnik.
Linia 5. public Graf otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 6. this kropka wierzcholki znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 7. this kropka krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 8. zamknij nawias klamrowy.
Linia 10. public Graf otwórz nawias okrągły List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki zamknij nawias okrągły otwórz nawias klamrowy.
Linia 11. this kropka wierzcholki znak równości wierzcholki średnik.
Linia 12. this kropka krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 13. zamknij nawias klamrowy.
Linia 15. public Graf otwórz nawias okrągły List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki przecinek List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie zamknij nawias okrągły otwórz nawias klamrowy.
Linia 16. this kropka wierzcholki znak równości wierzcholki średnik.
Linia 17. this kropka krawedzie znak równości krawedzie średnik.
Linia 18. zamknij nawias klamrowy.
Linia 20. public List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny getWierzcholki otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 21. return wierzcholki średnik.
Linia 22. zamknij nawias klamrowy.
Linia 24. public List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny getKrawedzie otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 25. return krawedzie średnik.
Linia 26. zamknij nawias klamrowy.
Linia 27. zamknij nawias klamrowy.
class Graf {
private List<Integer> wierzcholki;
private List<List<Integer>> krawedzie;
public Graf() {
this.wierzcholki = new ArrayList<>();
this.krawedzie = new ArrayList<>();
}
public Graf(List<Integer> wierzcholki) {
this.wierzcholki = wierzcholki;
this.krawedzie = new ArrayList<>();
}
public Graf(List<Integer> wierzcholki, List<List<Integer>> krawedzie) {
this.wierzcholki = wierzcholki;
this.krawedzie = krawedzie;
}
public List<Integer> getWierzcholki() {
return wierzcholki;
}
public List<List<Integer>> getKrawedzie() {
return krawedzie;
}
}
Podaliśmy w listach również typ danych, które będą za ich pomocą przechowywane.
Wierzchołki grafu reprezentowane będą liczbami naturalnymi.
Utworzony w ten sposób obiekt graf klasy Graf ma trzy różne wierzchołki oznaczone numerami 0, 1 oraz 2, jednak nie ma żadnych krawędzi:
By wyświetlić wierzchołki obiektu graf klasy Graf, wykorzystamy polecenie System.out.println:
Linia 1. public class Main otwórz nawias klamrowy.
Linia 2. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. Graf graf znak równości new Graf otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 4. System kropka out kropka println otwórz nawias okrągły graf kropka getWierzcholki otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 5. zamknij nawias klamrowy.
Linia 6. zamknij nawias klamrowy.
public class Main {
public static void main(String[] args) {
Graf graf = new Graf(Arrays.asList(0, 1, 2));
System.out.println(graf.getWierzcholki());
}
}
Każda krawędź reprezentowana jest przez dwuelementową listę zawierającą numery wierzchołków, które łączy.
Załóżmy, że nasz graf ma dwie krawędzie – jedna łączy wierzchołek 0 oraz 1, druga łączy wierzchołek 0 oraz 2.
Dodajmy do utworzonego obiektu krawędzie łączące wierzchołki:
Linia 1. public class Main otwórz nawias klamrowy.
Linia 2. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. Graf graf znak równości new Graf otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 4. System kropka out kropka println otwórz nawias okrągły graf kropka getWierzcholki otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 6. List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 7. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 8. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 2 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 10. graf znak równości new Graf otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 zamknij nawias okrągły przecinek krawedzie zamknij nawias okrągły średnik.
Linia 11. System kropka out kropka println otwórz nawias okrągły graf kropka getKrawedzie otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 12. zamknij nawias klamrowy.
Linia 13. zamknij nawias klamrowy.
public class Main {
public static void main(String[] args) {
Graf graf = new Graf(Arrays.asList(0, 1, 2));
System.out.println(graf.getWierzcholki());
List<List<Integer>> krawedzie = new ArrayList<>();
krawedzie.add(Arrays.asList(0, 1));
krawedzie.add(Arrays.asList(0, 2));
graf = new Graf(Arrays.asList(0, 1, 2), krawedzie);
System.out.println(graf.getKrawedzie());
}
}
Kod wyświetlający wierzchołki oraz krawędzie:
Linia 1. import java kropka util kropka ArrayList średnik.
Linia 2. import java kropka util kropka Arrays średnik.
Linia 3. import java kropka util kropka List średnik.
Linia 5. class Graf otwórz nawias klamrowy.
Linia 6. private List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki średnik.
Linia 7. private List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie średnik.
Linia 9. public Graf otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 10. this kropka wierzcholki znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 11. this kropka krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 12. zamknij nawias klamrowy.
Linia 14. public Graf otwórz nawias okrągły List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki zamknij nawias okrągły otwórz nawias klamrowy.
Linia 15. this kropka wierzcholki znak równości wierzcholki średnik.
Linia 16. this kropka krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 17. zamknij nawias klamrowy.
Linia 19. public Graf otwórz nawias okrągły List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki przecinek List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie zamknij nawias okrągły otwórz nawias klamrowy.
Linia 20. this kropka wierzcholki znak równości wierzcholki średnik.
Linia 21. this kropka krawedzie znak równości krawedzie średnik.
Linia 22. zamknij nawias klamrowy.
Linia 24. public List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny getWierzcholki otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 25. return wierzcholki średnik.
Linia 26. zamknij nawias klamrowy.
Linia 28. public List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny getKrawedzie otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 29. return krawedzie średnik.
Linia 30. zamknij nawias klamrowy.
Linia 31. zamknij nawias klamrowy.
Linia 33. public class Main otwórz nawias klamrowy.
Linia 34. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy.
Linia 35. Graf graf znak równości new Graf otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 36. System kropka out kropka println otwórz nawias okrągły graf kropka getWierzcholki otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 38. List otwórz nawias ostrokątny List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 39. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 40. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 2 zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 42. graf znak równości new Graf otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 zamknij nawias okrągły przecinek krawedzie zamknij nawias okrągły średnik.
Linia 43. System kropka out kropka println otwórz nawias okrągły graf kropka getKrawedzie otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 44. zamknij nawias klamrowy.
Linia 45. zamknij nawias klamrowy.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Graf {
private List<Integer> wierzcholki;
private List<List<Integer>> krawedzie;
public Graf() {
this.wierzcholki = new ArrayList<>();
this.krawedzie = new ArrayList<>();
}
public Graf(List<Integer> wierzcholki) {
this.wierzcholki = wierzcholki;
this.krawedzie = new ArrayList<>();
}
public Graf(List<Integer> wierzcholki, List<List<Integer>> krawedzie) {
this.wierzcholki = wierzcholki;
this.krawedzie = krawedzie;
}
public List<Integer> getWierzcholki() {
return wierzcholki;
}
public List<List<Integer>> getKrawedzie() {
return krawedzie;
}
}
public class Main {
public static void main(String[] args) {
Graf graf = new Graf(Arrays.asList(0, 1, 2));
System.out.println(graf.getWierzcholki());
List<List<Integer>> krawedzie = new ArrayList<>();
krawedzie.add(Arrays.asList(0, 1));
krawedzie.add(Arrays.asList(0, 2));
graf = new Graf(Arrays.asList(0, 1, 2), krawedzie);
System.out.println(graf.getKrawedzie());
}
}
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> wierzcholki = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7);
List<List<Integer>> krawedzie = new ArrayList<>();
krawedzie.add(Arrays.asList(7, 3));
krawedzie.add(Arrays.asList(2, 3));
krawedzie.add(Arrays.asList(3, 1));
krawedzie.add(Arrays.asList(4, 1));
krawedzie.add(Arrays.asList(5, 1));
krawedzie.add(Arrays.asList(6, 1));
krawedzie.add(Arrays.asList(0, 1));
Graf graf = new Graf(wierzcholki, krawedzie);
}
}
Ć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
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. public class Main otwórz nawias klamrowy.
Linia 2. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. List otwórz nawias ostrokątny Character zamknij nawias ostrokątny wierzcholki znak równości Arrays kropka asList otwórz nawias okrągły apostrof p apostrof przecinek apostrof q apostrof przecinek apostrof r apostrof przecinek apostrof s apostrof przecinek apostrof t apostrof przecinek apostrof u apostrof zamknij nawias okrągły średnik.
Linia 5. List otwórz nawias ostrokątny List otwórz nawias ostrokątny Character zamknij nawias ostrokątny zamknij nawias ostrokątny krawedzie znak równości new ArrayList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik.
Linia 6. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof t apostrof przecinek apostrof s apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 7. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof t apostrof przecinek apostrof q apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 8. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof t apostrof przecinek apostrof u apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 9. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof s apostrof przecinek apostrof p apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 10. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof s apostrof przecinek apostrof r apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 11. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof r apostrof przecinek apostrof u apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 12. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof r apostrof przecinek apostrof q apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 13. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof q apostrof przecinek apostrof p apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 14. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły apostrof p apostrof przecinek apostrof u apostrof zamknij nawias okrągły zamknij nawias okrągły średnik.
Linia 16. Graf graf znak równości new Graf otwórz nawias okrągły wierzcholki przecinek krawedzie zamknij nawias okrągły średnik.
Linia 17. zamknij nawias klamrowy.
Linia 18. zamknij nawias klamrowy.
public class Main {
public static void main(String[] args) {
List<Character> wierzcholki = Arrays.asList( 'p', 'q', 'r', 's', 't', 'u' );
List<List<Character>> krawedzie = new ArrayList<>();
krawedzie.add(Arrays.asList('t', 's'));
krawedzie.add(Arrays.asList('t', 'q'));
krawedzie.add(Arrays.asList('t', 'u'));
krawedzie.add(Arrays.asList('s', 'p'));
krawedzie.add(Arrays.asList('s', 'r'));
krawedzie.add(Arrays.asList('r', 'u'));
krawedzie.add(Arrays.asList('r', 'q'));
krawedzie.add(Arrays.asList('q', 'p'));
krawedzie.add(Arrays.asList('p', 'u'));
Graf graf = new Graf(wierzcholki, krawedzie);
}
}
Słownik
droga
droga
ciąg wierzchołków, w którym wszystkie wyrazy (z wyjątkiem pierwszego i ostatniego, które mogą być równe) są różne
graf
graf
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
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
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ą)
para nieuporządkowana
para nieuporządkowana
zbiór złożony jedynie z dwóch różnych elementów:
stopień wierzchołka
stopień wierzchołka
liczba krawędzi incydentnych z danym wierzchołkiem
wierzchołek
wierzchołek
inaczej: punkt, węzeł; element niepustego zbioru, który wraz ze zbiorem krawędzi tworzy graf