java graph tutorial how implement graph data structure
Denne omfattende Java-graf-tutorial forklarer grafdatastrukturen i detaljer. Det inkluderer, hvordan man opretter, implementerer, repræsenterer og gennemgår grafer i Java:
En grafdatastruktur repræsenterer hovedsageligt et netværk, der forbinder forskellige punkter. Disse punkter betegnes som hjørner, og de forbindelser, der forbinder disse hjørner, kaldes 'Kanter'. Så en graf g er defineret som et sæt hjørner V og kanter E, der forbinder disse hjørner.
Grafer bruges for det meste til at repræsentere forskellige netværk som computernetværk, sociale netværk osv. De kan også bruges til at repræsentere forskellige afhængigheder i software eller arkitekturer. Disse afhængighedsgrafer er meget nyttige til analyse af softwaren og til tider fejlretning af den.
=> Tjek ALLE Java-tutorials her.
Hvad du lærer:
- Java Graph Datastruktur
- Hvordan oprettes en graf?
- Grafimplementering i Java
- Java-grafbibliotek
- Konklusion
Java Graph Datastruktur
Nedenfor er en graf med fem hjørner {A, B, C, D, E} og kanter givet af {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Da kanterne ikke viser nogen retninger, er denne graf kendt som 'ikke-rettet graf'.
Bortset fra den ustyrede graf, der er vist ovenfor, er der flere varianter af grafen i Java.
Lad os diskutere disse varianter detaljeret.
Forskellige varianter af graf
Følgende er nogle af varianterne af grafen.
# 1) Direkte graf
En rettet graf eller digraf er en grafdatastruktur, hvor kanterne har en bestemt retning. De stammer fra et toppunkt og kulminerer til et andet toppunkt.
Følgende diagram viser eksemplet på rettet graf.
I ovenstående diagram er der en kant fra toppunkt A til toppunkt B. Men bemærk at A til B ikke er den samme som B til A som i ikke-rettet graf, medmindre der er en kant specificeret fra B til A.
En rettet graf er cyklisk, hvis der er mindst en sti, der har sit første og sidste toppunkt som det samme. I ovenstående diagram danner en sti A-> B-> C-> D-> E-> A en rettet cyklus eller cyklisk graf.
Omvendt er en rettet acyklisk graf en graf, hvor der ikke er nogen rettet cyklus, dvs. der er ingen sti, der danner en cyklus.
# 2) Vægtet graf
I en vægtet graf, en vægter knyttet til hver kant af grafen. Vægten angiver normalt afstanden mellem de to hjørner. Følgende diagram viser den vægtede graf. Da der ikke vises nogen retninger, er dette den ikke-retnede graf.
Bemærk, at en vægtet graf kan dirigeres eller ikke rettes.
Hvordan oprettes en graf?
Java giver ikke en fuldgyldig implementering af grafdatastrukturen. Vi kan dog repræsentere grafen ved hjælp af samlinger i Java. Vi kan også implementere en graf ved hjælp af dynamiske arrays som vektorer.
Normalt implementerer vi grafer i Java ved hjælp af HashMap-samling. HashMap-elementer er i form af nøgleværdipar. Vi kan repræsentere grafens tilstødelsesliste i et HashMap.
En mest almindelig måde at oprette en graf på er ved at bruge en af repræsentationerne af grafer som adjacency matrix eller adjacency list. Vi vil diskutere disse repræsentationer næste og derefter implementere grafen i Java ved hjælp af den nærhedsliste, som vi vil bruge ArrayList til.
Grafrepræsentation i Java
Grafrepræsentation betyder fremgangsmåden eller teknikken, hvor grafdata gemmes i computerens hukommelse.
Vi har to hovedrepræsentationer af grafer som vist nedenfor.
Adjacency Matrix
Adjacency Matrix er en lineær repræsentation af grafer. Denne matrix gemmer kortlægningen af hjørner og kanter på grafen. I tilknytningsmatrixen repræsenterer hjørner af grafen rækker og kolonner. Dette betyder, at hvis grafen har N-hjørner, så vil nærhedsmatricen have størrelse NxN.
Hvis V er et sæt hjørner i grafen, skal kryds Miji adjacency listen = 1 betyder, at der er en kant mellem hjørnerne i og j.
For bedre at forstå dette koncept tydeligt, lad os forberede en adjacency Matrix til en ikke-rettet graf.
Som det ses af ovenstående diagram, ser vi, at for toppunkt A er krydset AB og AE indstillet til 1, da der er en kant fra A til B og A til E. Tilsvarende er krydset BA sat til 1, da dette er en ikke-rettet graf og AB = BA. På samme måde har vi indstillet alle de andre kryds, hvor der er en kant, til 1.
Hvis grafen er rettet, skal krydset Mijvil kun blive sat til 1, hvis der er en klar kant rettet fra Vi til Vj.
Dette er vist i den følgende illustration.
Som vi kan se fra ovenstående diagram, er der en kant fra A til B. Så krydsning AB er sat til 1, men skæringspunkt BA er sat til 0. Dette skyldes, at der ikke er nogen kant rettet fra B til A.
Overvej hjørner E og D. Vi ser, at der er kanter fra E til D såvel som D til E. Derfor har vi indstillet begge disse skæringspunkter til 1 i nærhedsmatrix.
Nu går vi videre til vægtede grafer. Som vi ved for den vægtede graf, er et heltal også kendt som vægt forbundet med hver kant. Vi repræsenterer denne vægt i adjacency Matrix for den eksisterende kant. Denne vægt specificeres, når der er en kant fra et toppunkt til et andet i stedet for '1'.
Denne repræsentation er vist nedenfor.
Tilstødelsesliste
I stedet for at repræsentere en graf som en nærhedsmatrix, der er sekventiel i naturen, kan vi også bruge sammenkædet repræsentation. Denne sammenkædede repræsentation er kendt som nærhedslisten. En tilstødelsesliste er intet andet end en sammenkædet liste, og hver node på listen repræsenterer et toppunkt.
Tilstedeværelsen af en kant mellem to hjørner er angivet med en markør fra det første toppunkt til det andet. Denne tilstødelsesliste opretholdes for hvert toppunkt i grafen.
Når vi har krydset alle de tilstødende noder for en bestemt node, gemmer vi NULL i det næste markørfelt på den sidste node på adjacency-listen.
Nu bruger vi de ovennævnte grafer, som vi brugte til at repræsentere nærhedsmatrixen til at demonstrere nærhedslisten.
hvordan man åbner en .apk fil i windows
Ovenstående figur viser tilstødelseslisten for den ikke-rettede graf. Vi ser, at hvert toppunkt eller knudepunkt har sin nærhedsliste.
I tilfælde af den ikke-rettede graf er de samlede længder af nærhedslister normalt dobbelt så mange kanter. I den ovenstående graf er det samlede antal kanter 6, og summen eller summen af længden af hele adjacency-listen er 12.
Lad os nu udarbejde en nærhedsliste til den dirigerede graf.
Som det ses af ovenstående figur, er den samlede længde af tilgrænsningslisterne i grafen i den rettede graf lig med antallet af kanter i grafen. I ovenstående graf er der 9 kanter og summen af længderne på nærhedslister for denne graf = 9.
Lad os nu overveje følgende vægtede rettet graf. Bemærk, at hver kant af den vægtede graf har en vægt tilknyttet. Så når vi repræsenterer denne graf med nærhedslisten, skal vi tilføje et nyt felt til hver listeknude, der angiver kantens vægt.
Tilstødelisten for den vægtede graf er vist nedenfor.
Ovenstående diagram viser den vægtede graf og dens nærhedsliste. Bemærk, at der er et nyt mellemrum i nærhedslisten, der angiver vægten af hver knude.
Grafimplementering i Java
Det følgende program viser implementeringen af en graf i Java. Her har vi brugt nærhedslisten til at repræsentere grafen.
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i Produktion:
Graph Traversal Java
For at udføre en meningsfuld handling som at søge efter tilstedeværelsen af data er vi nødt til at krydse grafen, så hvert toppunkt og kanten af grafen besøges mindst en gang. Dette gøres ved hjælp af grafalgoritmer, der kun er et sæt instruktioner, der hjælper os med at krydse grafen.
Der understøttes to algoritmer til at krydse grafen i Java .
- Dybde-første gennemgang
- Bredde-første gennemkørsel
Dybde-første gennemgang
Dybde-første søgning (DFS) er en teknik, der bruges til at krydse et træ eller en graf. DFS-teknik starter med en rodnode og krydser derefter de tilstødende noder i rodnoden ved at gå dybere ind i grafen. I DFS-teknikken krydses noderne dybdegående, indtil der ikke er flere børn at udforske.
Når vi når bladknuden (ikke flere underknudepunkter), sporer DFS tilbage og starter med andre knudepunkter og udfører gennemkørsel på en lignende måde. DFS-teknik bruger en stakdatastruktur til at gemme de noder, der gennemgås.
Følgende er algoritmen for DFS-teknikken.
Algoritme
Trin 1: Start med rodnoden og indsæt den i stakken
Trin 2: Pop elementet fra stakken, og indsæt det på listen 'besøgt'
Trin 3: For node, der er markeret som 'besøgte' (eller i besøgsliste), skal du tilføje de tilstødende noder for denne node, der endnu ikke er markeret som besøgt, til stakken.
Trin 4: Gentag trin 2 og 3, indtil stakken er tom.
Illustration af DFS-teknik
Nu illustrerer vi DFS-teknikken ved hjælp af et korrekt eksempel på en graf.
Nedenfor er et eksempel på en graf. Vi opretholder stak for at gemme udforskede noder og en liste til lagring af besøgte noder.
Vi starter med A til at begynde med, markerer det som besøgt og føjer det til den besøgte liste. Derefter overvejer vi alle de tilstødende noder i A og skubber disse noder på stakken som vist nedenfor.
Dernæst popper vi en node fra stakken, dvs. B, og markerer den som besøgt. Vi tilføjer det derefter til listen 'besøgte'. Dette er vist nedenfor.
Nu betragter vi de tilstødende noder af B, som er A og C. Ud af dette er A allerede besøgt. Så vi ignorerer det. Dernæst popper vi C fra stakken. Marker C som besøgt. Den tilstødende node af C, dvs. E, føjes til stakken.
Dernæst popper vi den næste node E fra stakken og markerer den som besøgt. Node E's tilstødende knude er C, som allerede er besøgt. Så vi ignorerer det.
Nu er kun node D tilbage i stakken. Så vi markerer det som besøgt. Dens tilstødende knude er A, som allerede er besøgt. Så vi føjer det ikke til stakken.
På dette tidspunkt er stakken tom. Dette betyder, at vi har gennemført dybde-første traversal for den givne graf.
Den besøgte liste giver den endelige sekvens af traversal ved hjælp af dybde-første teknikken. Den endelige DFS-sekvens for ovenstående graf er A-> B-> C-> E-> D.
DFS-implementering
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list[]; // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i Produktion:
salesforce interviewspørgsmål og svar til erfarne udviklere
Anvendelser af DFS
# 1) Registrer en cyklus i en graf: DFS letter detekteringen af en cyklus i en graf, når vi kan gå tilbage til en kant.
# 2) Pathfinding: Som vi allerede har set i DFS-illustrationen, kan vi i lyset af de to hjørner finde stien mellem disse to hjørner.
# 3) Minimum spænder over træ og korteste sti: Hvis vi kører DFS-teknikken på den ikke-vægtede graf, giver det os det mindst spændende træ og den kortsluttede sti.
# 4) Topologisk sortering: Topologisk sortering bruges, når vi skal planlægge jobbet. Vi har afhængigheder mellem forskellige job. Vi kan også bruge topologisk sortering til at løse afhængigheder blandt linkere, instruktionsplanlæggere, dataserialisering osv.
Bredde-første gennemgang
BFS-teknik (Breadth-first) bruger en kø til at gemme noderne i grafen. I modsætning til DFS-teknikken krydser vi i BFS grafen bredt. Dette betyder, at vi krydser grafen niveauvis. Når vi udforsker alle hjørner eller knudepunkter på et niveau, fortsætter vi til det næste niveau.
Nedenfor er en algoritme for bredde-første traversal teknik .
Algoritme
Lad os se algoritmen for BFS-teknikken.
Givet en graf G, som vi har brug for til at udføre BFS-teknikken.
- Trin 1: Begynd med rodnoden, og indsæt den i køen.
- Trin 2: Gentag trin 3 og 4 for alle noder i grafen.
- Trin 3: Fjern rodnoden fra køen, og tilføj den til listen Besøgte.
- Trin 4: Føj nu alle de tilstødende noder i rodnoden til køen, og gentag trin 2 til 4 for hver node. [END OF LOOP]
- Trin 6: AFSLUT
Illustration af BFS
Lad os illustrere BFS-teknikken ved hjælp af et eksempel på en graf vist nedenfor. Bemærk, at vi har opretholdt en liste med navnet 'Besøgte' og en kø. Vi bruger den samme graf, som vi brugte i DFS-eksemplet til klarhedsformål.
Først starter vi med rod, dvs. node A, og føjer den til den besøgte liste. Alle de tilstødende noder i noden A, dvs. B, C og D, føjes til køen.
Dernæst fjerner vi node B fra køen. Vi føjer det til listen Besøgte og markerer det som besøgt. Dernæst udforsker vi de tilstødende noder for B i køen (C er allerede i køen). En anden tilstødende node A er allerede besøgt, så vi ignorerer den.
Dernæst fjerner vi node C fra køen og markerer den som besøgt. Vi tilføjer C til den besøgte liste, og dens tilstødende node E føjes til køen.
Dernæst sletter vi D fra køen og markerer den som besøgt. Node D's tilstødende knudepunkt A er allerede besøgt, så vi ignorerer det.
Så nu er kun node E i køen. Vi markerer det som besøgt og føjer det til den besøgte liste. Den tilstødende node af E er C, som allerede er besøgt. Så ignorer det.
På dette tidspunkt er køen tom, og den besøgte liste har den rækkefølge, vi opnåede som et resultat af BFS-traversal. Sekvensen er A-> B-> C-> D-> E.
BFS-implementering
Følgende Java-program viser implementeringen af BFS-teknikken.
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list[]; //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i Produktion:
Anvendelser af BFS Traversal
# 1) Affaldssamling: En af algoritmerne, der bruges af skraldopsamlingsteknikken til at kopiere affaldssamling, er 'Cheneys algoritme'. Denne algoritme bruger en bredeste-første traversal teknik.
# 2) Broadcasting i netværk: Broadcasting af pakker fra et punkt til et andet i et netværk sker ved hjælp af BFS-teknikken.
# 3) GPS-navigation: Vi kan bruge BFS-teknikken til at finde tilstødende noder, mens vi navigerer ved hjælp af GPS.
# 4) Sociale netværkswebsteder: BFS-teknik bruges også på sociale netværkswebsteder for at finde netværket af mennesker, der omgiver en bestemt person.
# 5) Korteste sti og minimum spændende træ i ikke-vægtet graf: I den uvægtede graf kan BFS-teknikken bruges til at finde et minimum spændende træ og den korteste sti mellem noderne.
Java-grafbibliotek
Java gør det ikke obligatorisk for programmører at altid implementere graferne i programmet. Java leverer mange klare biblioteker, der kan bruges direkte til at gøre brug af grafer i programmet. Disse biblioteker har al graf API-funktionalitet, der kræves for at udnytte grafen og dens forskellige funktioner fuldt ud.
Nedenfor er en kort introduktion til nogle af grafbibliotekerne i Java.
# 1) Google Guava: Google Guava tilbyder et rigt bibliotek, der understøtter grafer og algoritmer, herunder enkle grafer, netværk, værdigrafer osv.
# 2) Apache Commons: Apache Commons er et Apache-projekt, der leverer grafdatastrukturkomponenter og API'er, der har algoritmer, der fungerer på denne grafdatastruktur. Disse komponenter kan genbruges.
# 3) JGraphT: JGraphT er et af de meget anvendte Java-grafbiblioteker. Det giver grafdatastrukturfunktionalitet, der indeholder enkel graf, rettet graf, vægtet graf osv. Såvel som algoritmer og API'er, der arbejder med grafdatastrukturen.
# 4) SourceForge JUNG: JUNG står for “Java Universal Network / Graph” og er en Java-ramme. JUNG giver et udvideligt sprog til analyse, visualisering og modellering af de data, som vi ønsker skal repræsenteres som en graf.
JUNG leverer også forskellige algoritmer og rutiner til nedbrydning, klyngedannelse, optimering osv.
Ofte stillede spørgsmål
Q # 1) Hvad er en graf i Java?
Svar: En grafdatastruktur lagrer hovedsageligt forbundne data, for eksempel, et netværk af mennesker eller et netværk af byer. En grafdatastruktur består typisk af noder eller punkter kaldet hjørner. Hvert toppunkt er forbundet til et andet toppunkt ved hjælp af links kaldet kanter.
Q # 2) Hvad er typerne af grafer?
Svar: Forskellige typer grafer er angivet nedenfor.
- Linje graf: En linjediagram bruges til at plotte ændringer i en bestemt egenskab i forhold til tid.
- Søjlediagram: Søjlediagrammer sammenligner numeriske værdier for enheder som befolkningen i forskellige byer, læsefærdigheder i hele landet osv.
Bortset fra disse hovedtyper har vi også andre typer som piktogram, histogram, arealdiagram, spredningsdiagram osv.
Q # 3) Hvad er en tilsluttet graf?
Svar: En forbundet graf er en graf, hvor hvert toppunkt er forbundet med et andet toppunkt. Derfor i den tilsluttede graf kan vi komme til hvert toppunkt fra hvert andet toppunkt.
Q # 4) Hvad er anvendelsen af grafen?
det understøtter spørgsmål og svar på teknikersamtale
Svar: Grafer bruges i en række applikationer. Grafen kan bruges til at repræsentere et komplekst netværk. Grafer bruges også i applikationer til socialt netværk til at betegne netværket af mennesker såvel som til applikationer som at finde tilstødende mennesker eller forbindelser.
Grafer bruges til at betegne strømmen af beregning inden for datalogi.
Q # 5) Hvordan gemmer du en graf?
Svar: Der er tre måder at gemme en graf i hukommelsen på:
# 1) Vi kan gemme noder eller hjørner som objekter og kanter som pegepinde.
#to) Vi kan også gemme grafer som nærhedsmatrix, hvis rækker og kolonner er de samme som antallet af hjørner. Skæringspunktet for hver række og kolonne angiver tilstedeværelsen eller fraværet af en kant. I den ikke-vægtede graf betegnes tilstedeværelsen af en kant med 1, mens den i den vægtede graf erstattes af kantens vægt.
# 3) Den sidste tilgang til lagring af en graf er ved hjælp af en nærhedsliste over kanter mellem grafhjørner eller noder. Hver knude eller toppunkt har sin nærhedsliste.
Konklusion
I denne vejledning har vi diskuteret grafer i Java detaljeret. Vi udforskede de forskellige typer af grafer, implementering af graf og traversal teknikker. Grafer kan bruges til at finde den korteste sti mellem noder.
I vores kommende tutorials vil vi fortsætte med at udforske grafer ved at diskutere et par måder at finde den korteste vej.
=> Pas på den enkle Java-træningsserie her.
Anbefalet læsning
- Java Reflection Tutorial med eksempler
- Sådan implementeres Dijkstras algoritme i Java
- Java SWING Tutorial: Container, komponenter og håndtering af begivenheder
- JAVA-vejledning til begyndere: 100+ praktiske Java-videovejledninger
- TreeMap I Java - Vejledning med Java TreeMap-eksempler
- Adgang modifikatorer i Java - vejledning med eksempler
- Java String med String Buffer og String Builder Tutorial
- Java String indeholder () Metodevejledning med eksempler
