Letný semester, prednáška č. 8

Oznamy

• Dnes po prednáške bude zverejnené zadanie tretej domácej úlohy, ktorú bude potrebné odovzdať do pondelka 12. apríla, 9:00 (čiže do začiatku budúcej prednášky).
• V stredu na cvičeniach bude zverejnených niekoľko nebodovaných úloh zameraných na grafy a grafové algoritmy.
• Počas cvičení v stredu 7. apríla bude prebiehať tretí test zameraný na látku z prvých siedmich prednášok (časť úloh bude zameraná na grafy, časť ešte na skoršiu látku).

Triedy pre grafy z minulej prednášky

package graphs;

/**
 *  Rozhranie pre reprezentacie grafov o vrcholoch 0, 1, ..., n-1 pre nejake
 *  prirodzene cislo n.
 */
public interface Graph {
    /**
     * Metoda, ktora vrati pocet vrcholov reprezentovaneho grafu.
     *
     * @return Pocet vrcholov grafu.
     */
    int getNumberOfVertices();

    /**
     * Metoda, ktora vrati pocet hran reprezentovaneho grafu.
     *
     * @return Pocet hran grafu.
     */
    int getNumberOfEdges();

    /**
     * Metoda, ktora zisti, ci v grafe existuje hrana medzi danou dvojicou vrcholov.
     *
     * @param from Pociatocny vrchol.
     * @param to   Koncovy vrchol.
     * @return     Vrati true prave vtedy, ked v grafe existuje hrana z vrcholu from do vrcholu to.
     */
    boolean existsEdge(int from, int to);

    /**
     * Metoda, ktora vrati vsetkych naslednikov daneho vrcholu -- cize vsetky vrcholy, do ktorych vedie z daneho vrcholu
     * orientovana hrana. Pre neorientovane grafy tak tato metoda vzdy vrati vsetkych susedov daneho vrcholu.
     * 
     * @param vertex Lubovolny vrchol grafu.
     * @return       Naslednici vrcholu vertex ako instancia typu Iterable<Integer>.
     */
    Iterable<Integer> outgoingEdgesDestinations(int vertex);
}

package graphs;

public class Edge {
    private int from, to;

