java graph tutorial how implement graph data structure
Denne omfattende Java-grafopplæringen forklarer grafdatastrukturen i detalj. Den inkluderer hvordan du lager, implementerer, representerer og krysser grafer i Java:
En grafdatastruktur representerer hovedsakelig et nettverk som forbinder forskjellige punkter. Disse punktene blir betegnet som hjørner, og koblingene som forbinder disse hjørnene kalles 'Kanter'. Så en graf g er definert som et sett med hjørner V og kantene E som forbinder disse hjørnene.
Grafer brukes mest til å representere forskjellige nettverk som datanettverk, sosiale nettverk, etc. De kan også brukes til å representere forskjellige avhengigheter i programvare eller arkitekturer. Disse avhengighetsgrafene er veldig nyttige for å analysere programvaren og til tider feilsøke den.
=> Sjekk ALLE Java-opplæringsprogrammer her.
Hva du vil lære:
- Java Graph Datastruktur
- Hvordan lage en graf?
- Grafimplementering i Java
- Java Graph Library
- Konklusjon
Java Graph Datastruktur
Nedenfor er en graf med fem hjørner {A, B, C, D, E} og kanter gitt av {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Siden kantene ikke viser noen retninger, er denne grafen kjent som 'ikke-rettet graf'.

Bortsett fra den ikke-rettede grafen vist ovenfor, er det flere varianter av grafen i Java.
La oss diskutere disse variantene i detalj.
Forskjellige varianter av graf
Følgende er noen av variantene av grafen.
# 1) Regissert graf
En rettet graf eller digraf er en grafdatastruktur der kantene har en bestemt retning. De stammer fra ett toppunkt og kulminerer til et annet toppunkt.
Følgende diagram viser eksemplet på rettet graf.

I diagrammet ovenfor er det en kant fra toppunkt A til toppunkt B. Men merk at A til B ikke er den samme som B til A som i ikke-rettet graf, med mindre det er en kant spesifisert fra B til A.
En rettet graf er syklisk hvis det er minst en bane som har sin første og siste toppunkt som den samme. I diagrammet ovenfor danner en sti A-> B-> C-> D-> E-> A en rettet syklus eller syklisk graf.
Omvendt er en rettet asyklisk graf en graf der det ikke er noen rettet syklus, dvs. det er ingen bane som danner en syklus.
# 2) Vektet graf
I en vektet graf, en vekter knyttet til hver kant av grafen. Vekten angir normalt avstanden mellom de to toppunktene. Følgende diagram viser den vektede grafen. Ettersom ingen retninger vises, er dette den ikke-rettet grafen.

Merk at en vektet graf kan rettes eller ikke rettes.
Hvordan lage en graf?
Java gir ikke en fullverdig implementering av grafdatastrukturen. Imidlertid kan vi representere grafen programmatisk ved hjelp av samlinger i Java. Vi kan også implementere en graf ved hjelp av dynamiske matriser som vektorer.
Vanligvis implementerer vi grafer i Java ved hjelp av HashMap-samlingen. HashMap-elementer er i form av nøkkelverdipar. Vi kan representere diagrammet for tilknytning av graf i et HashMap.
En vanlig måte å lage en graf på er å bruke en av representasjonene av grafer som nærhetsmatrise eller nærhetsliste. Vi vil diskutere disse representasjonene neste, og deretter implementere grafen i Java ved hjelp av adjacency-listen som vi vil bruke ArrayList for.
Grafrepresentasjon i Java
Grafrepresentasjon betyr tilnærmingen eller teknikken der grafdata lagres i datamaskinens minne.
Vi har to hovedrepresentasjoner av grafer som vist nedenfor.
Adjacency Matrix
Adjacency Matrix er en lineær representasjon av grafer. Denne matrisen lagrer kartleggingen av hjørner og kanter i grafen. I tilknytningsmatrisen representerer hjørner av grafen rader og kolonner. Dette betyr at hvis grafen har N-hjørner, vil nærhetsmatrisen ha størrelse NxN.
hvordan man kaller en funksjon i hovedpyton
Hvis V er et sett med hjørner av grafen, så krysser Miji tilknytningslisten = 1 betyr at det er en kant mellom toppunktene i og j.
For å bedre forstå dette konseptet tydelig, la oss forberede en tilknytningsmatrise for en ikke-rettet graf.
Som det ses av diagrammet ovenfor, ser vi at for toppunkt A er kryssene AB og AE satt til 1 da det er en kant fra A til B og A til E. Tilsvarende er krysset BA satt til 1, da dette er en ikke-rettet graf og AB = BA. På samme måte har vi satt alle de andre kryssene som det er en kant til 1.
I tilfelle grafen er rettet, vil krysset Mijvil bare bli satt til 1 hvis det er en klar kant som er rettet fra Vi til Vj.
Dette vises i følgende illustrasjon.
Som vi kan se fra diagrammet ovenfor, er det en kant fra A til B. Så krysset AB er satt til 1, men skjæringspunktet BA er satt til 0. Dette er fordi det ikke er noen kant rettet fra B til A.
Tenk på hjørnene E og D. Vi ser at det er kanter fra E til D så vel som D til E. Derfor har vi satt begge disse skjæringspunktene til 1 i nærhetsmatrise.
Nå går vi videre til vektede grafer. Som vi vet for den vektede grafen, er et heltall også kjent som vekt assosiert med hver kant. Vi representerer denne vekten i nærmatrisen for kanten som eksisterer. Denne vekten spesifiseres når det er en kant fra et toppunkt til et annet i stedet for ‘1’.
Denne representasjonen er vist nedenfor.
Tilstøtningsliste
I stedet for å representere en graf som en nærhetsmatrise som er sekvensiell i naturen, kan vi også bruke koblet representasjon. Denne tilknyttede representasjonen er kjent som adjacency-listen. En tilknytningsliste er bare en koblet liste, og hver node i listen representerer et toppunkt.
Tilstedeværelsen av en kant mellom to hjørner er betegnet med en peker fra det første toppunktet til det andre. Denne tilknytningslisten opprettholdes for hvert toppunkt i grafen.
Når vi har krysset alle tilstøtende noder for en bestemt node, lagrer vi NULL i det neste pekefeltet til den siste noden i adjacency-listen.
Nå skal vi bruke de ovennevnte grafene som vi pleide å representere nærhetsmatrisen for å demonstrere nærhetslisten.
Ovenstående figur viser tilknytningslisten for den ikke-rettet grafen. Vi ser at hvert toppunkt eller node har sin nærhetsliste.
Når det gjelder den ikke-rettede grafen, er de totale lengdene på nærhetslister vanligvis dobbelt så mange kanter. I grafen ovenfor er det totale antallet kanter 6, og summen eller summen av lengden på hele tilknytningslisten er 12.
La oss nå utarbeide en nærhetsliste for den dirigerte grafen.
Som det ses av figuren ovenfor, er den totale lengden på tilgrenselistene i grafen i den rettet grafen lik antall kanter i grafen. I grafen ovenfor er det 9 kanter og summen av lengden på nærhetslister for denne grafen = 9.
La oss nå se på følgende vektede rettet graf. Legg merke til at hver kant av den vektede grafen har en vekt assosiert med seg. Så når vi representerer denne grafen med tilknytningslisten, må vi legge til et nytt felt til hver listenode som vil betegne vekten av kanten.
Tilstøtningslisten for den vektede grafen er vist nedenfor.
Ovenstående diagram viser den vektede grafen og dens nærhetsliste. Vær oppmerksom på at det er et nytt mellomrom i tilknytningslisten som angir vekten til hver node.
Grafimplementering i Java
Det følgende programmet viser implementeringen av en graf i Java. Her har vi brukt nærhetslisten til å representere 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 Produksjon:

Graph Traversal Java
For å utføre noen meningsfylt handling som å søke etter tilstedeværelsen av data, må vi krysse grafen slik at hvert toppunkt og kanten av grafen besøkes minst en gang. Dette gjøres ved hjelp av grafalgoritmer som ikke er annet enn et sett med instruksjoner som hjelper oss å krysse grafen.
Det er to algoritmer som støttes for å krysse grafen i Java .
- Dybde-første traversering
- Bredde-første traversering
Dybde-første gjennomgang
Dybde-første søk (DFS) er en teknikk som brukes til å krysse et tre eller en graf. DFS-teknikken starter med en rotnode og krysser deretter de tilstøtende nodene til rotnoden ved å gå dypere inn i grafen. I DFS-teknikken krysses nodene dybdevis til det ikke er flere barn å utforske.
Når vi når bladknutepunktet (ikke flere barneknuter), går DFS tilbake og starter med andre knutepunkter og utfører traversering på en lignende måte. DFS-teknikken bruker en stabeldatastruktur for å lagre nodene som blir krysset.
Følgende er algoritmen for DFS-teknikken.
Algoritme
Trinn 1: Start med rotnoden og sett den inn i bunken
Trinn 2: Popp elementet fra bunken og sett det inn i 'besøkt' -listen
Trinn 3: For node merket som ‘besøkt’ (eller i besøkt liste), legg til tilstøtende noder til denne noden som ennå ikke er merket som besøkt, i bunken.
Trinn 4: Gjenta trinn 2 og 3 til bunken er tom.
Illustrasjon av DFS-teknikk
Nå skal vi illustrere DFS-teknikken ved å bruke et riktig eksempel på en graf.
Nedenfor er et eksempel på en graf. Vi har stabelen for å lagre utforskede noder og en liste for å lagre besøkte noder.
hvor mye er quickbooks salgssted

Vi begynner med A til å begynne med, merker det som besøkt og legger det til den besøkte listen. Deretter vil vi vurdere alle tilstøtende noder til A og skyve disse nodene på stabelen som vist nedenfor.

Deretter popper vi en node fra stakken, dvs. B, og merker den som besøkt. Vi legger den deretter til ‘besøkt’-listen. Dette er representert nedenfor.

Nå vurderer vi de tilstøtende nodene til B som er A og C. Ut av dette er A allerede besøkt. Så vi ignorerer det. Deretter popper vi C fra bunken. Merk C som besøkt. Den tilstøtende noden til C, dvs. E, blir lagt til stabelen.

Deretter spretter vi neste node E fra bunken og merker den som besøkt. Node E's tilstøtende node er C som allerede er besøkt. Så vi ignorerer det.

Nå er bare node D igjen i bunken. Så vi markerer det som besøkt. Den tilstøtende noden er A som allerede er besøkt. Så vi legger det ikke til bunken.

På dette tidspunktet er bunken tom. Dette betyr at vi har fullført dybde-første traversal for den gitte grafen.
Den besøkte listen gir den endelige sekvensen av traversal ved hjelp av dybde-første teknikken. Den endelige DFS-sekvensen for grafen ovenfor 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 Produksjon:

Anvendelser av DFS
# 1) Oppdag en syklus i en graf: DFS gjør det lettere å oppdage en syklus i en graf når vi kan gå tilbake til en kant.
# 2) Pathfinding: Som vi allerede har sett i DFS-illustrasjonen, gitt to hovedpunkter kan vi finne stien mellom disse to toppunktene.
# 3) Minimum spenner over treet og korteste sti: Hvis vi kjører DFS-teknikken på den ikke-vektede grafen, gir den oss det minste spennende treet og den kortsluttede banen.
# 4) Topologisk sortering: Topologisk sortering brukes når vi må planlegge jobbene. Vi har avhengighet blant ulike jobber. Vi kan også bruke topologisk sortering for å løse avhengigheter blant lenker, instruksjonsplanleggere, dataserialisering, etc.
Bredde-første gjennomgang
Breadth-first (BFS) -teknikk bruker en kø for å lagre nodene i grafen. I motsetning til DFS-teknikken krysser vi i BFS grafen bredt. Dette betyr at vi krysser grafen nivåvis. Når vi utforsker alle toppunktene eller nodene på ett nivå, går vi videre til neste nivå.
Nedenfor er en algoritme for bredde-første traversal teknikk .
Algoritme
La oss se algoritmen for BFS-teknikken.
Gitt en graf G som vi trenger for å utføre BFS-teknikken.
- Trinn 1: Begynn med rotnoden og sett den inn i køen.
- Steg 2: Gjenta trinn 3 og 4 for alle noder i grafen.
- Trinn 3: Fjern rotnoden fra køen, og legg den til i listen Besøkte.
- Trinn 4: Legg nå alle tilstøtende noder til rotnoden i køen og gjenta trinn 2 til 4 for hver node.
- Trinn 6: EXIT
Illustrasjon av BFS
La oss illustrere BFS-teknikken ved hjelp av et eksempel på en graf vist nedenfor. Merk at vi har opprettholdt en liste med navnet ‘Besøkt’ og en kø. Vi bruker den samme grafen som vi brukte i DFS-eksemplet for klarhets skyld.

Først starter vi med rot, dvs. node A, og legger den til den besøkte listen. Alle tilstøtende noder til noden A, dvs. B, C og D, blir lagt til i køen.

Deretter fjerner vi noden B fra køen. Vi legger den til på listen Besøkte og merker den som besøkt. Deretter utforsker vi de tilstøtende nodene til B i køen (C er allerede i køen). En annen tilstøtende node A er allerede besøkt, så vi ignorerer den.

Deretter fjerner vi node C fra køen og merker den som besøkt. Vi legger til C i den besøkte listen, og dens tilstøtende node E blir lagt til i køen.

Deretter sletter vi D fra køen og merker den som besøkt. Node D's tilstøtende node A er allerede besøkt, så vi ignorerer den.

Så nå er bare node E i køen. Vi markerer den som besøkt og legger den til den besøkte listen. Den tilstøtende noden til E er C som allerede er besøkt. Så ignorere det.

På dette tidspunktet er køen tom, og den besøkte listen har sekvensen vi fikk som et resultat av BFS-traversering. Sekvensen er, A-> B-> C-> D-> E.
BFS Implementering
Følgende Java-program viser implementeringen av 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 Produksjon:

Anvendelser av BFS Traversal
# 1) Søppelinnsamling: En av algoritmene som brukes av søppeloppsamlingsteknikken for å kopiere søppeloppsamling er 'Cheneys algoritme'. Denne algoritmen bruker en bredeste første traversal teknikk.
# 2) Kringkasting i nettverk: Kringkasting av pakker fra et punkt til et annet i et nettverk gjøres ved hjelp av BFS-teknikken.
# 3) GPS-navigasjon: Vi kan bruke BFS-teknikken til å finne tilstøtende noder mens vi navigerer ved hjelp av GPS.
# 4) Sosiale nettverk nettsteder: BFS-teknikk brukes også på nettsteder for sosiale nettverk for å finne nettverket av mennesker som omgir en bestemt person.
# 5) Korteste sti og minimum spennende tre i uvektet graf: I den uvektede grafen kan BFS-teknikken brukes til å finne et minimumsomspennende tre og den korteste banen mellom nodene.
Java Graph Library
Java gjør det ikke obligatorisk for programmerere å alltid implementere grafene i programmet. Java tilbyr mange klare biblioteker som kan brukes direkte til å bruke grafer i programmet. Disse bibliotekene har all graf-API-funksjonalitet som kreves for å gjøre full bruk av grafen og dens forskjellige funksjoner.
Nedenfor er en kort introduksjon til noen av grafbibliotekene i Java.
# 1) Google Guava: Google Guava tilbyr et rikt bibliotek som støtter grafer og algoritmer, inkludert enkle grafer, nettverk, verdigrafer, etc.
# 2) Apache Commons: Apache Commons er et Apache-prosjekt som tilbyr komponenter i grafdata-strukturer og API-er som har algoritmer som fungerer på denne grafdatastrukturen. Disse komponentene er gjenbrukbare.
# 3) JGraphT: JGraphT er et av de mye brukte Java-grafbibliotekene. Den gir funksjonalitet for grafdatastruktur som inneholder enkel graf, rettet graf, vektet graf osv. Samt algoritmer og APIer som fungerer på grafdatastrukturen.
# 4) SourceForge JUNG: JUNG står for “Java Universal Network / Graph” og er et Java-rammeverk. JUNG gir et utvidbart språk for analyse, visualisering og modellering av dataene vi ønsker å bli representert som en graf.
JUNG tilbyr også forskjellige algoritmer og rutiner for nedbrytning, klynging, optimalisering, etc.
ofte stilte spørsmål
Q # 1) Hva er en graf i Java?
Svar: En grafdatastruktur lagrer hovedsakelig tilkoblede data, for eksempel, et nettverk av mennesker eller et nettverk av byer. En grafdatastruktur består vanligvis av noder eller punkter som kalles hjørner. Hvert toppunkt er koblet til et annet toppunkt ved hjelp av lenker som kalles kanter.
Q # 2) Hva er typene grafer?
Svar: Ulike typer grafer er listet opp nedenfor.
- Linjediagram: Et linjediagram brukes til å plotte endringene i en bestemt eiendom i forhold til tid.
- Søylediagram: Søylediagrammer sammenligner numeriske verdier for enheter som befolkningen i forskjellige byer, leseferdighetsprosenter over hele landet, etc.
Bortsett fra disse hovedtypene har vi også andre typer som piktogram, histogram, arealdiagram, spredningsdiagram, etc.
Q # 3) Hva er en koblet graf?
Svar: En tilkoblet graf er en graf der hvert toppunkt er koblet til et annet toppunkt. Derfor kan vi i den tilkoblede grafen komme til hvert toppunkt fra hvert annet toppunkt.
Q # 4) Hva er bruken av grafen?
nivå 1 helpdesk intervju spørsmål
Svar: Grafer brukes i en rekke applikasjoner. Grafen kan brukes til å representere et komplekst nettverk. Grafer brukes også i applikasjoner for sosiale nettverk for å betegne nettverket av mennesker så vel som for applikasjoner som å finne tilstøtende personer eller forbindelser.
Grafer brukes til å betegne strømmen av beregning innen informatikk.
Q # 5) Hvordan lagrer du en graf?
Svar: Det er tre måter å lagre en graf i minnet på:
#1) Vi kan lagre noder eller hjørner som objekter og kanter som pekere.
#to) Vi kan også lagre grafer som nærhetsmatrise hvis rader og kolonner er det samme som antall hjørner. Skjæringspunktet mellom hver rad og kolonne angir tilstedeværelsen eller fraværet av en kant. I den ikke-vektede grafen er tilstedeværelsen av en kant betegnet med 1 mens den i den vektede grafen erstattes av vekten av kanten.
# 3) Den siste tilnærmingen til å lagre en graf er ved å bruke en tilknytningsliste over kanter mellom grafhodene eller noder. Hver node eller toppunkt har sin nærhetsliste.
Konklusjon
I denne opplæringen har vi diskutert grafer i Java i detalj. Vi utforsket de forskjellige typene grafer, implementering av graf og traversal teknikker. Grafer kan brukes til å finne den korteste stien mellom noder.
I våre kommende veiledninger vil vi fortsette å utforske grafer ved å diskutere noen måter å finne den korteste veien.
=> Se opp den enkle Java-treningsserien her.
Anbefalt lesing
- Java Reflection Tutorial med eksempler
- Hvordan implementere Dijkstras algoritme i Java
- Java SWING Tutorial: Container, Components and Event Handling
- JAVA-opplæring for nybegynnere: 100+ praktiske Java-videoveiledninger
- TreeMap In Java - Veiledning med Java TreeMap-eksempler
- Få tilgang til modifikatorer i Java - opplæring med eksempler
- Java String with String Buffer and String Builder Tutorial
- Java String inneholder () Metodeopplæring med eksempler