Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Prednáška 33

Z Programovanie
Prejsť na: navigácia, hľadanie

Organizačné poznámky

Úlohy, projekt

  • DÚ16 (JavaFX) odovzdávajte do štvrtka 22:00
    • Väčšia úloha, nenechávať si na poslednú chvíľu (tiež dobrý tréning na skúšku)
  • Na začiatku budúceho týždňa zverejníme poslednú DÚ (na grafy)
  • Do stredy 2.5. si môžete vybrať tému nepovinného projektu

Prednášky a cvičenia v najbližšom čase

  • Tento týždeň iba prednáška, začíname novú tému, grafy
  • Zvyšné tri týždne prednášky aj cvičenia v normálnom termíne
  • Posledná rozcvička bude na cvičeniach 9.5.

Záverečný test

  • Posledný piatok semestra 18.5. o 13:00
  • Prípadné konflikty nám dajte vedieť čím skôr

Študentská vedecká konferencia

  • V stredu dekanské voľno kvôli študentskej vedeckej konferencii, odporúčame ísť si pozrieť aspoň niektoré prednášky (program)
  • Študenti prezentujú výsledky svojho výskumu
  • Hlavne diplomovky a doktorandi, ale aj bakalárske práce prípadne iné projekty
  • Na konferencii resp. na posteroch zistíte, čo robia školitelia, môže vám to pomôcť nájsť si školiteľa bakalárky, príp. aj ročníkového projektu
  • Tiež hľadáme dobrovoľníkov, ktorí pomôžu s organizačným zabezpečením

Úvod

  • Zvyšok semestra sa budeme venovať práci s grafmi
  • Grafy poznáte z predmetu Úvod do kombinatoriky a teórie grafov
  • Ďalšie algoritmy pre grafy v druhom ročníku na predmete Tvorba efektívnych algoritmov
  • Ďalšia teória grafov + nejaké algoritmy povinne voliteľný predmet pre tretí ročník Teória grafov

Príklady využitia grafov

  • Mapa, cestná sieť: vrcholy sú križovatky, mestá, obce, hrany sú cesty (podobne železnice, letecká sieť, ulice v rámci mesta ...)
  • Počítačové siete, elektrické obvody, siete potrubí
  • Web: vrcholy sú webstránky, hrany sú odkazy (podobne napríklad vedecké články a citácie medzi nimi)
  • Sociálne siete: vzťahy, kontakty medzi ľudmi, šírenie správ
  • Závislosti medzi činnosťami: ak máme vykonať niekoľko činností, ale niektoré sa dajú vykonať iba ak sú iné už hotové, ako ich usporiadať
  • Preferencie: napr. pri tvorbe rozvrhu sa určitý predmet môže konať len v určité časy, môžeme spájať hranou predmety a časy

Anglická terminológia:

  • graf = graph, vrchol = vertex (mn.č. vertices), hrana = edge

Reprezentácia grafov

Na dnešnej prednáške budeme uvažovať neorientovaný graf s vrcholmi očíslovanými 0,1,...,n-1.

  • Príklad: V={0,...,6}, E={{0,5},{1,2},{2,3},{1,3},{3,4}}

Do akých dátových štruktúr takýto graf uložíme?

  • V našom prípade množinu vrcholov reprezentujeme jednoducho počtom vrcholov n, zostáva uložiť hrany

Zoznam hrán

  • Najjednoduchšia reprezentácia je zoznam hrán
  • Vytvoríme si pomocnú triedu pre hranu, ktorá obsahuje čísla jej koncových vrcholov
  • Všetky hrany uložíme do poľa alebo spájaného zoznamu (ArrayList, LinkedList)
  • Takáto reprezentácia sa väčšinou nepoužíva, lebo je neefektívna
(0,5), (1,2), (2,3), (1,3), (3,4)

Matica susednosti (adjacency matrix)

  • Matica nxn napr typu boolean
  • Políčko a[i][j]=true ak {i,j} je hrana
  • Pre neorientovaný graf symetrická matica
   0 1 2 3 4 5 6