    public Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }

    public int getFrom() {
        return from;
    }

    public int getTo() {
        return to;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return this.getClass() == o.getClass() && from == ((Edge) o).from && to == ((Edge) o).to;
    }

    @Override
    public int hashCode() {
        return Integer.valueOf(from).hashCode() + 31 * Integer.valueOf(to).hashCode();
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca orientovany graf pomocou zoznamov naslednikov jednotlivych jeho vrcholov.
 */
public class SuccessorListsGraph implements Graph {
    /**
     * Pre kazdy vrchol zoznam jeho naslednikov.
     */
    private ArrayList<ArrayList<Integer>> successorLists;

    /**
     * Pocet hran v grafe (velkost grafu).
     */
    private int edgeCount;

    /**
     * Konstruktor, ktory dostane ako argumenty pocet vrcholov grafu (t. j. jeho rad), ako aj vsetky hrany grafu.
     *
     * @param vertexCount Rad grafu, cize pocet jeho vrcholov.
     * @param edges       Zoskupenie pozostavajuce zo vsetkych hran grafu.
     */
    public SuccessorListsGraph(int vertexCount, Collection<Edge> edges) {
        successorLists = new ArrayList<>();
        for (int i = 0; i <= vertexCount - 1; i++) {
            successorLists.add(new ArrayList<>());
        }
        edgeCount = 0;
        for (Edge e : edges) {
            if (!existsEdge(e.getFrom(), e.getTo())) {
                successorLists.get(e.getFrom()).add(e.getTo());
                edgeCount++;
            }
        }
    }

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

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

    @Override
    public boolean existsEdge(int from, int to) {
        return successorLists.get(from).contains(to);
    }

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int from) {
        return Collections.unmodifiableList(successorLists.get(from));  // Vratime nemodifikovatelny pohlad na zoznam successorLists.get(from).
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca orientovany graf pomocou matice susednosti.
 */
public class AdjacencyMatrixGraph implements Graph {
    /**
     * Matica susednosti.
     */
    private boolean adjacencyMatrix[][];

    /**
     * Pocet hran v grafe (velkost grafu).
     */
    private int edgeCount;

    /**
     * Konstruktor, ktory dostane ako argumenty pocet vrcholov grafu (t. j. jeho rad), ako aj vsetky hrany grafu.
     *
     * @param vertexCount Rad grafu, cize pocet jeho vrcholov.
     * @param edges       Zoskupenie pozostavajuce zo vsetkych hran grafu.
     */
    public AdjacencyMatrixGraph(int vertexCount, Collection<Edge> edges) {
        adjacencyMatrix = new boolean[vertexCount][vertexCount];
        edgeCount = 0;
        for (Edge e : edges) {
            if (!existsEdge(e.getFrom(), e.getTo())) {
                adjacencyMatrix[e.getFrom()][e.getTo()] = true;
                edgeCount++;
            }
        }
    }

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

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

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

    @Override
    public Iterable<Integer> outgoingEdgesDestinations(int vertex) {
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i <= getNumberOfVertices() - 1; i++) {
            if (adjacencyMatrix[vertex][i]) {
                a.add(i);
            }
        }
        return Collections.unmodifiableList(a);
    }
}

package graphs;

public interface UndirectedGraph extends Graph {

}

package graphs;

import java.util.*;

/**
 * Pomocne metody na pracu so zoskupeniami hran.
 */
public class Edges {

    public static Collection<Edge> symmetricClosure(Collection<Edge> edges) {
        List<Edge> result = new ArrayList<>();
        for (Edge e : edges) {
            result.add(e);
            if (e.getFrom() != e.getTo()) {
                result.add(new Edge(e.getTo(), e.getFrom()));
            }
        }
        return result;
    }

    public static int distinctUndirectedEdges(Collection<Edge> edges) {
        HashSet<Edge> set = new HashSet<>();
        for (Edge e : edges) {
            if (!set.contains(e) && !set.contains(new Edge(e.getTo(), e.getFrom()))) {
                set.add(e);
            }
        }
        return set.size();
    }
}

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca neorientovany graf pomocou zoznamov susedov jednotlivych jeho vrcholov.
 */
public class AdjacencyListsUndirectedGraph extends SuccessorListsGraph implements UndirectedGraph {
    private int undirectedEdgeCount;

    public AdjacencyListsUndirectedGraph(int vertexCount, Collection<Edge> edges) {
        super(vertexCount, Edges.symmetricClosure(edges));
        undirectedEdgeCount = Edges.distinctUndirectedEdges(edges);
    }

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

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca neorientovany graf pomocou matice susednosti.
 */
public class AdjacencyMatrixUndirectedGraph extends AdjacencyMatrixGraph implements UndirectedGraph {
    private int undirectedEdgeCount;

    public AdjacencyMatrixUndirectedGraph(int vertexCount, Collection<Edge> edges) {
        super(vertexCount, Edges.symmetricClosure(edges));
        undirectedEdgeCount = Edges.distinctUndirectedEdges(edges);
    }

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

Pokračovanie úvodu do grafov

Vytvorenie grafu

Metóda readGraph triedy Trieda uvedenej nižšie prečíta pomocou danej inštancie triedy Scanner reprezentáciu grafu a vytvorí z nej graf typu určeného jej druhým parametrom. Argument pre typ grafu je pritom vymenovaného typu GraphType (o vymenovaných typoch sa možno dočítať viac tu).

package graphs;

public enum GraphType {
    DIRECTED_SUCCESSOR_LISTS, DIRECTED_ADJACENCY_MATRIX, UNDIRECTED_ADJACENCY_LISTS, UNDIRECTED_ADJACENCY_MATRIX
}

package graphs;

import java.util.*;

public class Trieda {
    /**
     * Metoda, ktora precita textovu reprezentaciu grafu pozostavajucu z poctu vrcholov n, poctu hran m a z m dvojic
     * vrcholov udavajucich jednotlive hrany a vytvori z nej graf urceneho typu.
     *
     * @param scanner   Scanner, z ktoreho sa reprezentacia grafu cita.
     * @param graphType Typ vytvaraneho grafu.
     * @return          Vytvoreny graf.  
     */
    public static Graph readGraph(Scanner scanner, GraphType graphType) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        List<Edge> edges = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            edges.add(new Edge(scanner.nextInt(), scanner.nextInt()));
        }
        Graph g = null;
        switch (graphType) {
            case DIRECTED_SUCCESSOR_LISTS:
                g = new SuccessorListsGraph(n, edges);
                break;
            case DIRECTED_ADJACENCY_MATRIX:
                g = new AdjacencyMatrixGraph(n, edges);
                break;
            case UNDIRECTED_ADJACENCY_LISTS:
                g = new AdjacencyListsUndirectedGraph(n, edges);
                break;
            case UNDIRECTED_ADJACENCY_MATRIX:
                g = new AdjacencyMatrixUndirectedGraph(n, edges);
                break;
        }
        return g;
    }
}

Volanie metódy readGraph potom môže vyzerať napríklad nasledovne:

Graph g = readGraph(scanner, GraphType.DIRECTED_SUCCESSOR_LISTS);

Porovnanie reprezentácií grafov

Majme orientovaný graf s n vrcholmi a m hranami – počet hrán m teda môže byť od 0 po n². V závislosti od použitej reprezentácie grafu sa líši ako časová zložitosť jednotlivých operácií na grafoch, tak aj pamäťová zložitosť samotnej tejto reprezentácie. Napríklad:

• Pamäť potrebná na uloženie matice susednosti grafu je vždy rádovo veľkosti n². Pri reprezentácii pomocou zoznamov následníkov resp. susedov je veľkosť reprezentácie grafu rádovo n+m. Hlavne pre riedke grafy (s menším počtom hrán) je teda reprezentácia pomocou zoznamov pamäťovo efektívnejšia.
• Operácia existsEdge sa pre grafy reprezentované maticou susednosti vykoná v konštantnom čase. Pre grafy reprezentované zoznamami následníkov resp. susedov môže byť zložitosť tejto operácie až lineárna v závislosti od počtu vrcholov grafu (je potrebné prejsť celý zoznam susedov jedného vrchola, ktorý môže obsahovať až n rôznych vrcholov).
• Naopak vytvorenie zoznamu následníkov resp. susedov grafu v metóde outgoingEdgesDestinations je efektívnejšie pri reprezentácii pomocou zoznamov.

Ďalšie varianty grafov

Grafy na tejto prednáške chápeme v relatívne obmedzenom slova zmysle. V praxi sa často zídu aj rôzne rozšírenia definície grafu:

• Grafy s násobnými hranami (niekde tiež multigrafy) umožňujú viesť medzi danou dvojicou vrcholov viacero paralelných hrán. To možno v pamäti počítača realizovať napríklad nahradením booleovskej matice maticou prirodzených čísel udávajúcich násobnosti jendotlivých hrán, prípadne pridaním informácie o multiplicite do zoznamov následníkov resp. susedov.
• Ohodnotené grafy obsahujú na hranách nejakú ďalšiu prídavnú informáciu (napríklad pri cestnej sieti si môžeme pamätať dĺžku jednotlivých úsekov, prípadne ich možno využiť aj na reprezentáciu multigrafov). Možno ich reprezentovať nahradením booleovskej matice maticou ohodnotení, prípadne zakomponovaním informácie o ohodnotení hrán do zoznamov následníkov resp. susedov. S ohodnotenými grafmi sa okrajovo stretneme aj tento semester.
• Dynamické grafy podporujú aj pridávanie a mazanie vrcholov a/alebo hrán.

Prehľadávanie (orientovaného alebo neorientovaného) grafu do hĺbky

Existencia cesty medzi dvojicou vrcholov

Riešme teraz nasledujúci problém: pre danú dvojicu vrcholov u a v nejakého (orientovaného alebo neorientovaného) grafu potrebujeme zistiť, či sú spojené sledom – t. j. postupnosťou postupne na seba nadväzujúcich hrán (táto postupnosť môže byť aj prázdna, takže z každého vrcholu triviálne vedie sled do seba samého). Existencia sledu medzi dvoma vrcholmi je očividne ekvivalentná existencii cesty (t. j. sledu, v ktorom sa žiaden vrchol nezopakuje).

V nasledujúcom preto budeme hovoriť o existencii ciest.

Pojmy sledu a cesty o niečo presnejšie:

• Sledom v grafe rozumieme postupnosť vrcholov v₀, v₁, ..., v_n takú, že pre i = 1,...,n existuje v danom grafe hrana z v_i-1 do v_i.
• Cestou rozumieme sled v₀, v₁, ..., v_n taký, že vrcholy v₀, v₁, ..., v_n sú po dvoch rôzne.
• Dĺžkou sledu (alebo cesty) v₀, v₁, ..., v_n nazveme číslo n, čiže počet hrán tento sled tvoriacich.

Pre neorientované grafy možno problém existencie cesty medzi dvoma vrcholmi chápať aj ako úlohu zistiť, či sú tieto dva vrcholy v rovnakom komponente súvislosti grafu. Komponent súvislosti neorientovaného grafu je každý jeho (vzhľadom na inklúziu) maximálny podgraf, ktorý je súvislý – komponent súvislosti grafu teda pozostáva z nejakej podmnožiny jeho vrcholov a všetkých hrán pôvodného grafu spájajúcich vrcholy z tejto podmnožiny, pričom ľubovoľné dva vrcholy komponentu sú spojené cestou a pridaním ľubovoľného ďalšieho vrcholu grafu sa táto vlastnosť poruší. (Pri tejto „definícii” využívame fakt, že existencia cesty v neorientovanom grafe je zjavne reláciou ekvivalencie na množine jeho vrcholov.) Napríklad neorientovaný graf na nasledujúcom obrázku pozostáva z troch komponentov súvislosti.

Na riešenie problému existencie cesty použijeme prehľadávanie do hĺbky (angl. depth-first search) – podobné, ako sme už používali minulý semester pri vyfarbovaní súvislých oblastí v obdĺžnikovej mriežke. Procedúra na grafoch však bude všeobecnejšia:

• Mriežku môžeme reprezentovať neorientovaným grafom, v ktorom vrcholy zodpovedajú políčkam mriežky. Dvojica vrcholov je navyše spojená hranou práve vtedy, keď zodpovedajúce políčka spolu susedia a súčasne majú rovnakú farbu.
• Ostrovy rovnakej farby v mriežke potom zodpovedajú komponentom súvislosti výsledného neorientovaného grafu.

Na riešenie uvedeného problému napíšeme rekurzívnu metódu search, ktorá bude prehľadávať všetkých ešte nenavštívených následníkov daného vrcholu. Informáciu o navštívení jednotlivých vrcholov si budeme uchovávať v zozname visited. Metóda existsPath bude metódu search využívať na riešenie horeuvedeného problému.

/**
* Pomocna metoda pre metodu existsPath, ktora rekurzivne prehlada vsetky doposial nenavstivene vrcholy
* dosiahnutelne z daneho vrcholu.
* @param g       Orientovany alebo neorientovany graf, v ktorom sa prehladavanie realizuje.
* @param vertex  Vrchol grafu g, v ktorom sa prehladavanie zacina.
* @param visited Zoznam obsahujuci informacie o navstiveni jednotlivych vrcholov grafu. Pri volani metody by malo
*                platit visited.get(vertex) == false.
*/
static void search(Graph g, int vertex, List<Boolean> visited) {
    visited.set(vertex, true);
    for (int successor : g.outgoingEdgesDestinations(vertex)) {
        if (!visited.get(successor)) {
            search(g, successor, visited);
        }
    }
}

/**
 * Metoda, ktora zisti, ci je dvojica vrcholov grafu spojena cestou.
 * @param g    Graf, v ktorom sa uloha realizuje.
 * @param from Pociatocny vrchol.
 * @param to   Koncovy vrchol.
 * @return     Vystup je true prave vtedy, ked v grafe g existuje cesta z vrcholu from do vrcholu to.
 */
static boolean existsPath(Graph g, int from, int to) {
    ArrayList<Boolean> visited = new ArrayList<>();
    for (int i = 0; i <= g.getNumberOfVertices() - 1; i++) {
        visited.add(false);
    }
    search(g, from, visited);
    return visited.get(to);
}

Cvičenie. Vytvorte abstraktnú triedu AbstractGraph implementujúcu rozhranie Graph a upravte triedy SuccessorListsGraph a AdjacencyMatrixGraph tak, aby dedili od triedy AbstractGraph. Prepíšte metódy existsPath a search uvedené vyššie ako metódy inštancie triedy AbstractGraph. Aký bude mať táto zmena vplyv na argumenty týchto metód?

Hľadanie komponentov súvislosti neorientovaného grafu

V prípade, že pracujeme s neorientovaným grafom a existenciu cesty medzi dvojicami vrcholov by sme chceli testovať veľakrát, oplatí sa nájsť všetky komponenty súvislosti v danom grafe. Komponenty môžeme očíslovať od nuly až po nejaké k - 1, pričom pre každý vrchol si môžeme pamätať číslo jeho komponentu. Túto úlohu realizuje nasledujúca trieda:

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca rozdelenie neorientovaneho grafu na komponenty suvislosti.
 */
public class Components {
    /**
     * Neorientovany graf, ktoreho komponenty suvislosti su instanciou tejto triedy reprezentovane.
     */
    private UndirectedGraph g;

    /**
     * Zoznam, v ktorom si pre kazdy vrchol grafu g budeme pamatat cislo jeho komponentu.
     */
    private ArrayList<Integer> componentId;

    /**
     * Celkovy pocet komponentov suvislosti grafu g.
     */
    private int componentCount;

    /**
     * Konstruktor, ktory dostane ako argument neorientovany graf, najde komponenty suvislosti tohto grafu a informacie
     * o nich ulozi do premennych instancie.
     * @param g Neorientovany graf, ktoreho komponenty su reprezentovane instanciou tejto triedy.
     */
    public Components(UndirectedGraph g) {
        this.g = g;
        componentCount = 0;
        int n = g.getNumberOfVertices();

        componentId = new ArrayList<>();
        for (int i = 0; i <= n - 1; i++) {
            componentId.add(-1);
        }

        for (int i = 0; i <= n - 1; i++) {
            if (componentId.get(i) == -1) {
                search(i, componentCount);
                componentCount++;
            }
        }
    }

    /**
     * Pomocna metoda pre konstruktor, ktora oznaci vrcholy jedneho komponentom suvislosti identifikatorom tohto
     * komponentu. Pracuje na baze prehladavania do hlbky.
     * @param vertex Vrchol, z ktoreho sa zacina prehladavanie vrcholov komponentu.
     * @param id     Identifikator komponentu suvislosti.
     */
    private void search(int vertex, int id) {
        componentId.set(vertex, id);
        for (int neighbour : g.outgoingEdgesDestinations(vertex)) {
            if (componentId.get(neighbour) == -1) {
                search(neighbour, id);
            }
        }
    }

    /**
     * Metoda, ktora zisti, ci v grafe, ktoreho komponenty reprezentuje instancia tejto triedy, existuje cesta spajajuca
     * danu dvojicu vrcholov.
     * @param from Pociatocny vrchol.
     * @param to   Koncovy vrchol.
     * @return     Metoda vrati true prave vtedy, ked v grafe existuje cesta z vrcholu from do vrcholu to.
     */
    public boolean existsPath(int from, int to) {
        return componentId.get(from).equals(componentId.get(to));
    }

    /**
     * Metoda, ktora vrati celkovy pocet komponentov grafu.
     * @return Pocet komponentov.
     */
    public int getComponentCount() {
        return componentCount;
    }
}

Nasledujúci kód načíta neorientovaný graf a dvojicu jeho vrcholov. Na konzolu následne vypíše, či sú tieto dva vrcholy v danom grafe spojené cestou.

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Zadaj neorientovany graf:");
    UndirectedGraph g = (UndirectedGraph) readGraph(scanner, GraphType.UNDIRECTED_ADJACENCY_LISTS);
    System.out.println("Zadaj dvojicu vrcholov grafu:");
    int from = scanner.nextInt();
    int to = scanner.nextInt();

    Components components = new Components(g);
    if (components.existsPath(from, to)) {
        System.out.println("Vrcholy su spojene cestou.");
    } else {
        System.out.println("Vrcholy nie su spojene cestou.");
    }
}

