streamalism.org

1. Oversikt

I denne veiledningen, vi vil forstå de grunnleggende begrepene i en graf som datastruktur.

Vi vil også utforske implementeringen i Java sammen med forskjellige mulige operasjoner i en graf. Vi vil også diskutere Java-bibliotekene som tilbyr grafimplementeringer.

2. Graf Datastruktur

En graf er en datastruktur for lagring av tilkoblede data som et nettverk av mennesker på en sosial medieplattform.

En graf består av hjørner og kanter. Et toppunkt representerer enheten (for eksempel mennesker) og en kant representerer forholdet mellom enheter (for eksempel en persons vennskap).

La oss definere en enkel graf for å forstå dette bedre:

Her har vi definert en enkel graf med fem hjørner og seks kanter. Sirklene er hjørner som representerer mennesker, og linjene som forbinder to hjørner er kanter som representerer venner på en online portal.

Det er noen varianter av denne enkle grafen, avhengig av egenskapene til kantene. La oss kort gå gjennom dem i de neste avsnittene.

Imidlertid vil vi bare fokusere på den enkle grafen som presenteres her for Java-eksemplene i denne opplæringen.

2.1. Regissert graf

Grafen vi har definert så langt, har kanter uten noen retning. Hvis disse kantene har en retning i dem, er den resulterende grafen kjent som en rettet graf.

Et eksempel på dette kan være å representere hvem som sender venneforespørselen i et vennskap på nettportalen:

Her kan vi se at kantene har en fast retning. Kantene kan også være toveis.

2.2. Vektet vekt

Igjen, vår enkle graf har kanter som er upartiske eller uveide. Hvis i stedet disse kantene har relativ vekt, er denne grafen kjent som en vektet graf.

Et eksempel på en praktisk anvendelse av dette kan være å representere hvor relativt gammelt et vennskap er på nettportalen:

Her kan vi se at kantene har vekter knyttet til seg. Dette gir en relativ betydning for disse kantene.

3. Grafrepresentasjoner

En graf kan være representert i forskjellige former som nærhetsmatrise og nærhetsliste. Hver og en har sine fordeler og ulemper i et annet oppsett.

Vi introduserer disse grafframstillingene i denne delen.

3.1. Adjacency Matrix

En tilknytningsmatrise er en firkantet matrise med dimensjoner som tilsvarer antall hjørner i grafen.

Elementene i matrisen har vanligvis verdiene '0' eller '1'. Verdien ‘1’ indikerer nærhet mellom toppunktene i raden og kolonnen og ellers verdien ‘0’.

La oss se hvordan nærhetsmatrisen ser ut for vår enkle graf fra forrige avsnitt:

Denne representasjonen er rettferdig lettere å implementere og effektiv å spørre også. Det er det imidlertid mindre effektiv med hensyn til plassbesatt.

3.2. Tilstøtningsliste

En nærhetsliste er ingenting annet enn en rekke lister. Matrisens størrelse tilsvarer antall hjørner i grafen.

Listen ved en bestemt indeks av matrisen representerer de tilstøtende toppunktene til toppunktet representert av den matriceindeksen.

La oss se hvordan adjacency-listen ser ut for vår enkle graf fra forrige avsnitt:

Denne representasjonen er relativt vanskelig å lage og mindre effektiv å spørre. Imidlertid tilbyr det bedre plasseffektivitet.

Vi bruker adjacency-listen til å representere grafen i denne opplæringen.

4. Grafer i Java

Java har ikke en standardimplementering av grafdatastrukturen.

Imidlertid kan vi implementere grafen ved hjelp av Java Collections.

La oss begynne med å definere et toppunkt:

klasse Vertex {String label; Vertex (strengmerke) {this.label = label; } // er lik og hashCode}

Ovennevnte definisjon av toppunkt har bare en etikett, men dette kan representere enhver mulig enhet som Person eller By.

Vær også oppmerksom på at vi må overstyre er lik() og hashCode () metoder som disse er nødvendige for å jobbe med Java Collections.

Som vi diskuterte tidligere, er en graf ingenting annet enn en samling av hjørner og kanter som kan representeres som enten en nærhetsmatrise eller en nærhetsliste.

La oss se hvordan vi kan definere dette ved hjelp av en tilknytningsliste her:

klasse Graf {privat Kart adjVertices; // standard konstruktør, getters, setters}

Som vi kan se her, klassen Kurve bruker Kart fra Java Collections for å definere nærhetslisten.

Det er flere operasjoner mulig på en grafdatastruktur, for eksempel opprette, oppdatere eller søke gjennom grafen.

Vi vil gå gjennom noen av de vanligste operasjonene og se hvordan vi kan implementere dem i Java.

5. Grafmutasjonsoperasjoner

Til å begynne med vil vi definere noen metoder for å mutere grafdatastrukturen.

La oss definere metoder for å legge til og fjerne hjørner:

void addVertex (String label) {adjVertices.putIfAbsent (new Vertex (label), new ArrayList ()); } ugyldig removeVertex (strengetikett) {Vertex v = ny Vertex (label); adjVertices.values ​​(). stream (). forEach (e -> e.remove (v)); adjVertices.remove (ny Vertex (etikett)); }

Disse metodene bare legger til og fjerner elementer fra hjørner Sett.

La oss nå definere en metode for å legge til en kant:

void addEdge (String label1, String label2) {Vertex v1 = new Vertex (label1); Vertex v2 = ny Vertex (label2); adjVertices.get (v1) .add (v2); adjVertices.get (v2) .add (v1); }

Denne metoden skaper en ny Kant og oppdaterer de tilstøtende toppunktene Kart.

På en lignende måte vil vi definere removeEdge () metode:

ugyldig removeEdge (String label1, String label2) {Vertex v1 = new Vertex (label1); Vertex v2 = ny Vertex (label2); Liste eV1 = adjVertices.get (v1); Liste eV2 = adjVertices.get (v2); hvis (eV1! = null) eV1.remove (v2); hvis (eV2! = null) eV2.remove (v1); }

Deretter, la oss se hvordan vi kan lage den enkle grafen vi har tegnet tidligere ved hjelp av metodene vi har definert så langt:

Graf createGraph () {Grafgraf = ny Graf (); graph.addVertex ("Bob"); graph.addVertex ("Alice"); graph.addVertex ("Mark"); graph.addVertex ("Rob"); graph.addVertex ("Maria"); graph.addEdge ("Bob", "Alice"); graph.addEdge ("Bob", "Rob"); graph.addEdge ("Alice", "Mark"); graph.addEdge ("Rob", "Mark"); graph.addEdge ("Alice", "Maria"); graph.addEdge ("Rob", "Maria"); retur graf; }

Vi definerer endelig en metode for å få de tilstøtende toppunktene til et bestemt toppunkt:

Liste getAdjVertices (strengetikett) {return adjVertices.get (new Vertex (label)); }

6. Gjennomgang av en graf

Nå som vi har grafdatastruktur og funksjoner for å opprette og oppdatere den definert, kan vi definere noen tilleggsfunksjoner for å krysse grafen. Vi må krysse en graf for å utføre noen meningsfylt handling, som å søke i grafen.

Det er to mulige måter å krysse en graf, dybde-første traversal og bredde-første traversal.

6.1. Dybde-første gjennomgang

En dybde-første gjennomgang starter ved et vilkårlig rotpunkt og utforsker hjørner så dypere som mulig langs hver gren før de utforsker hjørner på samme nivå.

La oss definere en metode for å utføre dybde-første traversal:

Sett depthFirstTraversal (grafgraf, strengrot) {sett besøkt = ny LinkedHashSet (); Stack stack = new Stack (); stack.push (root); while (! stack.isEmpty ()) {String toppunkt = stack.pop (); if (! visited.contains (toppunkt)) {besøkt.add (toppunkt); for (Vertex v: graph.getAdjVertices (toppunkt)) {stack.push (v.label); }}} besøk tilbake; }

Her, vi bruker en Stable for å lagre toppunktene som må krysses.

La oss kjøre dette på grafen vi opprettet i forrige underavsnitt:

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

Vær oppmerksom på at vi bruker toppunkt "Bob" som vår rot for traversal her, men dette kan være hvilken som helst annen toppunkt.

6.2. Bredde-første gjennomgang

Sammenlignende starter en bredde-første traversal ved et vilkårlig rotpunkt og utforsker alle nærliggende hjørner på samme nivå før du går dypere i grafen.

La oss nå definere en metode for å utføre bredde-første traversal:

Sett breddeFirstTraversal (grafgraf, strengrot) {Sett besøkt = ny LinkedHashSet (); Kø-kø = ny LinkedList (); kø.tillegge (rot); besøkte.add (root); while (! queue.isEmpty ()) {String toppunkt = queue.poll (); for (Vertex v: graph.getAdjVertices (toppunkt)) {if (! visited.contains (v.label)) {visited.add (v.label); kø.add (v.label); }}} besøk tilbake; }

Merk at en bredde-første traversal bruker Kø for å lagre toppunktene som må krysses.

La oss igjen kjøre denne gjennomgangen på samme graf:

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

Igjen, rotpunktet som er "Bob" her kan også være et hvilket som helst annet toppunkt.

7. Java-biblioteker for grafer

Det er ikke nødvendig å alltid implementere grafen fra bunnen av i Java. Det er flere open source og modne biblioteker tilgjengelig som tilbyr grafimplementeringer.

I de neste få delene vil vi gå gjennom noen av disse bibliotekene.

7.1. JGraphT

JGraphT er et av de mest populære bibliotekene i Java for grafdatastrukturen. Det gjør det mulig å lage en enkel graf, rettet graf, vektet graf, blant andre.

I tillegg tilbyr den mange mulige algoritmer på grafdatastrukturen. En av våre tidligere veiledninger dekker JGraphT mye mer detaljert.

7.2. Google Guava

Google Guava er et sett med Java-biblioteker som tilbyr en rekke funksjoner, inkludert grafdatastruktur og dens algoritmer.

Den støtter å lage enkle Kurve, ValueGraph, og Nettverk. Disse kan defineres som Muterbar eller Uforanderlig.

7.3. Apache Commons

Apache Commons er et Apache-prosjekt som tilbyr gjenbrukbare Java-komponenter. Dette inkluderer Commons Graph som tilbyr et verktøysett for å opprette og administrere grafdatastruktur. Dette gir også vanlige grafalgoritmer for å operere på datastrukturen.

7.4. Sourceforge JUNG

Java Universal Network / Graph (JUNG) er et Java-rammeverk som gir utvidbart språk for modellering, analyse og visualisering av data som kan vises som en graf.

JUNG støtter en rekke algoritmer som inkluderer rutiner som klynging, spaltning og optimalisering.

Disse bibliotekene gir en rekke implementeringer basert på grafdatastrukturen. Det er også kraftigere rammer basert på grafer, som Apache Giraph, som for tiden brukes på Facebook for å analysere grafen som ble dannet av brukerne, og Apache TinkerPop, ofte brukt på toppen av grafdatabaser.

8. Konklusjon

I denne artikkelen diskuterte vi grafen som en datastruktur sammen med dens representasjoner. Vi definerte en veldig enkel graf i Java ved hjelp av Java Collections og definerte også vanlige traversaler for grafen.

Vi snakket også kort om forskjellige biblioteker som er tilgjengelige i Java utenfor Java-plattformen, som gir grafimplementeringer.

Som alltid er koden for eksemplene tilgjengelig på GitHub.