0  F F F F F T F
1  F F T T F F F
2  F T F T F F F
3  F T T F T F F
4  F F F T F F F
5  T F F F F F F
6  F F F F F F F

Zoznamy susedov (adjacency lists)

  • Pre každý vrchol zoznam jeho susedov
  • Uložíme ako pole potrebnej veľkosti alebo spájaný zoznam (ArrayList, LinkedList)
0: 5
1: 2,3
2: 1,3
3: 1,2,4
4: 3
5: 0
6:

Graf ako abstraktný dátový typ: Interface Graph

  • Ukážeme si konkrétne implementácie pre maticu a zoznamy susedov, potrebujeme však vedieť, aké operácie by mal graf poskytovať.
  • Tu je jednoduché rozhranie pre graf, do ktorého vieme pridávať hrany, testovať či hrana existuje a prechádzať cez susedov určitého vrcholu.
/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}
  • adjVertices vráti Iterable, čo je rozhranie (interface) s jedinou predpísanou metódou iterator(), ktorá vráti iterátor cez ten istý typ
  • Objekty typu Iterable sa dajú použiť vo for-cykle typu for(int v : g.adjVertices(u))

Príklad použitia: vypísanie grafu v poradí počet vrcholov, počet hrán a potom zoznam hrán, každá daná koncovými vrcholmi:

    /** Graph g vypíše do výstupného streamu */
    static void printGraph(Graph g, PrintStream out) {
        int n = g.getNumberOfVertices();
        out.println(n + " " + g.getNumberOfEdges());
        for (int u = 0; u < n; u++) {
            for(int v : g.adjVertices(u)) {
                if (u < v) {  // kvoli symetrii v neorientovaných grafoch
                    out.println(u + " " + v);
                }
            }
        }
    }

Napr. pre graf vyššie

7 5
0 5
1 2
1 3
2 3
3 4

Implementácia pomocou zoznamov susedov: Trieda AdjListsGraph

  • Pre každý vrchol si udržiavame zoznam susedných vrcholov v ArrayListe
  • Ako iterátor cez susedov použijeme jednoducho iterátor z ArrayListu
/** Trieda reprezentujúca neorientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return adjLists.size();
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(from);
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
	// vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex)); 
    }
}

Implementácia pomocou matice susednosti: Trieda AdjMatrixGraph

  • V konštruktore vyrobíme maticu vyplnenú false
  • O niečo zložitejšia metóda adjVertices
    • Dal by sa spraviť aj iterátor vlastnou triedou bez použitia pomocného poľa
/** Trieda reprezentujúca neorientovaný graf pomocou matice susednosti. */
class AdjMatrixGraph implements Graph {

    /** Matica susednosti */
    private boolean[][] matrix;
    /** Počet hrán grafu */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjMatrixGraph(int numVertices) {
        matrix = new boolean[numVertices][numVertices];
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                matrix[i][j] = false;
            }
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return matrix.length;
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        if (existsEdge(from, to)) { // nepridava existujuce hrany
            return false;
        }
        matrix[from][to] = true;  //prida hranu v oboch smeroch
        matrix[to][from] = true;
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return matrix[from][to];
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        // vytvori pomocne pole a,
        // vlozi do neho vsetkych susedov 
	// a vrati ho ako Iterable obaleny aby sa nedal menit
        ArrayList<Integer> a = new ArrayList<Integer>();
        for (int i = 0; i < matrix[vertex].length; i++) {
            if (matrix[vertex][i]) {
                a.add(i);
            }
        }
        return Collections.unmodifiableList(a);
    }
}

Vytvorenie grafu

  • Vytvoríme prázdny graf s určitým počtom vrcholov, po jednom pridávame hrany
    /** Zo scannera načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov.
     * Ak je matrix true, uloží ho ako AdjMatrixGraph,
     * inak ako AdjListsGraph. */
    static Graph readGraph(Scanner s, boolean matrix) {
        int n = s.nextInt();
        int m = s.nextInt();
        Graph g;
        if (matrix) {
            g = new AdjMatrixGraph(n);
        } else {
            g = new AdjListsGraph(n);
        }
        for (int i = 0; i < m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            g.addEdge(u, v);
        }
        return g;
    }