Prehľadávanie (orientovaného alebo neorientovaného) grafu do šírky

Podobne ako prehľadávanie do hĺbky možno vo všeobecnejšom kontexte grafov aplikovať aj prehľadávanie do šírky (angl. breadth-first search), ktorého variant pre obdĺžnikovú mriežku poznáme z minulého semestra. Prehľadávanie grafu do šírky bude možné použiť na hľadanie najkratších ciest medzi dvojicami vrcholov orientovaného (a teda aj neorientovaného) grafu, kde dĺžka cesty je meraná počtom hrán.

Hľadanie najkratšej cesty

Hľadanie najkratších ciest v grafe – či už orientovanom alebo neorientovanom – možno realizovať napríklad nasledujúcou triedou ShortestPathsFromVertex:

• Jej konštruktor dostane ako parameter graf g a nejaký jeho význačný „štartovací” vrchol start. Následne spustí na grafe g prehľadávanie do šírky z vrcholu start.
• Takto sa postupne prehľadajú vrcholy vo vzdialenosti 1 od start, potom vrcholy vo vzdialenosti 2 od start, atď. Na zabezpečenie takéhoto poradia sa použije rad, podobne ako pri algoritme na mriežke minulý semester. V každom momente vykonávania algoritmu môže tento rad obsahovať vrcholy najviac dvoch rôznych vzdialeností od start.
• Pre každý vrchol v sa počas prehľadávania do zoznamu dist uloží jeho vzdialenosť od vrcholu start a do zoznamu prev sa uloží vrchol u, z ktorého bol vrchol v objavený – musí pritom vždy ísť o predposledný vrchol na jednej z najkratších ciest zo start do v.
• Metóda distanceFromStart bude pre daný vrchol vertex vracať jeho vzdialenosť od vrcholu start. Tu sa jednoducho využije hodnota uložená v zozname dist.
• Metóda shortestPathFromStart bude pre daný vrchol vertex vracať najkratšiu cestu z vrcholu start do vrcholu vertex reprezentovanú zoznamom vrcholov. Tú bude konštruovať od konca: začne vo vrchole vertex a postupne bude hľadať predchodcov pomocou hodnôt uložených v zozname prev.

