streamalism.org

1. Prehľad

V tomto návode pochopíme základné pojmy grafu ako dátovej štruktúry.

Preskúmame tiež jeho implementáciu v prostredí Java spolu s rôznymi operáciami možnými v grafe. Budeme tiež diskutovať o knižniciach Java ponúkajúcich implementácie grafov.

2. Grafová dátová štruktúra

Graf je a dátová štruktúra na ukladanie pripojených údajov ako sieť ľudí na platforme sociálnych médií.

Graf sa skladá z vrcholov a hrán. Vrchol predstavuje entitu (napríklad ľudia) a hrana predstavuje vzťah medzi entitami (napríklad priateľstvá človeka).

Definujeme jednoduchý graf, aby sme tomu lepšie porozumeli:

Tu sme definovali jednoduchý graf s piatimi vrcholmi a šiestimi okrajmi. Kruhy sú vrcholy predstavujúce ľudí a čiary spájajúce dva vrcholy sú hrany predstavujúce priateľov na online portáli.

Existuje niekoľko variácií tohto jednoduchého grafu v závislosti od vlastností hrán. Prejdime si ich v krátkosti v ďalších častiach.

Zameriame sa však iba na jednoduchý graf, ktorý je tu uvedený pre príklady Java v tomto návode.

2.1. Nasmerovaný graf

Graf, ktorý sme doteraz definovali, má hrany bez akéhokoľvek smeru. Ak tieto hrany majú v nich smer, je výsledný graf známy ako smerovaný graf.

Príkladom toho môže byť zastupovanie toho, kto pošle žiadosť o priateľstvo v priateľstve na online portáli:

Tu vidíme, že hrany majú pevný smer. Okraje môžu byť tiež obojsmerné.

2.2. Vážený graf

Náš jednoduchý graf má opäť hrany, ktoré sú nestranné alebo nevážené. Keby namiesto nich hrany majú relatívnu váhu, tento graf je známy ako vážený graf.

Príkladom praktického použitia tohto riešenia môže byť vyjadrenie toho, aké relatívne staré je priateľstvo na online portáli:

Tu vidíme, že hrany majú s nimi spojené váhy. To poskytuje relatívny význam pre tieto hrany.

3. Grafové znázornenia

Graf môže byť znázornený v rôznych formách, ako napríklad matica susedstva a zoznam susedstiev. Každý z nich má svoje výhody a nevýhody v inom usporiadaní.

Tieto znázornenia grafov si predstavíme v tejto časti.

3.1. Matica susedstva

Matica susednosti je štvorcová matica s rozmermi ekvivalentnými počtu vrcholov v grafe.

Prvky matice majú zvyčajne hodnoty „0“ alebo „1“. Hodnota „1“ označuje susednosť medzi vrcholmi v riadku a stĺpci a inak hodnotu „0“.

Pozrime sa, ako vyzerá matica susednosti pre náš jednoduchý graf z predchádzajúcej časti:

Toto zastúpenie je spravodlivé ľahšie implementovateľné a efektívne dopytovať tiež. Je to však tak menej efektívne vzhľadom na obsadený priestor.

3.2. Zoznam susedov

Zoznam susedov nie je nič iné ako pole zoznamov. Veľkosť poľa je ekvivalentná počtu vrcholov v grafe.

Zoznam pri konkrétnom indexe poľa predstavuje susedné vrcholy vrcholu predstavované indexom poľa.

Pozrime sa, ako vyzerá zoznam susedstva pre náš jednoduchý graf z predchádzajúcej časti:

Toto znázornenie je je pomerne ťažké vytvoriť a menej efektívne pri dotazovaní. Avšak ponúka lepšia efektivita priestoru.

Na znázornenie grafu v tomto výučbe použijeme zoznam susednosti.

4. Grafy v Jave

Java nemá predvolenú implementáciu dátovej štruktúry grafu.

Graf však môžeme implementovať pomocou Java Collections.

Začnime definovaním vrcholu:

trieda Vertex {reťazcový štítok; Vrchol (reťazec) {this.label = label; } // rovná sa a hashCode}

Vyššie uvedená definícia vrcholu má iba označenie, ale toto môže predstavovať akúkoľvek možnú entitu Osoba alebo Mesto.

Pamätajte tiež na to musíme prepísať rovná sa () a hashCode () metódy potrebné na prácu s kolekciami Java.

Ako sme už diskutovali, graf nie je nič iné ako súhrn vrcholov a hrán, ktoré možno reprezentovať buď ako maticu susedstva, alebo ako zoznam susedov.

Pozrime sa, ako to môžeme definovať pomocou zoznamu susedstiev:

trieda Graf {súkromná mapa adjVertices; // štandardný konštruktor, getre, setre}

Ako vidíme tu, trieda Graf používa Mapa zo zbierok Java na definovanie zoznamu susedstiev.

Na štruktúre dát grafu je možné niekoľko operácií, ako napr vytváranie, aktualizovanie alebo vyhľadávanie cez graf.

Prejdeme si niektoré z bežnejších operácií a uvidíme, ako ich môžeme implementovať v prostredí Java.

5. Operácie mutácie grafov

Na začiatok si zadefinujeme niekoľko metód mutácie dátovej štruktúry grafu.

Definujme metódy pridávania a odstraňovania vrcholov:

void addVertex (String label) {adjVertices.putIfAbsent (new Vertex (label), new ArrayList ()); } void removeVertex (reťazec) {Vertex v = nový vrchol (štítok); adjVertices.values ​​(). stream (). forEach (e -> e.remove (v)); adjVertices.remove (nový vrchol (štítok)); }

Tieto metódy jednoducho pridávajú a odstraňujú prvky z vrcholy Set.

Teraz tiež definujeme metódu na pridanie okraja:

void addEdge (reťazec label1, reťazec label2) {Vertex v1 = nový vrchol (label1); Vrchol v2 = nový Vrchol (štítok2); adjVertices.get (v1). pridať (v2); adjVertices.get (v2). add (v1); }

Táto metóda vytvára nový Hrana a aktualizuje susedné vrcholy Mapa.

Podobným spôsobom definujeme removeEdge () metóda:

void removeEdge (reťazec label1, reťazec label2) {Vertex v1 = nový vrchol (label1); Vrchol v2 = nový Vrchol (štítok2); Zoznam eV1 = adjVertices.get (v1); Zoznam eV2 = adjVertices.get (v2); if (eV1! = null) eV1.remove (v2); if (eV2! = null) eV2.remove (v1); }

Ďalej sa pozrime, ako môžeme vytvoriť jednoduchý graf, ktorý sme nakreslili skôr, pomocou metód, ktoré sme doteraz definovali:

Graph createGraph () {Graph graph = new Graph (); graph.addVertex ("Bob"); graph.addVertex ("Alica"); graph.addVertex ("Značka"); graph.addVertex ("Rob"); graph.addVertex ("Mária"); graph.addEdge ("Bob", "Alice"); graph.addEdge ("Bob", "Rob"); graph.addEdge ("Alice", "Mark"); graph.addEdge ("Rob", "Mark"); graph.addEdge ("Alice", "Maria"); graph.addEdge ("Rob", "Maria"); návratový graf; }

Nakoniec definujeme metódu na získanie susedných vrcholov konkrétneho vrcholu:

Zoznam getAdjVertices (reťazcový štítok) {return adjVertices.get (nový vrchol (štítok)); }

6. Traversing a Graph

Teraz, keď máme definovanú štruktúru dát a funkcie grafu na ich vytvorenie a aktualizáciu, môžeme definovať niektoré ďalšie funkcie na prechádzanie grafom. Aby sme mohli vykonať akúkoľvek zmysluplnú akciu, ako je napríklad vyhľadávanie v grafe, musíme prejsť grafom.

Existujú dvoma možnými spôsobmi, ako prechádzať grafom, priečnym priečnikom hĺbky a priečnym priečnikom.

6.1. Prechod do hĺbky

Prechod hĺbkou prvý začína na ľubovoľnom koreňovom vrchole a skúma vrcholy čo najhlbšie pozdĺž každej vetvy a potom skúma vrcholy na rovnakej úrovni.

Definujme metódu na vykonanie priechodu prvej hĺbky:

Set depthFirstTraversal (Graph graph, String root) {Set opened = new LinkedHashSet (); Stack stack = nový Stack (); stack.push (root); while (! stack.isEmpty ()) {String vertex = stack.pop (); if (! navštívil.obsahuje (vrchol)) {navštívil.add (vrchol); pre (Vertex v: graph.getAdjVertices (vrchol)) {stack.push (v.label); }}} návrat navštívený; }

Tu, používame a Stoh na uloženie vrcholov, ktoré je potrebné prekonať.

Spustíme to na grafe, ktorý sme vytvorili v predchádzajúcej podsekcii:

assertEquals ("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal (graf, "Bob"). toString ());

Upozorňujeme, že ako koreň tu používame vrchol „Bob“, ale môže to byť akýkoľvek iný vrchol.

6.2. Prechod na šírku

Porovnateľne platí, že priechod na šírku začína na ľubovoľnom koreňovom vrchole a Skúma všetky susedné vrcholy na rovnakej úrovni, než pôjde hlbšie v grafe.

Teraz definujme spôsob vykonania priechodu šírkou ako prvý:

Nastaviť šírkuFirstTraversal (graf, koreň reťazca) {Navštívená sada = nová LinkedHashSet (); Poradie vo fronte = new LinkedList (); queue.add (root); navštívený.pridat (root); while (! queue.isEmpty ()) {String vertex = queue.poll (); pre (Vertex v: graph.getAdjVertices (vrchol)) {if (! navštívený.obsah (v.label)) {navštívený.add (v.label); queue.add (v.label); }}} návrat navštívený; }

Všimnite si, že priechod na šírku využíva Fronta na uloženie vrcholov, ktoré je potrebné prekonať.

Zopakujme tento prechod na rovnakom grafe:

assertEquals ("[Bob, Alice, Rob, Mark, Maria]", šírkaFirstTraversal (graf, "Bob"). toString ());

Opäť platí, že koreňový vrchol, ktorý je tu „Bob“, môže byť rovnako akýkoľvek iný vrchol.

7. Knižnice Java pre grafy

V Jave nie je nutné vždy graf implementovať úplne od začiatku. Existuje niekoľko otvorených a vyspelých knižníc, ktoré ponúkajú implementácie grafov.

V nasledujúcich niekoľkých podkapitolách si prejdeme niektoré z týchto knižníc.

7.1. JGraphT

JGraphT je jednou z najpopulárnejších knižníc v Jave pre štruktúru dát grafu. Umožňuje okrem iného vytvorenie jednoduchého grafu, riadeného grafu, váženého grafu.

Okrem toho ponúka mnoho možných algoritmov pre štruktúru dát grafu. Jeden z našich predchádzajúcich tutoriálov sa venuje JGraphT oveľa podrobnejšie.

7.2. Google Guava

Google Guava je sada knižníc Java, ktoré ponúkajú celý rad funkcií vrátane štruktúry dát grafu a jej algoritmov.

Podporuje vytváranie jednoduchých Graf, ValueGrapha Sieť. Tieto môžu byť definované ako Premenlivé alebo Nezmeniteľné.

7.3. Apache Commons

Apache Commons je projekt Apache, ktorý ponúka opakovane použiteľné komponenty Java. Patrí sem Commons Graph, ktorý ponúka sadu nástrojov na vytváranie a správu dátových štruktúr grafu. Toto tiež poskytuje bežné algoritmy grafov na prácu s dátovou štruktúrou.

7.4. Sourceforge JUNG

Java Universal Network / Graph (JUNG) je rámec Java, ktorý poskytuje rozšíriteľný jazyk pre modelovanie, analýzu a vizualizáciu akýchkoľvek údajov, ktoré je možné znázorniť ako graf.

JUNG podporuje množstvo algoritmov, ktoré zahŕňajú rutiny ako klastrovanie, rozklad a optimalizácia.

Tieto knižnice poskytujú množstvo implementácií založených na dátovej štruktúre grafov. Existujú aj také výkonnejšie rámce založené na grafoch, ako je napríklad Apache Giraph, ktorý sa v súčasnosti používa na Facebooku na analýzu grafu vytvoreného ich používateľmi, a Apache TinkerPop, ktorý sa bežne používa v databázach grafov.

8. Záver

V tomto článku sme diskutovali o grafe ako o dátovej štruktúre spolu s jej znázorneniami. Definovali sme veľmi jednoduchý graf v Jave pomocou Java Collections a tiež sme definovali bežné prechody pre graf.

Krátko sme hovorili aj o rôznych knižniciach dostupných v prostredí Java mimo platformy Java, ktorá poskytuje implementácie grafov.

Ako vždy, kód príkladov je k dispozícii na GitHub.