Porovnanie reprezentácií

  • Majme graf s n vrcholmi a m hranami
  • Počet hrán m môže byť od 0 po n(n-1)/2
  • Vyjadríme čas rôznych operácií v O-notácii:
    • O(1): robíme len konštantný počet operácií bez ohľadu na veľkosť grafu
    • O(n): čas operácie rastie v najhoršom prípade lineárne s počtom vrcholov grafu
    • O(m): čas operácie rastie v najhoršom prípade lineárne s počtom hrán grafu
    • O(n^{2}): čas operácie rastie v najhoršom prípade kvadraticky s počtom vrcholov grafu
  • Väčšinou máme viac hrán ako vrcholov, takže O(1) je lepšie ako O(n), to je lepšie ako O(m) a to je lepšie O(n^{2})
Zoznam hrán Matica susednosti Zoznamy susedov
Pamäť O(m) O(n^{2}) O(n+m)
Vytvoriť graf bez hrán O(1) O(n^{2}) O(n)
addEdge O(1) O(1) O(1)
existsEdge O(m) O(1) O(n)
Prejdenie susedov vrchola O(m) O(n) O(stupeň)
Výpis grafu pomocou adjVertices O(nm) O(n^{2}) O(n+m)
  • Matica susednosti
    • Rýchla operácia existsEdge
    • Ak je graf riedky (málo hrán), zaberá zbytočne veľa pamäte a dlho trvá prejdenie susedov vrchola
  • Zoznamy susednosti
    • Vhodný aj pre riedke grafy
    • Dlho trvá nájdenie konkrétnej hrany, ale všetkých susedov vrchola vieme prejsť rýchlo
    • Najvhodnejšia reprezentácia na väčšinu algoritmov, ktoré uvidíme

Poznámky a obmeny

Orientované grafy

  • Ak v metóde addEdge pridáme hranu iba jedným smerom, dostaneme orientovaný graf
  • adjIterator vráti iterátor cez vychádzajúce hrany

Grafy s násobnými hranami

  • AdjMatrixGraph nepovoľuje násobné hrany
    • Ak chceme prirobiť, museli by sme v matici mať int-y vyjadrujúce násobnosť hrany
  • AdjListsGraph nekontroluje násobnosť hrany, dovoľuje opakovanie
    • Kontrola násobnosti by dlho trvala - pri addEdge by sme museli pozrieť, či už v poli nie je

Ohodnotené grafy

  • V grafe si pre jednotlivé vrcholy a hrany môžeme chcieť pamätať ďalšie dáta
  • Napr. ak modelujeme cestnú sieť, hrana môže mať určitú dĺžku
  • Vrcholy môžu mať mená, súradnice a pod.
  • Nabudúce pridáme takéto dáta do implementácie

Dynamické grafy

  • Náš graf možno meniť len pridaním hrán
  • V grafe môžeme chcieť robiť aj iné zmeny
    • Mazanie hrán by sa ľahko doplnilo, rýchle pre maticu, pomalšie pre zoznamy susedov
    • Pridávanie a mazanie vrcholov ťažšie -- potrebujeme číslovanie 0..n-1
  • Neskôr si ukážeme všeobecnejšiu štruktúru, ktorá to umožňuje

Súvislosť grafu, prehľadávanie do hĺbky (depth-first search, DFS)

  • Zameriame sa na zisťovanie, či sú dva vrcholy spojené v grafe cestou, t.j. či sú v tom istom komponente súvislosti (v neorientovanom grafe)
  • Napr. vrchol 1 je v komponente súvislosti s vrcholmi 2,3,4
  • Použijeme prehľadávanie do hĺbky, podobné ako sme použili na vyfarbovanie súvislých oblastí v matici (ostrovy)
    • Mapu ostrovov môžeme zapísať ako graf, pričom každé políčko ostrovu bude vrchol a dve políčka budú spojené hranou, ak spolu susedia
    • Ostrovy sú potom komponenty súvislosti

