java graph tutorial how implement graph data structure
Deze uitgebreide zelfstudie over Java Graph geeft een gedetailleerde uitleg van de gegevensstructuur van grafieken. Het omvat het maken, implementeren, weergeven en doorlopen van grafieken in Java:
Een grafische datastructuur vertegenwoordigt voornamelijk een netwerk dat verschillende punten met elkaar verbindt. Deze punten worden genoemd als hoekpunten en de schakels die deze punten verbinden worden ‘Edges’ genoemd. Dus een grafiek g wordt gedefinieerd als een set hoekpunten V en randen E die deze hoekpunten verbinden.
Grafieken worden meestal gebruikt om verschillende netwerken weer te geven, zoals computernetwerken, sociale netwerken, enz. Ze kunnen ook worden gebruikt om verschillende afhankelijkheden in software of architecturen weer te geven. Deze afhankelijkheidsgrafieken zijn erg handig bij het analyseren van de software en soms ook bij het debuggen ervan.
Bekijk hier ALLE Java-tutorials.
Wat je leert:
- Java Graph-gegevensstructuur
- Hoe maak je een grafiek?
- Grafiekimplementatie in Java
- Java Graph-bibliotheek
- Gevolgtrekking
Java Graph-gegevensstructuur
Hieronder is een grafiek weergegeven met vijf hoekpunten {A, B, C, D, E} en randen gegeven door {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Omdat de randen geen richtingen aangeven, staat deze grafiek bekend als ‘ongerichte grafiek’.
Afgezien van de hierboven getoonde ongerichte grafiek, zijn er verschillende varianten van de grafiek in Java.
Laten we deze varianten in detail bespreken.
Verschillende varianten van de grafiek
De volgende zijn enkele van de varianten van de grafiek.
# 1) Gerichte grafiek
Een gerichte graaf of digraph is een datastructuur van een grafiek waarin de randen een specifieke richting hebben. Ze zijn afkomstig van het ene hoekpunt en culmineren in een ander hoekpunt.
Het volgende diagram toont het voorbeeld van een gerichte graaf.
In het bovenstaande diagram is er een rand van hoekpunt A naar hoekpunt B. Maar merk op dat A naar B niet hetzelfde is als B naar A, zoals in een ongerichte grafiek, tenzij er een rand is gespecificeerd van B naar A.
Een gerichte graaf is cyclisch als er ten minste één pad is waarvan het eerste en laatste hoekpunt hetzelfde is. In het bovenstaande diagram vormt een pad A-> B-> C-> D-> E-> A een gerichte cyclus of cyclische grafiek.
Omgekeerd is een gerichte acyclische grafiek een grafiek waarin er geen gerichte cyclus is, d.w.z. er is geen pad dat een cyclus vormt.
# 2) Gewogen grafiek
In een gewogen grafiek, een gewichthoort bij elke rand van de grafiek. Het gewicht geeft normaal gesproken de afstand tussen de twee hoekpunten aan. Het volgende diagram toont de gewogen grafiek. Aangezien er geen richtingen worden weergegeven, is dit de ongerichte grafiek.
Merk op dat een gewogen grafiek kan worden gericht of ongericht.
Hoe maak je een grafiek?
Java biedt geen volwaardige implementatie van de grafische datastructuur. We kunnen de grafiek echter programmatisch weergeven met Collecties in Java. We kunnen ook een grafiek implementeren met behulp van dynamische arrays zoals vectoren.
Meestal implementeren we grafieken in Java met behulp van de HashMap-verzameling. HashMap-elementen hebben de vorm van sleutel-waardeparen. We kunnen de lijst met aangrenzende grafieken weergeven in een HashMap.
Een meest gebruikelijke manier om een grafiek te maken, is door een van de weergaven van grafieken te gebruiken, zoals een aangrenzende matrix of een aangrenzende lijst. We zullen deze representaties vervolgens bespreken en vervolgens de grafiek in Java implementeren met behulp van de aangrenzende lijst waarvoor we ArrayList zullen gebruiken.
Grafische weergave in Java
Grafische weergave betekent de benadering of techniek waarmee grafiekgegevens in het computergeheugen worden opgeslagen.
We hebben twee hoofdweergaven van grafieken, zoals hieronder weergegeven.
Nabijheid Matrix
Adjacency Matrix is een lineaire weergave van grafieken. Deze matrix slaat de mapping van hoekpunten en randen van de grafiek op. In de aangrenzende matrix vertegenwoordigen hoekpunten van de grafiek rijen en kolommen. Dit betekent dat als de grafiek N hoekpunten heeft, de aangrenzende matrix de afmeting NxN zal hebben.
Als V een set hoekpunten van de grafiek is, dan is snijpunt Mijin de aangrenzende lijst = 1 betekent dat er een rand bestaat tussen de hoekpunten i en j.
Laten we, om dit concept beter te begrijpen, een aangrenzende matrix voorbereiden voor een ongerichte grafiek.
Zoals te zien is in het bovenstaande diagram, zien we dat voor hoekpunt A de snijpunten AB en AE zijn ingesteld op 1 omdat er een rand is van A naar B en A naar E. Evenzo wordt snijpunt BA ingesteld op 1, omdat dit een ongericht is. grafiek en AB = BA. Evenzo hebben we alle andere snijpunten waarvoor er een rand is, op 1 gezet.
Als de grafiek is gericht, is het snijpunt Mijwordt alleen op 1 gezet als er een duidelijke rand is gericht van Vi naar Vj.
Dit wordt getoond in de volgende afbeelding.
Zoals we in het bovenstaande diagram kunnen zien, is er een rand van A naar B. Dus snijpunt AB is ingesteld op 1, maar snijpunt BA is ingesteld op 0. Dit komt omdat er geen rand is gericht van B naar A.
Beschouw hoekpunten E en D. We zien dat er randen zijn van E naar D en ook van D naar E. Daarom hebben we beide snijpunten in de aangrenzende matrix op 1 gezet.
Nu gaan we verder met gewogen grafieken. Zoals we weten voor de gewogen grafiek, wordt aan elke rand een geheel getal, ook wel gewicht genoemd, geassocieerd. We vertegenwoordigen dit gewicht in de aangrenzende matrix voor de rand die bestaat. Dit gewicht wordt gespecificeerd wanneer er een rand is van het ene hoekpunt naar het andere in plaats van ‘1’.
Deze weergave wordt hieronder weergegeven.
Nabijheidslijst
In plaats van een grafiek weer te geven als een aangrenzende matrix die sequentieel van aard is, kunnen we ook gekoppelde representatie gebruiken. Deze gekoppelde weergave staat bekend als de aangrenzende lijst. Een aangrenzende lijst is niets anders dan een gekoppelde lijst en elk knooppunt in de lijst vertegenwoordigt een hoekpunt.
De aanwezigheid van een rand tussen twee hoekpunten wordt aangegeven door een wijzer van het eerste hoekpunt naar het tweede. Deze aangrenzende lijst wordt bijgehouden voor elk hoekpunt in de grafiek.
Wanneer we alle aangrenzende knooppunten voor een bepaald knooppunt hebben doorlopen, slaan we NULL op in het volgende aanwijzerveld van het laatste knooppunt van de aangrenzende lijst.
Nu zullen we de bovenstaande grafieken gebruiken die we hebben gebruikt om de aangrenzende matrix weer te geven om de aangrenzende lijst te demonstreren.
De bovenstaande afbeelding toont de aangrenzende lijst voor de ongerichte grafiek. We zien dat elk hoekpunt of knooppunt zijn aangrenzende lijst heeft.
In het geval van de ongerichte graaf zijn de totale lengtes van aangrenzende lijsten meestal tweemaal het aantal randen. In de bovenstaande grafiek is het totale aantal randen 6 en het totaal of de som van de lengte van alle aangrenzende lijsten is 12.
Laten we nu een aangrenzende lijst maken voor de gerichte grafiek.
Zoals blijkt uit de bovenstaande figuur, is in de gerichte grafiek de totale lengte van de aangrenzende lijsten van de grafiek gelijk aan het aantal randen in de grafiek. In de bovenstaande grafiek zijn er 9 randen en de som van de lengtes van aangrenzende lijsten voor deze grafiek = 9.
Laten we nu eens kijken naar de volgende gewogen gerichte grafiek. Merk op dat aan elke rand van de gewogen grafiek een gewicht is gekoppeld. Dus wanneer we deze grafiek weergeven met de aangrenzende lijst, moeten we een nieuw veld toevoegen aan elk lijstknooppunt dat het gewicht van de rand aangeeft.
De aangrenzende lijst voor de gewogen grafiek wordt hieronder weergegeven.
Het bovenstaande diagram toont de gewogen grafiek en de aangrenzende lijst. Merk op dat er een nieuwe spatie in de aangrenzende lijst is die het gewicht van elk knooppunt aangeeft.
Grafiekimplementatie in Java
Het volgende programma toont de implementatie van een grafiek in Java. Hier hebben we de aangrenzende lijst gebruikt om de grafiek weer te geven.
Uitgang:
Graph Traversal Java
Om een zinvolle actie uit te voeren, zoals het zoeken naar de aanwezigheid van gegevens, moeten we de grafiek zo doorlopen dat elk hoekpunt en de rand van de grafiek minstens één keer wordt bezocht. Dit wordt gedaan met behulp van grafiekalgoritmen die niets anders zijn dan een reeks instructies die ons helpen de grafiek te doorlopen.
Er worden twee algoritmen ondersteund om de grafiek in Java te doorlopen
- Diepte-eerste traversal
- Breedte-eerste traversal
Diepte-eerste traversal
Diepte-eerst zoeken (DFS) is een techniek die wordt gebruikt om door een boom of een grafiek te lopen. De DFS-techniek begint met een hoofdknooppunt en doorloopt vervolgens de aangrenzende knooppunten van het hoofdknooppunt door dieper in de grafiek te gaan. In de DFS-techniek worden de knooppunten in de diepte doorlopen totdat er geen kinderen meer zijn om te verkennen.
Zodra we het bladknooppunt bereiken (geen onderliggende knooppunten meer), loopt de DFS terug en begint met andere knooppunten en voert het doorlopen op een vergelijkbare manier uit. De DFS-techniek maakt gebruik van een stapelgegevensstructuur om de knooppunten op te slaan die worden doorlopen.
Hieronder volgt het algoritme voor de DFS-techniek.
Algoritme
Stap 1: Begin met het hoofdknooppunt en plaats het in de stapel
Stap 2: Haal het item uit de stapel en plaats het in de ‘bezochte’ lijst
Stap 3: Voeg voor het knooppunt dat is gemarkeerd als ‘bezocht’ (of in de lijst met bezochte adressen) de aangrenzende knooppunten van dit knooppunt die nog niet zijn gemarkeerd als bezocht, toe aan de stapel.
Stap 4: Herhaal stap 2 en 3 totdat de stapel leeg is.
Illustratie Van DFS-Techniek
Nu zullen we de DFS-techniek illustreren aan de hand van een goed voorbeeld van een grafiek.
Hieronder is een voorbeeldgrafiek weergegeven. We onderhouden een stapel om onderzochte knooppunten op te slaan en een lijst om bezochte knooppunten op te slaan.
We beginnen om te beginnen met A, markeren het als bezocht en voegen het toe aan de bezochte lijst. Vervolgens zullen we alle aangrenzende knooppunten van A bekijken en deze knooppunten op de stapel duwen zoals hieronder weergegeven.
Vervolgens halen we een knooppunt uit de stapel, d.w.z. B, en markeren het als bezocht. We voegen het vervolgens toe aan de ‘bezochte’ lijst. Dit wordt hieronder weergegeven.
Nu kijken we naar de aangrenzende knooppunten van B die A en C zijn. Hiervan is A al bezocht. Dus we negeren het. Vervolgens halen we C van de stapel. Markeer C zoals bezocht. Het aangrenzende knooppunt van C, d.w.z. E, wordt aan de stapel toegevoegd.
Vervolgens halen we het volgende knooppunt E uit de stapel en markeren het als bezocht. Het aangrenzende knooppunt van knooppunt E is C dat al is bezocht. Dus we negeren het.
Nu blijft alleen knooppunt D in de stapel. Dus we markeren het als bezocht. Het aangrenzende knooppunt is A dat al is bezocht. We voegen het dus niet toe aan de stapel.
vr headset voor xbox one x
Op dit punt is de stapel leeg. Dit betekent dat we de diepte-eerst-verplaatsing voor de gegeven grafiek hebben voltooid.
De bezochte lijst geeft de laatste reeks verplaatsingen weer met behulp van de diepte eerst techniek. De laatste DFS-reeks voor de bovenstaande grafiek is A-> B-> C-> E-> D.
DFS-implementatie
Uitgang:
Toepassingen van DFS
# 1) Detecteer een cyclus in een grafiek: DFS vergemakkelijkt het detecteren van een cyclus in een grafiek wanneer we naar een rand kunnen terugkeren.
# 2) Pathfinding: Zoals we al hebben gezien in de DFS-illustratie, kunnen we bij elke twee hoekpunten het pad tussen deze twee hoekpunten vinden.
# 3) Minimum spanning tree en kortste pad: Als we de DFS-techniek op de niet-gewogen grafiek uitvoeren, geeft dit ons de minimale spanning tree en het verkorte pad.
# 4) Topologische sortering: Topologische sortering wordt gebruikt wanneer we de taken moeten plannen. We hebben afhankelijkheden tussen verschillende banen. We kunnen ook topologische sortering gebruiken voor het oplossen van afhankelijkheden tussen linkers, instructieplanners, dataserialisatie, enz.
Breedte-eerste traversal
Breadth-first (BFS) techniek maakt gebruik van een wachtrij om de knooppunten van de grafiek op te slaan. In tegenstelling tot de DFS-techniek, doorlopen we in BFS de grafiek in de breedte. Dit betekent dat we de grafiek niveaugewijs doorlopen. Als we alle hoekpunten of knooppunten op het ene niveau verkennen, gaan we naar het volgende niveau.
Hieronder wordt een algoritme gegeven voor de breedte-eerste doorgangstechniek
Algoritme
Laten we eens kijken naar het algoritme voor de BFS-techniek.
Gegeven een grafiek G waarvoor we de BFS-techniek moeten uitvoeren.
- Stap 1: Begin met het rootknooppunt en plaats het in de wachtrij.
- Stap 2: Herhaal stap 3 en 4 voor alle knooppunten in de grafiek.
- Stap 3: Verwijder het hoofdknooppunt uit de wachtrij en voeg het toe aan de lijst Bezocht.
- Stap 4: Voeg nu alle aangrenzende knooppunten van het hoofdknooppunt toe aan de wachtrij en herhaal stap 2 tot en met 4 voor elk knooppunt. (EINDE VAN LUS)
- Stap 6: UITGANG
Illustratie van BFS
Laten we de BFS-techniek illustreren met behulp van een voorbeeldgrafiek die hieronder wordt weergegeven. Merk op dat we een lijst met de naam ‘Bezocht’ en een wachtrij hebben bijgehouden. Voor de duidelijkheid gebruiken we dezelfde grafiek die we in het DFS-voorbeeld hebben gebruikt.
Eerst beginnen we met root, d.w.z. knooppunt A, en voegen deze toe aan de bezochte lijst. Alle aangrenzende knooppunten van knooppunt A, d.w.z. B, C en D, worden aan de wachtrij toegevoegd.
Vervolgens verwijderen we knooppunt B uit de wachtrij. We voegen het toe aan de bezochte lijst en markeren het als bezocht. Vervolgens verkennen we de aangrenzende knooppunten van B in de wachtrij (C staat al in de wachtrij). Een ander aangrenzend knooppunt A is al bezocht, dus we negeren het.
Vervolgens verwijderen we knooppunt C uit de wachtrij en markeren het als bezocht. We voegen C toe aan de bezochte lijst en het aangrenzende knooppunt E wordt aan de wachtrij toegevoegd.
Vervolgens verwijderen we D uit de wachtrij en markeren deze als bezocht. Het aangrenzende knooppunt A van knooppunt D is al bezocht, dus we negeren het.
Dus nu staat alleen knooppunt E in de wachtrij. We markeren het als bezocht en voegen het toe aan de bezochte lijst. Het aangrenzende knooppunt van E is C dat al is bezocht. Negeer het dus.
Op dit punt is de wachtrij leeg en heeft de bezochte lijst de volgorde die we hebben verkregen als resultaat van BFS-traversal. De volgorde is, A-> B-> C-> D-> E.
BFS-implementatie
Het volgende Java-programma toont de implementatie van de BFS-techniek.
Uitgang:
Toepassingen van BFS Traversal
# 1) Afvalinzameling: Een van de algoritmen die door de garbage collection-techniek wordt gebruikt om Garbage collection te kopiëren, is 'Cheney's algoritme'. Dit algoritme maakt gebruik van een breedte-eerste traversale techniek.
# 2) Uitzenden in netwerken: Het uitzenden van pakketten van het ene punt naar het andere in een netwerk gebeurt met behulp van de BFS-techniek.
# 3) GPS-navigatie: We kunnen de BFS-techniek gebruiken om aangrenzende knooppunten te vinden tijdens het navigeren met GPS.
# 4) Sociale netwerkwebsites: BFS-techniek wordt ook gebruikt in sociale netwerkwebsites om het netwerk van mensen rondom een bepaalde persoon te vinden.
# 5) Kortste pad en minimale spanning tree in niet-gewogen grafiek: In de ongewogen grafiek kan de BFS-techniek worden gebruikt om een minimale spanning tree en het kortste pad tussen de knooppunten te vinden.
Java Graph-bibliotheek
Java verplicht programmeurs niet om de grafieken altijd in het programma te implementeren. Java biedt veel kant-en-klare bibliotheken die direct kunnen worden gebruikt om grafieken in het programma te gebruiken. Deze bibliotheken hebben alle grafische API-functionaliteit die nodig is om volledig gebruik te maken van de grafiek en zijn verschillende functies.
Hieronder vindt u een korte inleiding tot enkele van de grafische bibliotheken in Java.
# 1) Google Guava: Google Guava biedt een rijke bibliotheek die grafieken en algoritmen ondersteunt, waaronder eenvoudige grafieken, netwerken, waardegrafieken, enz.
# 2) Apache Commons: Apache Commons is een Apache-project dat Graph-datastructuurcomponenten en API's biedt die algoritmen hebben die op deze grafiekdatastructuur werken. Deze componenten zijn herbruikbaar.
# 3) JGraphT: JGraphT is een van de meest gebruikte Java-grafiekbibliotheken. Het biedt grafische datastructuurfunctionaliteit met een eenvoudige grafiek, gerichte grafiek, gewogen grafiek, enz., Evenals algoritmen en API's die werken op de datastructuur van de grafiek.
# 4) BronForge JUNG: JUNG staat voor 'Java Universal Network / Graph' en is een Java-framework. JUNG biedt een uitbreidbare taal voor analyse, visualisatie en modellering van de gegevens die we als een grafiek willen weergeven.
JUNG biedt ook verschillende algoritmen en routines voor decompositie, clustering, optimalisatie, enz.
Veel Gestelde Vragen
V # 1) Wat is een grafiek in Java?
Antwoord: Een grafische datastructuur slaat voornamelijk verbonden data op, bijvoorbeeld, een netwerk van mensen of een netwerk van steden. Een datastructuur van een grafiek bestaat doorgaans uit knooppunten of punten die hoekpunten worden genoemd. Elk hoekpunt is verbonden met een ander hoekpunt met behulp van links die randen worden genoemd.
Q # 2) Wat zijn de soorten grafieken?
Antwoord: Hieronder worden verschillende soorten grafieken weergegeven.
- Lijn grafiek: Een lijngrafiek wordt gebruikt om de veranderingen in een bepaalde eigenschap uit te zetten in verhouding tot de tijd.
- Staafdiagram: Staafdiagrammen vergelijken numerieke waarden van entiteiten zoals de bevolking in verschillende steden, alfabetiseringspercentages in het hele land, enz.
Naast deze hoofdtypen hebben we ook andere typen, zoals pictogram, histogram, vlakgrafiek, spreidingsdiagram, enz.
V # 3) Wat is een verbonden grafiek?
Antwoord: Een verbonden graaf is een grafiek waarin elk hoekpunt is verbonden met een ander hoekpunt. Daarom kunnen we in de verbonden grafiek elk hoekpunt vanaf elk ander hoekpunt bereiken.
Q # 4) Wat zijn de toepassingen van de grafiek?
Antwoord: Grafieken worden in verschillende toepassingen gebruikt. De grafiek kan worden gebruikt om een complex netwerk weer te geven. Grafieken worden ook gebruikt in sociale netwerktoepassingen om het netwerk van mensen aan te duiden, maar ook voor toepassingen zoals het vinden van aangrenzende mensen of verbindingen.
Grafieken worden gebruikt om de stroom van berekeningen in de informatica aan te duiden.
Q # 5) Hoe sla je een grafiek op?
Antwoord: Er zijn drie manieren om een grafiek in het geheugen op te slaan:
# 1) We kunnen knooppunten of hoekpunten opslaan als objecten en randen als aanwijzers.
#twee) We kunnen ook grafieken opslaan als aangrenzende matrix waarvan de rijen en kolommen hetzelfde zijn als het aantal hoekpunten. Het snijpunt van elke rij en kolom geeft de aan- of afwezigheid van een rand aan. In de niet-gewogen grafiek wordt de aanwezigheid van een rand aangeduid met 1, terwijl deze in de gewogen grafiek wordt vervangen door het gewicht van de rand.
# 3) De laatste manier om een grafiek op te slaan, is door een aangrenzende lijst van randen tussen grafpunten of knooppunten te gebruiken. Elk knooppunt of hoekpunt heeft zijn aangrenzende lijst.
Gevolgtrekking
In deze tutorial hebben we grafieken in Java in detail besproken. We hebben de verschillende soorten grafieken, grafiekimplementatie en doorgangstechnieken onderzocht. Grafieken kunnen worden gebruikt om het kortste pad tussen knooppunten te vinden.
In onze komende tutorials zullen we grafieken blijven onderzoeken door een paar manieren te bespreken om het kortste pad te vinden.
Bekijk hier de eenvoudige Java-trainingsserie.
Aanbevolen literatuur
- Zelfstudie over reflectie in Java met voorbeelden
- Hoe Dijkstra's algoritme in Java te implementeren
- Java SWING-zelfstudie: afhandeling van containers, componenten en gebeurtenissen
- JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials
- TreeMap in Java - Tutorial met Java TreeMap-voorbeelden
- Toegang tot modificatoren in Java - zelfstudie met voorbeelden
- Java String met String Buffer en String Builder Tutorial
- Java String bevat () Method Tutorial met voorbeelden