streamalism.org

1. Oversigt

I denne vejledning Vi forstår de grundlæggende begreber i en graf som en datastruktur.

Vi vil også undersøge dens implementering i Java sammen med forskellige mulige operationer på en graf. Vi vil også diskutere Java-bibliotekerne, der tilbyder grafimplementeringer.

2. Grafdatastruktur

En graf er en datastruktur til lagring af tilsluttede data som et netværk af mennesker på en social medieplatform.

En graf består af hjørner og kanter. Et toppunkt repræsenterer enheden (for eksempel mennesker) og en kant repræsenterer forholdet mellem enheder (for eksempel en persons venskaber).

Lad os definere en simpel graf for at forstå dette bedre:

Her har vi defineret en simpel graf med fem hjørner og seks kanter. Cirklerne er hjørner, der repræsenterer mennesker, og linjerne, der forbinder to hjørner, er kanter, der repræsenterer venner på en online portal.

Der er et par variationer af denne enkle graf afhængigt af kanternes egenskaber. Lad os kort gennemgå dem i de næste sektioner.

Vi fokuserer dog kun på den enkle graf, der præsenteres her for Java-eksemplerne i denne vejledning.

2.1. Regisseret graf

Grafen, vi hidtil har defineret, har kanter uden nogen retning. Hvis disse kanter har en retning i demer den resulterende graf kendt som en rettet graf.

Et eksempel på dette kan være at repræsentere, hvem der sender venneanmodningen i et venskab på online-portalen:

Her kan vi se, at kanterne har en fast retning. Kanterne kan også være tovejs.

2.2. Vægtet graf

Igen har vores enkle graf kanter, der er upartiske eller uvægtede. Hvis i stedet disse kanter bærer relativ vægt, denne graf er kendt som en vægtet graf.

Et eksempel på en praktisk anvendelse af dette kan være at repræsentere, hvor relativt gammelt et venskab er på online-portalen:

Her kan vi se, at kanterne har vægte forbundet med dem. Dette giver en relativ betydning for disse kanter.

3. Grafrepræsentationer

En graf kan være repræsenteret i forskellige former som nærhedsmatrix og nærhedsliste. Hver og en har deres fordele og ulemper i en anden opsætning.

Vi introducerer disse grafrepræsentationer i dette afsnit.

3.1. Adjacency Matrix

En nærhedsmatrix er en firkantet matrix med dimensioner svarende til antallet af hjørner i grafen.

Elementerne i matrixen har typisk værdierne '0' eller '1'. En værdi på '1' angiver tilknytning mellem hjørnerne i rækken og kolonnen og ellers en værdi på '0'.

Lad os se, hvordan adjacency-matrixen ser ud for vores enkle graf fra det foregående afsnit:

Denne repræsentation er retfærdig lettere at implementere og effektiv at forespørge såvel. Det er det dog mindre effektiv med hensyn til pladsbesat.

3.2. Adjacency List

En nærhedsliste er intet andet end en række lister. Matrixens størrelse svarer til antallet af hjørner i grafen.

Listen ved et specifikt indeks for matrixen repræsenterer de tilstødende hjørner af toppunktet repræsenteret af det matrixindeks.

Lad os se, hvordan nærhedslisten ser ud for vores enkle graf fra det foregående afsnit:

Denne repræsentation er forholdsvis vanskelig at skabe og mindre effektiv at forespørge. Det tilbyder dog bedre pladseffektivitet.

Vi bruger nærhedslisten til at repræsentere grafen i denne vejledning.

4. Grafer i Java

Java har ikke en standardimplementering af grafdatastrukturen.

Vi kan dog implementere grafen ved hjælp af Java Collections.

Lad os begynde med at definere et toppunkt:

klasse Vertex {String label; Vertex (strengetiket) {this.label = label; } // er lig med og hashCode}

Ovenstående definition af toppunkt har bare en etiket, men dette kan repræsentere enhver mulig enhed som Person eller By.

Bemærk også, at vi er nødt til at tilsidesætte lige med() og hashCode () metoder, da disse er nødvendige for at arbejde med Java Collections.

Som vi diskuterede tidligere, er en graf intet andet end en samling af hjørner og kanter, der kan repræsenteres som enten en nærhedsmatrix eller en nærhedsliste.

Lad os se, hvordan vi kan definere dette ved hjælp af en nærhedsliste her:

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

Som vi kan se her, klassen Kurve bruger Kort fra Java-samlinger for at definere nærhedslisten.

Der er flere operationer mulige på en grafdatastruktur, f.eks oprettelse, opdatering eller søgning gennem grafen.

Vi gennemgår nogle af de mere almindelige operationer og ser, hvordan vi kan implementere dem i Java.

5. Grafmutationsoperationer

Til at begynde med definerer vi nogle metoder til at mutere grafdatastrukturen.

Lad os definere metoder til at tilføje og fjerne hjørner:

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

Disse metoder tilføjer og fjerner simpelthen elementer fra hjørner Set.

Lad os nu også definere en metode til at tilføje en kant:

ugyldig 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 metode skaber en ny Edge og opdaterer de tilstødende hjørner Kort.

På en lignende måde definerer vi 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); }