Existuje cesta z u do v?

  • Poďme teda zisťovať, či sú u a v v tom istom komponente
  • Rekurzívne prehľadávame začínajúc od vrcholu u
  • Vytvoríme si pole booleanov visited, v ktorom si značíme už navštívené vrcholy
  • Z každého vrcholu rekurzívne prehľadáme zatiaľ nenavštívených susedov
   /** Pomocná metóda pre metódu connected.
     * Dostane graf g, vrchol vertex
     * a pole s poznačenými navštívenými vrcholmi, pričom
     * visited[vertex] by malo byť false.
     * Rekurzívne prehľadá nenavštívené vrcholy, ktoré sa z
     * vrcholu vertex dajú dosiahnuť. */
    static void search(Graph g, int vertex, boolean[] visited) {
        visited[vertex] = true;
        for(int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
            if (!visited[neighbor]) {
                search(g, neighbor, visited); // navstivime ho rekurzivne
            }
        }
    }

    /** Metóda, ktorá zistí, či sú vrcholy from a to v grafe g
     * spojené cestou. */
    static boolean connected(Graph g, int from, int to) {
        // vytvor pole visited vyplnené false
        boolean[] visited = new boolean[g.getNumberOfVertices()];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
        search(g, from, visited); // zavolaj rekurziu
        return visited[to];       // dostali sme sa do vrchola to?
    }

Hľadanie komponentov súvislosti

  • Ak by sme chceli testovať spojenie medzi veľa dvojicami vrcholov, oplatí sa nám nájsť komponenty súvislosti v celom grafe naraz.
  • Komponenty očísľujeme 0,1,...,k-1. Pre každý vrchol máme v poli číslo jeho komponentu.
  • Potom dva vrcholy sú spojené cestou práve vtedy, keď majú rovnaké číslo komponentu.
  • Toto robí nasledujúca trieda.
/** Trieda obsahujúca rozdelenie vrcholov grafu do komponentov súvislosti */
class Components {

    /** Pre každý vrchol číslo jeho komponentu 0..počet komponentov-1 */
    private int[] componentId;
    /** počet komponentov grafu */
    private int numComponents;
    /** samotný graf */
    private Graph g;

    /** Konštruktor, ktorý dostane graf a prehľadávaním do hĺbky
     * hľadá komponenty súvislosti */
    public Components(Graph g) {
        this.g = g;  // uloz graf
        numComponents = 0;  // inicializuj pocet komponentov
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        // vytvor pole cisel komponentov a inicializuj na -1 - nevyfarbene
        componentId = new int[n];
        for (int i = 0; i < n; i++) {
            componentId[i] = -1;
        }
        // prechadzaj cez vrcholy a ak najdes nevyfarbeny, spusti prehladavanie
        for (int i = 0; i < n; i++) {
            if (componentId[i] == -1) {
                search(i, numComponents); // vyfarbi cislom numComponents
                numComponents++;          // zvys numComponents
            }
        }
    }

    /** Pomocná rekurzívna metóda používaná v konštruktore na vyfarbenie
     * jedného komponentu číslom id. */
    private void search(int vertex, int id) {
        componentId[vertex] = id;
        for (int neighbor : g.adjVertices(vertex)) {
            if (componentId[neighbor] == -1) {
                search(neighbor, id); // navstivime ho rekurzivne
            }
        }
    }

    /** Vráti true ak vrcholy from a to sú v tom istom komponente */
    public boolean areConnected(int from, int to) {
        return componentId[from] == componentId[to];
    }

    /** Vráti počet komponentov grafu */
    public int getNumberOfComponents() {
        return numComponents;
    }
}
  • Čas výpočtu pri použití zoznamov susedov je O(n+m)
  • Vedeli by sme triedu obohatiť aj o iterovanie cez vrcholy v jednotlivých komponentoch

