Cvičenie 8 – Grafy

Ciele cvičení:

  • vedieť ako možno reprezentovať orientovaný aj neorientovaný graf
  • vedieť implementovať algoritmy na prehľadávanie grafov a topologické triedenie pri použití rôznych spôsobov uloženia grafu v programe
  • vedieť aplikovať grafové algoritmy na riešenie prakticky motivovaných problémov

Teoretická príprava

  • Uveďte 2 príklady z reálneho života (okrem príkladov z prednášky), kde možno reálny svet modelovať pomocou neorientovaných grafov.
  • Tvorí graf používateľov sociálnej siete súvislý graf (všimnite si prípad, keď sa nový používateľ zaregistruje do systému)?
  • Nakreslite súvislý neorientovaný graf so 7 vrcholmi a 12 hranami. Vrcholy označte číslami 0 až 6.
  • Vytvorte maticu susednosti k uvedenému grafu.
  • Zvoľte ľubovoľný vrchol grafu ako štartovací vrchol BFS a odsimulujte priebeh algoritmu BFS (prehľadávanie do šírky) z prednášky. Zaznačte si, v akom poradí boli vrcholy navštívené. Zároveň si pre každý vrchol grafu poznamenajte číslo vrcholu, vďaka ktorému sa tento vrchol stal navštíveným.
  • Analogicku úlohu riešte aj s prehľadávaním do hĺbky (DFS) predtým, než sa mu budete v rámci niektorej z úloh venovať.
  • Porovnajte výsledky s vizualizáciou algoritmov pomocou knižnice PAZGraphs.
  • Knižnica na prácu s grafmi: PAZGraphs (Maven)

Prehľadávanie do šírky (BFS)

Doplňte algoritmus BFS z prednášky tak, aby sa pre každý vrchol vypočítala jeho vzdialenosť od štartovacieho vrcholu BFS prehľadávania.

  • pre každý vrchol grafu vypíšte jeho vzdialenosť
  • vytvorte metódu najdiCestu, ktorá pre zadaný vrchol z predvýpočítanej informácie z BFS prehľadávania vráti zoznam vrcholov tvoriacich najkratšiu cestu z tohto vrcholu do štartovacieho vrcholu prehľadávania (resp. null, ak taká cesta neexistuje):


1
public static List<Vertex> cestaZ(Graph g, Map<Vertex, Integer> vzdialenosti, Vertex kam);

Prehľadávanie do šírky a matica susednosti

Implementujte test súvislosti grafu (akýmkoľvek prehľadávaním z prednášky) v prípade, že graf je popísaný maticou susednosti.

Možné riešenie úlohy:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Vytvori ku neohodnotenemu grafu prisluchajucu maticu susednosti

public static boolean[][] grafNaMaticuSusednosti(Graph g) {

    Vertex[] vrcholyVPoli = g.createVertexArray();

    boolean[][] matica = g.createAdjacencyMatrix(vrcholyVPoli);

        return matica;

}



// Otestuje suvislost neorientovaneho grafu zadaneho maticou susednosti

public static boolean suvislostNeorientovaneho(boolean[][] matica) {

    // Vyberieme pocet vrcholov grafu

    int n = matica.length;



    // Vytvorime pole na evidenciu navstivenia vrcholu (default je false)

    boolean[] navstiveny = new boolean[n];



        // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial

        // neskusali navstivit

        Queue<Integer> rad = new LinkedList<Integer>();



        // Na zaciatku je navstiveny iba startovaci vrchol

        navstiveny[0] = true;

        rad.offer(0);



        // Kym rad nie je prazdny

        while (!rad.isEmpty()) {

                // Vyberieme prvy vrchol v rade

                int vIdx = rad.poll();



                // Postupne vsetkych nenavstivenych susedov vrcholu oznacime ako

                // navstivenych a pridame ich do radu

                for (int i=0; i<n; i++)

                        if ((matica[vIdx][i]) && (!navstiveny[i])) {

                                navstiveny[i] = true;

                                rad.offer(i);

                        }

        }



        // Zistime, ci ostal nejaky vrchol nenavstiveny

        for (int i=0; i<n; i++)

                if (!navstiveny[i])

                        return false;



        return true;

}
  • Ako by ste tento program upravili na výpočet vzdialenosti najkratšej cesty zo zadaného vrchola grafu do všetkých ostatných vrcholov grafu bez použitia objektov tried JCF? Implementujte.
    • Tip: Vytvorte si pole int-ov, ktoré bude také veľké ako je počet vrcholov grafu. V ňom si pre každý vrchol pamätajte nájdenú vzdialenosť (resp. -1 ak sa cestu zo zadaného vrcholu k danému vrcholu zatiaľ nepodarilo nájsť).

Analyzujeme grafy

  • S využitím prehľadávacích algoritmov z prednášky, vytvorte program tak, aby ste:
    • vypísali, či graf je súvislý,
    • spočítali počet komponentov grafu,
    • pre každý vrchol vypísali informáciu, do ktorého komponentu patrí, môžete použiť Map a číslovať komponenty od 0 (preferované)
    • vypísali koľko vrcholov má najväčší komponent grafu.
  • Navrhnite úpravu algoritmu BFS/DFS z prednášky tak, aby ste si pre každý vrchol grafu zapamätali objaviteľskú hranu.
  • Ďalšie úlohy:
    • Navrhnite algoritmus pre výpočet excentricitu štartovacieho vrcholu BFS?
    • Navrhnite algoritmus pre výpočet priemeru grafu.
    • Uvažujte a diskutujte, či je matica susednosti vhodná reprezentácia grafu sociálnej siete ako je napr. Facebook. Koľko operácií potrebujeme vykonať pri takejto reprezentácií, aby sme našli spoločných priateľov medzi 2 osobami? Aká iná reprezentácia grafu by bola vhodnejšia?
  • Nech G je súvislý graf. Hranu nazývame mostom, ak jej odstránením sa stane graf nesúvislým. Navrhnite algoritmus na nájdenie mostov.

Topologické triedenie

  • Nakreslite orientovaný graf so 7 vrcholmi a 12 hranami tak, že medzi 2 vrcholmi je nanajvýš jedna orientovaná hrana. V uvedenom grafe aplikujte algoritmus topologického triedenia.
    • Ak topologické triedenie neskončilo s prázdnym grafom, navrhnite postup, ktorý vo „zvyšku“ grafu nájde orientovaný cyklus. Využijeme tvrdenie, že orientovaný graf má topologické usporiadanie vrcholov práve vtedy, keď neobsahuje orientovaný cyklus. Ako by ste dokázali toto tvrdenie?

Pre fajnšmekrov

  • S využitím myšlienky prehľadávania do hĺbky vytvorte efektívny algoritmus na nájdetenie artikulácii v grafe.
  • Vytvorte algoritmus na nájdenie riešenie problému o misionároch a kanibaloch (s minimálnym počtom presunov):
    • Online hra
    • pokúste sa program riešiť pre ľubovoľný počet kanibalov/misionárov