package graphs;

import java.util.*;

/**
 * Trieda reprezentujuca najkratsie cesty z pevne daneho pociatocneho vrcholu do vsetkych ostatnych vrcholov grafu.
 */
public class ShortestPathsFromVertex {
    /**
     * Graf, v ktorom sa hladanie najkratsich ciest realizuje.
     */
    private Graph g;

    /**
     * "Startovaci" vrchol. Instancia triedy bude reprezentovat najkratsie cesty z tohto vrcholu do vsetkych ostatnych
     * vrcholov grafu g.
     */
    private int start;

    /**
     * Zoznam obsahujuci pre kazdy vrchol grafu jeho vzdialenost zo startovacieho vrcholu start. Ak zo start do nejakeho
     * vrcholu nevedie ziadna cesta, bude namiesto jeho vzdialenosti v zozname ulozena hodnota -1.
     */
    private List<Integer> distances;

    /**
     * Zoznam obsahujuci pre kazdy vrchol v grafu g jeho predchodcu na najkratsej ceste z vrcholu start do vrcholu v.
     * Pre vrchol start samotny a vrcholy, do ktorych zo start nevedie ziadna cesta, bude v zozname ulozena hodnota -1.
     */
    private List<Integer> predecessors;

    /**
     * Konstruktor, ktory pre dany graf a "startovaci" vrchol rovno aj najde najkratsie cesty zo startovacieho vrcholu
     * do vsetkych ostatnych vrcholov grafu.
     * @param g     Graf, v ktorom sa hladanie ciest realizuje.
     * @param start "Startovaci" vrchol.
     */
    public ShortestPathsFromVertex(Graph g, int start) {
        this.g = g;
        this.start = start;

        /* Inicializacia zoznamov dist a prev: */
        distances = new ArrayList<>();
        predecessors = new ArrayList<>();
        for (int i = 0; i <= g.getNumberOfVertices() - 1; i++) {
            distances.add(-1);
            predecessors.add(-1);
        }

        /* Samotne prehladavanie do sirky: */
        Queue<Integer> queue = new LinkedList<>();
        distances.set(start, 0);
        queue.add(start);
        while (!queue.isEmpty()) {
            // Vyberieme vrchol z radu, prejdeme vsetkych jeho naslednikov, nenavstivenych spracujeme a vlozime do radu:
            int vertex = queue.remove();
            for (int successor : g.outgoingEdgesDestinations(vertex)) {
                if (distances.get(successor) == -1) {
                    distances.set(successor, distances.get(vertex) + 1);
                    predecessors.set(successor, vertex);
                    queue.add(successor);
                }
            }
        }
    }