Príklad použitia prehľadávania do hĺbky: valec lesom

  • Ukážeme si trochu netradičný príklad, v ktorom sa dajú grafy a prehľadávanie použiť
  • Máme daný obdĺžnikový pozemok obohnaný plotom, na ktorom rastú stromy, ktoré si predstavíme ako body rovine
  • Pri západnom okraji pozemku stojí valec s polomerom r (t.j. v rovine si ho predstavíme ako kruh), pričom pri západnej strane plotu je dosť miesta, aby popri nej valec prešiel od severu na juh
  • Cieľom je zistiť, či sa valec dá pretlačiť pomedzi stromy na východnú stranu pozemku

Na prvý pohľad geometrická úloha sa prevedie na grafovú takto:

  • Vytvoríme vrcholy S a J reprezentujúce severnú a južnú stranu pozemku
  • Vytvoríme tiež vrchol pre každý strom
  • Vrcholy pre dva stromy spojíme hranou, ak sú bližšie ako 2r, t.j. valec sa medzi ne neprepchá
  • Podobne vrchol pre strom spojíme hranou s vrcholom S alebo J, ak je k príslušnému okraju pozemku bližšie ako 2r.
  • Ak S a J sú v tom istom komponente súvislosti, valec nie je možné cez les prepchať, lebo existuje lomená čiara spájajúca stromy na ceste z S do J, cez ktorú valec nevie prejsť
  • Ak S a J nie sú v tom istom komponente súvislosti, valec môžeme posúvať po južnej strane komponentu obsahujúceho vrchol S
  • Na odpoveď, či sa dá valec presunúť lesom, teda stačí spustiť connected(g,S,J).

Zhrnutie

  • Grafy sa používajú na veľa problémov
  • Reprezentujeme ich ako zoznamy susedov, prípadne ako maticu susednosti
  • V neorientovanom grafe vieme prehľadávaním do hĺbky nájsť komponenty súvislosti
  • Ako je to v orientovaných grafoch?
  • Celý program (vrátane prehľadávania do šírky z ďalšej prednášky) pozri nižšie

Zdrojový kód programu, grafy

Program k prednáškam: Prednáška 33 a Prednáška 34

  • dve reprezentácie grafu, prehľadávanie do hĺbky a do šírky
package prog;

import java.io.*;
import java.util.*;

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

/** Trieda reprezentujúca neorientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return adjLists.size();
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v oboch smeroch
        adjLists.get(to).add(from);
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
	// vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex)); 
    }
}

/** Trieda reprezentujúca neorientovaný graf pomocou matice susednosti. */
class AdjMatrixGraph implements Graph {

    /** Matica susednosti */
    private boolean[][] matrix;
    /** Počet hrán grafu */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjMatrixGraph(int numVertices) {
        matrix = new boolean[numVertices][numVertices];
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                matrix[i][j] = false;
            }
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return matrix.length;
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        if (existsEdge(from, to)) { // nepridava existujuce hrany
            return false;
        }
        matrix[from][to] = true;  //prida hranu v oboch smeroch
        matrix[to][from] = true;
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return matrix[from][to];
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        // vytvori pomocne pole a,
        // vlozi do neho vsetkych susedov 
	// a vrati ho ako Iterable obaleny aby sa nedal menit
        ArrayList<Integer> a = new ArrayList<Integer>();
        for (int i = 0; i < matrix[vertex].length; i++) {
            if (matrix[vertex][i]) {
                a.add(i);
            }
        }
        return Collections.unmodifiableList(a);
    }
}

/** Trieda obsahujúca rozdelenie vrcholov grafu do komponentov súvislosti */
class Components {

    /** Pre každý vrchol číslo jeho komponentu 0..počet komponentov-1 */
    private int[] componentId;
    /** počet komponentov grafu */
    private int numComponents;
    /** samotný graf */
    private Graph g;

