streamalism.org

1. Pregled

U ovom vodiču, razumjet ćemo osnovne pojmove grafa kao strukturu podataka.

Također ćemo istražiti njegovu implementaciju u Javi, zajedno s raznim operacijama koje su moguće na grafikonu. Također ćemo razgovarati o Java knjižnicama koje nude implementacije grafova.

2. Struktura podataka grafikona

Grafikon je a struktura podataka za pohranu povezanih podataka poput mreže ljudi na platformi društvenih medija.

Grafikon se sastoji od vrhova i bridova. Vrh predstavlja entitet (na primjer, ljudi) i rub predstavlja odnos između entiteta (na primjer, prijateljstva neke osobe).

Definirajmo jednostavni Graf kako bismo ovo bolje razumjeli:

Ovdje smo definirali jednostavan graf s pet vrhova i šest bridova. Kružnice su vrhovi koji predstavljaju ljude, a linije koje povezuju dva vrha rubovi koji predstavljaju prijatelje na mrežnom portalu.

Postoji nekoliko varijacija ovog jednostavnog grafa ovisno o svojstvima rubova. Kratko ćemo ih pregledati u sljedećim odjeljcima.

Međutim, usredotočit ćemo se samo na jednostavni graf koji je ovdje predstavljen za primjere Jave u ovom vodiču.

2.1. Usmjereni grafikon

Graf koji smo do sada definirali ima rubove bez ikakvog smjera. Ako ovi rubovi imaju smjer u njima, rezultirajući graf poznat je kao usmjereni graf.

Primjer za to može biti predstavljanje onih koji šalju zahtjev za prijateljstvo u prijateljstvu na mrežnom portalu:

Ovdje možemo vidjeti da rubovi imaju fiksni smjer. I rubovi mogu biti dvosmjerni.

2.2. Ponderirani grafikon

Ponovno, naš jednostavni graf ima nepristrane ili neponderirane rubove. Ako umjesto njih rubovi nose relativnu težinu, ovaj je graf poznat kao ponderirani graf.

Primjer praktične primjene ovoga može biti predstavljanje koliko je prijateljstvo relativno staro na internetskom portalu:

Ovdje možemo vidjeti da su rubovi povezani s utezima. To daje relativno značenje ovim rubovima.

3. Grafički prikazi

Grafikon se može predstaviti u različitim oblicima poput matrice susjedstva i popisa susjednosti. Svatko ima svoje prednosti i nedostatke u različitim postavkama.

Ove prikaze grafova predstavit ćemo u ovom odjeljku.

3.1. Matrica susjedstva

Matrica susjedstva je kvadratna matrica s dimenzijama ekvivalentnim broju vrhova u grafikonu.

Elementi matrice obično imaju vrijednosti '0' ili '1'. Vrijednost "1" označava susjedstvo između vrhova retka i stupca, a u suprotnom vrijednost "0".

Pogledajmo kako izgleda matrica susjedstva za naš jednostavni graf iz prethodnog odjeljka:

Ovaj prikaz je pošteno lakši za primjenu i učinkovit za postavljanje upita također. Međutim, jeste manje učinkovit s obzirom na zauzeti prostor.

3.2. Popis susjedstva

Popis susjednosti nije ništa drugo nego niz popisa. Veličina polja ekvivalentna je broju vrhova na grafikonu.

Popis na određenom indeksu niza predstavlja susjedne vrhove vrhova predstavljenih tim indeksom niza.

Pogledajmo kako izgleda popis susjedstva za naš jednostavni graf iz prethodnog odjeljka:

Ovo predstavljanje je relativno je teško stvoriti i manje učinkovito za postavljanje upita. Međutim, nudi bolja iskoristivost prostora.

Koristit ćemo popis susjedstva za predstavljanje grafa u ovom vodiču.

4. Grafovi na Javi

Java nema zadanu implementaciju strukture podataka grafa.

Međutim, grafikon možemo implementirati pomoću Java Collections.

Počnimo s definiranjem temena:

klasa Vertex {Oznaka niza; Vrh (oznaka niza) {this.label = label; } // jednako i hashCode}

Gornja definicija vrha sadrži samo oznaku, ali to može predstavljati bilo koji mogući entitet poput Osoba ili Grad.

Također, imajte na umu da moramo nadjačati jednako () i hashCode () metode koje su potrebne za rad s Java Zbirkama.

Kao što smo ranije raspravljali, graf nije ništa drugo nego skup vrhova i bridova koji se mogu predstaviti ili kao matrica susjedstva ili kao popis susjedstva.

Pogledajmo kako to možemo definirati pomoću popisa susjednosti ovdje:

razred Graf {privatna karta adjVertices; // standardni konstruktor, getteri, postavljači}

Kao što ovdje možemo vidjeti, razred Grafikon koristi Karta iz Java Collections za definiranje popisa susjednosti.

Postoji nekoliko mogućih operacija na strukturi podataka grafikona, kao što je stvaranje, ažuriranje ili pretraživanje kroz graf.

Provest ćemo neke od najčešćih operacija i vidjeti kako ih možemo implementirati u Javi.

5. Operacije mutacije grafikona

Za početak ćemo definirati neke metode za mutiranje strukture podataka grafikona.

Definirajmo metode za dodavanje i uklanjanje vrhova:

void addVertex (oznaka niza) {adjVertices.putIfAbsent (nova Vertex (oznaka), nova ArrayList ()); } void removeVertex (oznaka niza) {Vertex v = novi Vertex (oznaka); adjVertices.values ​​(). stream (). forEach (e -> e.remove (v)); adjVertices.remove (novi Vertex (oznaka)); }

Ove metode jednostavno dodaju i uklanjaju elemente iz vrhovi Set.

Ajmo sada definirati i metodu za dodavanje ruba:

void addEdge (String label1, String label2) {Vertex v1 = novi Vertex (label1); Vrh v2 = novi vrh (oznaka2); adjVertices.get (v1) .add (v2); adjVertices.get (v2) .add (v1); }

Ova metoda stvara novu Rub i ažurira susjedne vrhove Karta.

Na sličan ćemo način definirati i removeEdge () metoda:

void removeEdge (String label1, String label2) {Vertex v1 = novi Vertex (label1); Vrh v2 = novi vrh (oznaka2); Popis eV1 = adjVertices.get (v1); Popis eV2 = adjVertices.get (v2); if (eV1! = null) eV1.remove (v2); if (eV2! = null) eV2.remove (v1); }

Dalje, pogledajmo kako možemo stvoriti jednostavni graf koji smo prethodno nacrtali pomoću metoda koje smo do sada definirali:

Graf createGraph () {Grafikon grafa = novi Grafikon (); graph.addVertex ("Bob"); graph.addVertex ("Alice"); graph.addVertex ("Označi"); graph.addVertex ("Rob"); graph.addVertex ("Marija"); graph.addEdge ("Bob", "Alice"); graph.addEdge ("Bob", "Rob"); graph.addEdge ("Alice", "Oznaka"); graph.addEdge ("Rob", "Označi"); graph.addEdge ("Alice", "Maria"); graph.addEdge ("Rob", "Maria"); graf povratka; }

Napokon ćemo definirati metodu za dobivanje susjednih vrhova određenog vrha:

Popis getAdjVertices (oznaka niza) {return adjVertices.get (novi Vertex (oznaka)); }

6. Prelazak grafa

Sada kada imamo definiranu strukturu podataka podataka o grafu i funkcije za njihovo stvaranje i ažuriranje, možemo definirati neke dodatne funkcije za prelazak grafa. Moramo preći graf kako bismo izveli bilo koju značajnu radnju, poput pretraživanja unutar grafa.

Tamo su dva moguća načina prijelaza preko grafa, prijelaz prvo u dubinu i prvo u širinu.

6.1. Dubina-prvo prelazak

Prelazak prve dubine započinje proizvoljnim korijenskim vrhom i istražuje vrhove što dublje duž svake grane prije nego što istraži vrhove na istoj razini.

Definirajmo metodu za izvođenje prvo-dubinskog prelaska:

Postavi depthFirstTraversal (grafikon grafa, korijen niza) {Posećeno = novi LinkedHashSet (); Stog stoga = novi stog (); stog.push (korijen); while (! stack.isEmpty ()) {Vrh niza = stack.pop (); if (! posjetio.sadrži (vrh)) {posjetio.add (vrh); za (Vertex v: graph.getAdjVertices (vertex)) {stack.push (v.label); }}} povratak posjećen; }

Ovdje, koristimo a Stog za pohranu vrhova kojima treba prijeći.

Pokrenimo ovo na grafikonu koji smo stvorili u prethodnom pododjeljku:

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

Imajte na umu da ovdje koristimo vrh "Bob" kao korijen za prelazak, ali to može biti bilo koji drugi vrh.

6.2. Prijelaz širina-prvo

Usporedno, prijelaz u širinu započinje proizvoljnim korijenskim vrhom i istražuje sve susjedne vrhove na istoj razini prije nego što uđe dublje u grafikonu.

Ajmo sada definirati metodu za izvođenje prvo prelaska u širinu:

Postavi širinuFirstTraversal (grafikon grafikona, korijen niza) {Posećeno = novi LinkedHashSet (); Red čekanja = novi LinkedList (); queue.add (root); posjetio.add (korijen); while (! queue.isEmpty ()) {Vrh niza = queue.poll (); za (Vertex v: graph.getAdjVertices (vertex)) {if (! visit.contens (v.label)) {posjetio.add (v.label); queue.add (v.label); }}} povratak posjećen; }

Imajte na umu da je prijelaz u širinu koristi Red za pohranu vrhova kojima treba prijeći.

Ponovimo ovu obilaznicu na istom grafikonu:

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

Opet, korijenski vrh koji je ovdje "Bob" može biti bilo koji drugi vrh.

7. Java knjižnice za grafikone

Nije potrebno u Java uvijek implementirati graf od nule. Dostupno je nekoliko biblioteka otvorenog koda i zrelih biblioteka koje nude implementacije grafikona.

U sljedećih nekoliko pododjeljaka proći ćemo kroz neke od ovih knjižnica.

7.1. JGraphT

JGraphT je jedna od najpopularnijih knjižnica u Javi za strukturu podataka grafa. Omogućuje stvaranje jednostavnog, usmjerenog, ponderiranog grafa, između ostalog.

Uz to, nudi brojne moguće algoritme za strukturu podataka grafa. Jedan od naših prethodnih vodiča obrađuje JGraphT mnogo detaljnije.

7.2. Google Guava

Google Guava je skup Java knjižnica koje nude niz funkcija, uključujući strukturu podataka grafikona i njegove algoritme.

Podržava stvaranje jednostavnih Grafikon, ValueGraph, i Mreža. Oni se mogu definirati kao Promjenjivo ili Nepromjenjiv.

7.3. Apache Commons

Apache Commons je Apache projekt koji nudi Java komponente za višekratnu upotrebu. To uključuje Commons Graph koji nudi set alata za stvaranje i upravljanje strukturom podataka grafikona. Ovo također pruža uobičajene algoritme grafova za rad na strukturi podataka.

7.4. Sourceforge JUNG

Java Universal Network / Graph (JUNG) Java je okvir koji pruža proširivi jezik za modeliranje, analizu i vizualizaciju bilo kojih podataka koji se mogu predstaviti kao graf.

JUNG podržava brojne algoritme koji uključuju rutine poput grupiranja, razgradnje i optimizacije.

Te knjižnice pružaju brojne implementacije temeljene na strukturi podataka grafikona. Postoje također snažniji okviri temeljeni na grafikonima, kao što je Apache Giraph, koji se trenutno koristi na Facebooku za analizu grafa koji oblikuju njihovi korisnici, i Apache TinkerPop, koji se obično koristi na vrhu baza podataka grafova.

8. Zaključak

U ovom smo članku raspravljali o grafu kao strukturi podataka zajedno s njegovim prikazima. Definirali smo vrlo jednostavan graf u Javi pomoću Java kolekcija i definirali uobičajene prijelaze za graf.

Također smo kratko razgovarali o raznim bibliotekama dostupnim na Javi izvan Java platforme koja pruža implementacije grafova.

Kao i uvijek, kod za primjere dostupan je na GitHub-u.