    /**
     * Metoda, ktora vrati dlzku najkratsej cesty z vrcholu start do daneho vrcholu.
     * @param vertex Vrchol, vzdialenost ktoreho z vrcholu start sa pocita.
     * @return       Dlzka najkratsej cesty z vrcholu start do vrcholu vertex. Ak ziadna neexistuje, vrati sa -1.
     */
    public int distanceFromStart(int vertex) {
        return distances.get(vertex);
    }

    /**
     * Metoda, ktora vrati najkratsiu cestu z vrcholu start do daneho vrcholu, reprezentovanu ako zoznam vrcholov.
     * @param vertex Vrchol, najkratsia cesta do ktoreho z vrcholu start sa pocita.
     * @return       Nemodifikovatelny zoznam obsahujuci postupne vsetky vrcholy najkratsej cesty zo start do vertex.
     *               Ak ziadna cesta zo start do vertex neexistuje, vrati metoda referenciu null.
     */
    public List<Integer> shortestPathFromStart(int vertex) {
        if (distances.get(vertex) == -1) {
            return null;
        }
        LinkedList<Integer> path = new LinkedList<>();
        int v = vertex;
        while (v != -1) {
            path.addFirst(v);
            v = predecessors.get(v);
        }
        return Collections.unmodifiableList(path);
    }
}