    /** Konštruktor, ktorý dostane graf a prehľadávaním do hĺbky
     * hľadá komponenty súvislosti */
    public Components(Graph g) {
        this.g = g;  // uloz graf
        numComponents = 0;  // inicializuj pocet komponentov
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu
        // vytvor pole cisel komponentov a inicializuj na -1 - nevyfarbene
        componentId = new int[n];
        for (int i = 0; i < n; i++) {
            componentId[i] = -1;
        }
        // prechadzaj cez vrcholy a ak najdes nevyfarbeny, spusti prehladavanie
        for (int i = 0; i < n; i++) {
            if (componentId[i] == -1) {
                search(i, numComponents); // vyfarbi cislom numComponents
                numComponents++;          // zvys numComponents
            }
        }
    }

    /** Pomocná rekurzívna metóda používaná v konštruktore na vyfarbenie
     * jedného komponentu číslom id. */
    private void search(int vertex, int id) {
        componentId[vertex] = id;
        for (int neighbor : g.adjVertices(vertex)) {
            if (componentId[neighbor] == -1) {
                search(neighbor, id); // navstivime ho rekurzivne
            }
        }
    }

    /** Vráti true ak vrcholy from a to sú v tom istom komponente */
    public boolean areConnected(int from, int to) {
        return componentId[from] == componentId[to];
    }

    /** Vráti počet komponentov grafu */
    public int getNumberOfComponents() {
        return numComponents;
    }
}

/** Trieda, ktorá reprezentuje najkratšie cesty a vzdialenosti
 * z jedného vrchola do ostatných. */
class ShortestPaths {

    /** Graf, v ktorom počítame cesty */
    private Graph g;
    /** Štartovací vrchol, z ktorého rátame najkratšie cesty */
    private int start;
    /** Pre každý vrchol v grafe vzdialenosť od startu
     * alebo -1 ak je v inom komponente. */
    private int[] dist;
    /** Pre každý vrchol u predchádzajúci vrchol na ceste zo start do u */
    private int[] prev;

    /** Konštruktor, ktorý dostane graf a štartovací vrchol 
     * a nájde najkratšie cesty */
    public ShortestPaths(Graph g, int start) {
        this.g = g;
        this.start = start;
        int n = g.getNumberOfVertices();
        // inicializacia poli - vyplnime -1
        dist = new int[n];
        prev = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = -1;
            prev[i] = -1;
        }

        // prehladavanie do sirky
        // vytvorime rad a vlozime do neho startovaci vrchol
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.addLast(start);
        dist[start] = 0;  // sam od seba ma vzdialenost 0

        while (!queue.isEmpty()) {
            // vyberieme prvok na zaciatku radu
            int vertex = queue.removeFirst();
            // prejdeme cez jeho susedov a ak este neboli navstiveni
            // urcime im vzdialenost a pridame ich do radu
            for (int neighbor : g.adjVertices(vertex)) {
                if (dist[neighbor] < 0) {
                    dist[neighbor] = dist[vertex] + 1;
                    prev[neighbor] = vertex;
                    queue.addLast(neighbor);
                }
            }
        }
    }

    /** Je vrchol vertex spojený so štartovacím vrcholom? */
    public boolean isConnected(int vertex) {
        return dist[vertex] >= 0;
    }

    /** Vráti vzdialenosť vrcholu vertex od štartovacieho vrcholu.
     * Ak sú v rôznych komponentoch, vráti -1. */
    public int distance(int vertex) {
        return dist[vertex];
    }

    /** Vráti najkratšiu cestu zo štartovacieho vrcholu
     * do vrcholu vertex (postupnosť vrcholov, cez ktoré cesta ide).
     * Ak sú v rôznych komponentoch, vráti null. */
    public int[] shortestPath(int vertex) {
        if (!isConnected(vertex)) {  // vybav rozne koponenty
            return null;
        }
        int[] path = new int[dist[vertex] + 1];  // alokujeme cestu
        int v = vertex;   //posledny vrchol bude vertex
        path[dist[vertex]] = v;
        for (int i = dist[vertex] - 1; i >= 0; i--) { // odzadu pridavame vrcholy
            v = prev[v];      // posunieme sa na predchadzajuci vrchol na ceste
            path[i] = v;
        }
        return path;
    }
}