Lad os derefter se, hvordan vi kan oprette den enkle graf, vi har tegnet tidligere ved hjælp af de metoder, vi hidtil har defineret:

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 til at få de tilstødende hjørner af et bestemt toppunkt:

Liste getAdjVertices (strengetiket) {return adjVertices.get (ny Vertex (label)); }

6. Gennemgang af en graf

Nu hvor vi har grafdatastruktur og funktioner til at oprette og opdatere den definerede, kan vi definere nogle yderligere funktioner til at krydse grafen. Vi er nødt til at krydse en graf for at udføre enhver meningsfuld handling, som søgning i grafen.

Der er to mulige måder at krydse en graf på, dybde-første traversal og bredde-første traversal.

6.1. Dybde-første gennemgang

En dybde-første gennemgang starter ved et vilkårligt rodpunkt og udforsker hjørner så dybere som muligt langs hver gren, inden de udforsker hjørner på samme niveau.

Lad os definere en metode til at udføre dybde-første traversal:

Indstil depthFirstTraversal (grafgraf, strengrod) {Set besøgt = ny LinkedHashSet (); Stakstak = ny stak (); stack.push (rod); while (! stack.isEmpty ()) {String vertex = stack.pop (); hvis (! besøgt.indholder (toppunkt)) {besøgte.add (toppunkt); for (Vertex v: graph.getAdjVertices (vertex)) {stack.push (v.label); }}} returneret besøgt; }

Her, vi bruger en Stak at gemme de hjørner, der skal krydses.

Lad os køre dette på den graf, vi oprettede i det forrige underafsnit:

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

Bemærk, at vi bruger toppunkt “Bob” som vores rod til traversal her, men dette kan være ethvert andet toppunkt.

6.2. Bredde-første gennemgang

Sammenlignende starter en bredde-første traversal ved et vilkårligt rodpunkt og udforsker alle nærliggende hjørner på samme niveau, inden de går dybere i grafen.

Lad os nu definere en metode til at udføre bredden første traversal:

Indstil breadthFirstTraversal (grafgraf, strengrod) {Set besøgt = ny LinkedHashSet (); Kø-kø = ny LinkedList (); kø.tillæg (rod); visited.add (rod); while (! queue.isEmpty ()) {String vertex = queue.poll (); for (Vertex v: graph.getAdjVertices (vertex)) {if (! visited.contains (v.label)) {visited.add (v.label); kø.tillæg (v.mærke); }}} returneret besøgte; }

Bemærk, at en bredde-første gennemgang gør brug af Kø at gemme de hjørner, der skal krydses.

Lad os igen køre denne gennemgang på samme graf:

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

Igen kan rodpunktet, der er "Bob" her, lige så godt være ethvert andet toppunkt.

7. Java-biblioteker til grafer

Det er ikke nødvendigt altid at implementere grafen fra bunden i Java. Der er flere open source og modne biblioteker til rådighed, der tilbyder grafimplementeringer.

I de næste par underafsnit gennemgår vi nogle af disse biblioteker.

7.1. JGraphT

JGraphT er et af de mest populære biblioteker i Java til grafdatastrukturen. Det muliggør oprettelse af en simpel graf, rettet graf, vægtet graf, blandt andre.

Derudover tilbyder det mange mulige algoritmer på grafdatastrukturen. En af vores tidligere tutorials dækker JGraphT meget mere detaljeret.

7.2. Google Guava

Google Guava er et sæt Java-biblioteker, der tilbyder en række funktioner, herunder grafdatastruktur og dens algoritmer.

Det understøtter oprettelse af enkle Kurve, ValueGraphog Netværk. Disse kan defineres som Omskiftelig eller Uforanderlig.

7.3. Apache Commons

Apache Commons er et Apache-projekt, der tilbyder genanvendelige Java-komponenter. Dette inkluderer Commons Graph, der tilbyder et værktøjssæt til at oprette og administrere grafdatastruktur. Dette giver også almindelige grafalgoritmer til at fungere på datastrukturen.

7.4. Sourceforge JUNG

Java Universal Network / Graph (JUNG) er en Java-ramme, der giver udvideligt sprog til modellering, analyse og visualisering af alle data, der kan repræsenteres som en graf.

JUNG understøtter en række algoritmer, som inkluderer rutiner som klyngedannelse, nedbrydning og optimering.

Disse biblioteker giver et antal implementeringer baseret på grafdatastrukturen. Der er også mere kraftfulde rammer baseret på grafer, såsom Apache Giraph, der i øjeblikket bruges på Facebook til at analysere grafen, der er dannet af deres brugere, og Apache TinkerPop, der ofte bruges oven på grafdatabaser.

8. Konklusion

I denne artikel diskuterede vi grafen som en datastruktur sammen med dens repræsentationer. Vi definerede en meget enkel graf i Java ved hjælp af Java Collections og definerede også almindelige traversaler til grafen.

Vi talte også kort om forskellige biblioteker, der er tilgængelige i Java uden for Java-platformen, der giver grafimplementeringer.

Som altid er koden til eksemplerne tilgængelig på GitHub.