Nasledujúci kód načíta graf a dvojicu jeho vrcholov; vypíše najkratšiu cestu medzi danými vrcholmi.

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Zadaj graf:");
    Graph g = readGraph(scanner, GraphType.DIRECTED_SUCCESSOR_LISTS);
    System.out.println("Zadaj pociatocny a koncovy vrchol:");
    int from = scanner.nextInt();
    int to = scanner.nextInt();

    ShortestPathsFromVertex shortestPathsFromVertex = new ShortestPathsFromVertex(g, from);
    System.out.println("Najkratsia cesta ma dlzku " + shortestPathsFromVertex.distanceFromStart(to) + ".");
    List<Integer> shortestPath = shortestPathsFromVertex.shortestPathFromStart(to);
    if (shortestPath != null) {
        System.out.println(shortestPath);
    }
}

Stromy prehľadávania do hĺbky a do šírky

Označme pri prehľadávaní do hĺbky aj do šírky tie hrany, ktoré boli použité pri objavovaní nových vrcholov – to znamená: pri prehľadávaní do hĺbky hrany (u,v) také, že vo volaní metódy search pre vrchol u sa táto metóda zavolala rekurzívne aj pre vrchol v a pri prehľadávaní do šírky hrany (u,v) také, že sa v rámci prehľadávania následníkov vrcholu u do radu pridal vrchol v.

• V oboch prípadoch potom takéto hrany tvoria strom zakorenený vo vrchole, v ktorom prehľadávanie začalo (pri orientovaných grafoch sú všetky hrany orientované smerom od koreňa k listom).
• Hovoríme teda o stromoch prehľadávania do hĺbky resp. do šírky (angl. DFS Tree resp. BFS Tree).
• V prípade, že je graf súvislý, ide v obidvoch prípadoch o jeho kostru (t. j. strom zložený zo všetkých vrcholov grafu a jeho vybraných hrán).
• U stromov prehľadávania do šírky reprezentujú cesty od koreňa k listom vždy niektorú z najkratších ciest medzi príslušnými vrcholmi grafu.

Príklad. Nižšie je znázornený diagram orientovaného grafu a jeho stromy prehľadávania do hĺbky a do šírky v prípade, že prehľadávanie začne vo vrchole 0 a pri spracúvaní následníkov sa postupuje vzostupne podľa čísel vrcholov (tak je tomu pri naších triedach pre grafy, avšak pri všeobecnej triede implementujúcej rozhranie Graph toto poradie nemusí byť garantované).

Strom prehľadávania do hĺbky:

                                                       

Strom prehľadávania do šírky:

                                                       

Prehľadávanie s návratom na grafoch