public class Prog {

    /** Zo scannera s načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov.
     * Ak je matrix true, uloží ho ako AdjMatrixGraph,
     * inak ako AdjListsGraph. */
    static Graph readGraph(Scanner s, boolean matrix) {
        int n = s.nextInt();
        int m = s.nextInt();
        Graph g;
        if (matrix) {
            g = new AdjMatrixGraph(n);
        } else {
            g = new AdjListsGraph(n);
        }
        for (int i = 0; i < m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            g.addEdge(u, v);
        }
        return g;
    }

    /** Graph g vypíše do výstupného streamu */
    static void printGraph(Graph g, PrintStream out) {
        int n = g.getNumberOfVertices();
        out.println(n + " " + g.getNumberOfEdges());
        for (int u = 0; u < n; u++) {
            for (int v : g.adjVertices(u)) {
                if (u < v) {  // kvoli symetrii v neorientovaných grafoch
                    out.println(u + " " + v);
                }
            }
        }
    }

    /** Pomocná metóda pre metódu connected.
     * Dostane graf g, vrchol vertex
     * a pole s poznačenými navštívenými vrcholmi, pričom
     * visited[vertex] by malo byť false.
     * Rekurzívne prehľadá nenavštívené vrcholy, ktoré sa z
     * vrcholu vertex dajú dosiahnuť. */
    static void search(Graph g, int vertex, boolean[] visited) {
        visited[vertex] = true;
        for (int neighbor : g.adjVertices(vertex)) { // prejdi cez susedov
            if (!visited[neighbor]) {
                search(g, neighbor, visited); // navstivime ho rekurzivne
            }
        }
    }

    /** Metóda, ktorá zistí, či sú vrcholy from a to v grafe g
     * spojené cestou. */
    static boolean connected(Graph g, int from, int to) {
        // vytvor pole visited vyplnené false
        boolean[] visited = new boolean[g.getNumberOfVertices()];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
        search(g, from, visited); // zavolaj rekurziu
        return visited[to];       // dostali sme sa do vrchola to?
    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner s;
        Graph g;
        PrintStream out;

        // nacitame graph ako maticu susedov a vypiseme
        s = new Scanner(new File("graph-in.txt"));
        g = readGraph(s, true);
        s.close();
        out = new PrintStream("graph-out1.txt");
        printGraph(g, out);
        out.close();

        // nacitame graf ako zoznamy susedov a vypiseme
        s = new Scanner(new File("graph-in.txt"));
        g = readGraph(s, false);
        s.close();
        out = new PrintStream("graph-out2.txt");
        printGraph(g, out);
        out.close();

        // ratame pre dvojice vrcholov ci su spojene jednorazovou funkciou
        System.out.println("Are 1 and 4 connected? " + connected(g, 1, 4));
        System.out.println("Are 0 and 1 connected? " + connected(g, 0, 1));

        // predpocitame komponenty, potom zistime ich pocet a testujeme spojitost
        Components comp = new Components(g);
        System.out.println("The number of connected components: " 
			   + comp.getNumberOfComponents());
        System.out.println("Are 1 and 4 connected? " + comp.areConnected(1, 4));
        System.out.println("Are 0 and 1 connected? " + comp.areConnected(0, 1));

        // najdeme najkratsie vzdialenosti z 1 do ostatnych vrcholov
        ShortestPaths paths = new ShortestPaths(g, 1);
        System.out.println("Are 1 and 4 connected? " + paths.isConnected(4));
        System.out.println("Distance of 1 and 4: " + paths.distance(4));
        System.out.println("Shortest path from 1 to 4: " 
			   + Arrays.toString(paths.shortestPath(4)));
    }
}