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 za pomocą listy.

List<Wierzcholek> wierzcholki

Podobnie w przypadku krawędzi:

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:

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:

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());
    }
}

Wynik jego działania:

[0, 1, 2] // wierzchołki
[[0, 1], [0, 2]] // krawędzie

Graf opisany za pomocą poniższej klasy:

public class Main {
    public static void main(String[] args) {
        List<Integer> wierzcholki = Arrays.asList(1, 2, 4, 5, 6, 7);

        List<List<Integer>> krawedzie = new ArrayList<>();
        krawedzie.add(Arrays.asList(7, 5));
        krawedzie.add(Arrays.asList(4, 6));
        krawedzie.add(Arrays.asList(1, 2));

        Graf graf = new Graf(wierzcholki, krawedzie);
    }
}

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.

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);

        Graf graf = new Graf(wierzcholki, krawedzie);
    }
}

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

Linia 1. import java kropka util kropka Arrays średnik. Linia 2. import java kropka util kropka ArrayList średnik. Linia 3. import java kropka util kropka List średnik. Linia 5. public class Main otwórz nawias klamrowy. Linia 6. 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 7. List otwórz nawias ostrokątny Integer zamknij nawias ostrokątny wierzcholki znak równości Arrays kropka asList otwórz nawias okrągły 0 przecinek 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 zamknij nawias okrągły średnik. Linia 9. 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 10. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 7 przecinek 3 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 2 przecinek 3 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 3 przecinek 1 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 4 przecinek 1 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 5 przecinek 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 15. krawedzie kropka add otwórz nawias okrągły Arrays kropka asList otwórz nawias okrągły 6 przecinek 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 16. 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 18. Graf graf znak równości new Graf otwórz nawias okrągły wierzcholki przecinek krawedzie zamknij nawias okrągły średnik. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy.

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

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

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

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

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ź

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

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

stopień wierzchołka

liczba krawędzi incydentnych z danym wierzchołkiem

wierzchołek

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

Wprowadzenie

Prezentacja multimedialna

Struktura grafu

Wierzchołki i krawędzie

Przykład

Słownik