Pre veľa úloh na grafoch nie sú známe – a v prípade platnosti niektorých hypotéz z teoretickej informatiky často ani neexistujú – žiadne efektívne algoritmy. Prehľadávaním s návratom však vieme spočítať odpoveď aspoň pre malé vstupy.

Hľadanie ciest dĺžky k

Nasledujúca trieda FixedLengthPaths pre daný graf g, danú dvojicu vrcholov from, to a dané prirodzené číslo length nájde všetky cesty dĺžky presne length vedúce v g z vrcholu from do vrcholu to. Prehľadávanie s návratom sa spustí hneď v konštruktore a nájdené cesty sa uložia do zoznamu paths.

Pri prehľadávaní sa v spájanom zozname path budú postupne generovať všetky cesty hľadaného typu. Pre každý vrchol budeme mať navyše v ArrayList-e visited poznačené, či sme ho už v generovanej ceste použili. Akonáhle nájdeme cestu požadovanej dĺžky končiacu vo vrchole to, uložíme ju do zoznamu paths.

package graphs;

import java.util.*;

/**
 * Trieda realizujuca najdenie vsetkych ciest danej fixnej dlzky medzi danou dvojicou vrcholov daneho grafu.
 */
public class FixedLengthPaths {
    /**
     * Graf, v ktorom sa hladanie ciest realizuje.
     */
    private Graph g;

    /**
     * Pociatocny vrchol hladanych ciest.
     */
    private int from;

    /**
     * Koncovy vrchol hladanych ciest.
     */
    private int to;

    /**
     * Pozadovana dlzka hladanych ciest.
     */
    private int length;

    /**
     * Pomocny zoznam, v ktorom sa budu pomocou prehladavania s navratom postupne generovat jednotlive cesty.
     */
    private LinkedList<Integer> path;

    /**
     * Pomocny zoznam, v ktorom si budeme pocas generovania ciest pre kazdy vrchol pamatat, ci sa nachadza alebo
     * nenachadza v doposial vygenerovanej casti cesty.
     */
    private ArrayList<Boolean> visited;

    /**
     * Zoznam, v ktorom budu ulozene vsetky vygenerovane cesty.
     */
    private List<List<Integer>> paths;

    /**
     * Konstruktor, ktory rovno aj spusti prehladavanie s navratom a do zoznamu paths postupne ulozi vsetky cesty danej
     * dlzky medzi danou dvojicou vrcholov daneho grafu.
     * @param g      Graf, v ktorom sa hladanie ciest realizuje.
     * @param from   Pociatocny vrchol hladanych ciest.
     * @param to     Koncovy vrchol hladanych ciest.
     * @param length Pozadovana dlzka hladanych ciest.
     */
    public FixedLengthPaths(Graph g, int from, int to, int length) {
        this.g = g;
        this.from = from;
        this.to = to;
        this.length = length;
        paths = new LinkedList<>();

        visited = new ArrayList<>();
        for (int i = 0; i <= g.getNumberOfVertices() - 1; i++) {
            visited.add(false);
        }
        path = new LinkedList<>();
        path.add(from);
        visited.set(from, true);
        search();
    }

    /**
     * Metoda realizujuca samotne rekurzivne prehladavanie s navratom. Ak je dosial vygenerovana cast cesty kratsia nez
     * length, postupne sa vyskusaju vsetky moznosti jej predlzenia. V pripade, ze uz ide o cestu dlzky length, overi
     * sa, ci cesta konci vo vrchole to a ak ano, prida sa kopia tejto cesty do zoznamu paths.
     */
    private void search() {
        if (path.size() == length + 1) {   // Dlzka zoznamu je vzdy o jedna vacsia, nez dlzka nim reprezentovanej cesty.
            if (path.getLast() == to) {
                paths.add(Collections.unmodifiableList(new LinkedList<>(path)));
            }
        } else {
            for (int successor : g.outgoingEdgesDestinations(path.getLast())) {
                if (!visited.get(successor)) {
                    visited.set(successor, true);
                    path.add(successor);
                    search();
                    path.removeLast();
                    visited.set(successor, false);
                }
            }
        }
    }

    /**
     * Metoda, ktora vrati nemodifikovatelny pohlad na zoznam vsetkych vygenerovanych ciest.
     * @return Nemodifikovatelny zoznam vsetkych ciest dlzky length veducich v grafe g z vrcholu from do vrcholu to.
     */
    public List<List<Integer>> getPaths() {
        return Collections.unmodifiableList(paths);
    }
}

Nasledujúci kód načíta graf, dvojicu vrcholov from, to a prirodzené číslo length a vypíše všetky cesty dĺžky length z vrcholu from do vrcholu to.

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.println("Zadaj graf:");
    Graph g = readGraph(scanner, GraphType.DIRECTED_SUCCESSOR_LISTS);
    System.out.println("Zadaj pociatocny a koncovy vrchol:");
    int from = scanner.nextInt();
    int to = scanner.nextInt();
    System.out.println("Zadaj dlzku generovanych ciest:");
    int length = scanner.nextInt();
  
    FixedLengthPaths fixedLengthPaths = new FixedLengthPaths(g, from, to, length);
    System.out.println("Cesty dlzky " + length + ":");
    for (List<Integer> path : fixedLengthPaths.getPaths()) {
        System.out.println(path);
    }
}

Príklad. Pre orientovaný graf s vrcholmi {0,...,4} a hranami {(0,1),(0,2),(0,3),(1,2),(2,3),(2,4),(4,3)}, počiatočný vrchol 0 a koncový vrchol 3 dostávame nasledujúce výstupy

Cesty dlzky 1:
[0, 3]
Cesty dlzky 2:
[0, 2, 3]
Cesty dlzky 3:
[0, 1, 2, 3]
[0, 2, 4, 3]
Cesty dlzky 4:
[0, 1, 2, 4, 3]

Cvičenia:

• Upravte triedu FixedLengthPaths tak, aby namiesto hľadania a ukladania všetkých ciest danej dĺžky iba počítala, koľko ich je.
• Upravte triedu FixedLengthPaths tak, aby iba zisťovala, či existuje cesta danej dĺžky (po prvej nájdenej ceste je teda možné prehľadávanie ukončiť).
• Navrhnite spôsoby, ako v niektorých prípadoch zistiť, že aktuálne rozrobenú cestu už nie je možné požadovaným spôsobom rozšíriť.

Hľadanie najdlhšej cesty

Uvažujme teraz problém nájdenia nejakej z najdlhších ciest z u do v (ak existuje aspoň jedna). Túto úlohu bude realizovať trieda LongestPath; oproti predchádzajúcemu programu sa ten nasledujúci bude líšiť iba málo:

• Budeme si pamätať najdlhšiu nájdenú cestu.
• Vždy, keď prídeme do cieľového vrcholu, porovnáme dĺžku aktuálnej cesty s najdlhšou cestou nájdenou doteraz.

/* Trieda, pomocou ktorej mozno najst jednu z najdlhsich ciest medzi danou dvojicou vrcholov. */
class LongestPath {
    private Graph g;      // Orientovany (alebo neorientovany) graf
    private int from, to; // Pociatocny a koncovy vrchol
    
    private int maxLength; // Dlzka doposial najdlhsej najdenej cesty z from do to
    
    private LinkedList<Integer> path;        // Zoznam, v ktorom budeme postupne generovat cesty
    private LinkedList<Integer> longestPath; // Okrem toho si budeme pamatat najdlhsiu doposial vygenerovanu cestu
    private ArrayList<Boolean> visited;      // i-ty prvok zoznamu visited bude true, ak sa vrchol i nachadza v path
    
    /* Konstruktor dostane graf, pociatocny a koncovy vrchol. Spusti prehladavanie 
       s navratom, ktore hlada najdlhsiu cestu medzi danymi vrcholmi. */
    public LongestPath(Graph g, int from, int to) {
        this.g = g;
        this.from = from;
        this.to = to;
                
        visited = new ArrayList<>();
        for (int i = 0; i <= g.getNumberOfVertices() - 1; i++) {
            visited.add(false);
        }
        
        maxLength = -1;             // Doposial nemame ziadnu cestu
        path = new LinkedList<>();
        path.add(from);             // Kazda cesta z from bude zacinat vo from
        visited.set(from, true);
        search();                   // Spusti generovanie ciest
    }

    /* Hlavna rekurzivna metoda prehladavania s navratom.
       Ak cesta dorazila do vrchola to, jej dlzka sa porovna s najdlhsou doposial
       najdenou cestou a ak je dlhsia, ulozi sa ako nova doposial najdlhsia cesta.
       Ak este nedorazila do vrchola to, vyskusaju sa vsetky moznosti na jej
       predlzenie.
    */
    private void search() {
        if (path.getLast() == to) { // Ak sme dorazili do cieloveho vrchola, ukonci prehladavanie  
            if (path.size() - 1 > maxLength) {
                maxLength = path.size() - 1;
                longestPath = new LinkedList<>(path);
            }
        } else {                    // Inak vyskusaj vsetky moznosti predlzenia cesty
            for (int neighbour : g.adjVertices(path.getLast())) {
                if (!visited.get(neighbour)) {
                    visited.set(neighbour, true);
                    path.addLast(neighbour);
                    search();
                    path.removeLast();
                    visited.set(neighbour, false);
                }
            }
        }
    }
    
    /* Metoda, ktora vrati najdenu najdlhsiu cestu: */
    public List<Integer> longestPath() {
        if (longestPath != null) {
            return Collections.unmodifiableList(longestPath);
        } else {
            return null;
        }
    }
}

Použitie triedy:

LongestPath lp = new LongestPath(g, from, to);
List<Integer> longest = lp.longestPath();
if (longest != null) {
    System.out.println("Najdlhsia cesta: " + longest); 
}

Príklad výstupu na rovnakom grafe ako vyššie:

Najdlhsia cesta: [0, 1, 2, 4, 3]