java graph tutorial how implement graph data structure
Ta izčrpna vadnica za grafe Java podrobno razlaga strukturo grafičnih podatkov. Vključuje, kako ustvariti, implementirati, predstaviti in prečkati grafe v Javi:
Graf podatkovne strukture v glavnem predstavlja omrežje, ki povezuje različne točke. Te točke se imenujejo oglišča, povezave, ki jih povezujejo, pa se imenujejo 'robovi'. Torej je graf g definiran kot množica točk V in robov E, ki povezujejo te točke.
Grafi se večinoma uporabljajo za predstavitev različnih omrežij, kot so računalniška omrežja, socialna omrežja itd. Lahko se uporabljajo tudi za predstavitev različnih odvisnosti v programski opremi ali arhitekturah. Ti grafi odvisnosti so zelo uporabni pri analizi programske opreme in včasih tudi pri odpravljanju napak.
=> Tukaj preverite VSE Vadnice za Java.
Kaj se boste naučili:
- Struktura podatkov Java Graph
- Kako ustvariti graf?
- Izvajanje grafa v Javi
- Knjižnica Java Graph
- Zaključek
Struktura podatkov Java Graph
Spodaj je graf s petimi točkami {A, B, C, D, E} in robovi, ki jih podajajo {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Ker robovi ne kažejo nobenih smeri, je ta graf znan kot „neusmerjen graf“.
Poleg zgoraj prikazanega neusmerjenega grafa obstaja v Javi več različic grafa.
Podrobno se pogovorimo o teh variantah.
Različne različice grafa
Sledi nekaj različic grafa.
# 1) Usmerjeni graf
Usmerjeni graf ali digraf je struktura podatkov grafa, pri kateri imajo robovi določeno smer. Izvirajo iz ene točke in dosežejo vrhunec v drugo točko.
Naslednji diagram prikazuje primer usmerjenega grafa.
V zgornjem diagramu je rob od točke A do točke B. Vendar upoštevajte, da A do B ni enako kot B do A, kot v neusmerjenem grafu, razen če obstaja rob, določen od B do A.
Usmerjeni graf je cikličen, če obstaja vsaj ena pot, ki ima svojo prvo in zadnjo točko enako. V zgornjem diagramu pot A-> B-> C-> D-> E-> A tvori usmerjeni cikel ali ciklični graf.
Nasprotno pa je usmerjeni aciklični graf graf, v katerem ni usmerjenega cikla, torej ni poti, ki tvori cikel.
katera je najboljša programska oprema za upravljanje nalog
# 2) Uteženi graf
V uteženem grafu utežje povezan z vsakim robom grafa. Utež običajno označuje razdaljo med obema točkama. Naslednji diagram prikazuje tehtani graf. Ker nobene smeri niso prikazane, je to neusmerjen graf.
Upoštevajte, da je utežen graf lahko usmerjen ali neusmerjen.
Kako ustvariti graf?
Java ne zagotavlja polnopravne izvedbe podatkovne strukture grafa. Vendar lahko grafično predstavimo graf z uporabo zbirk v Javi. Graf lahko izvedemo tudi z uporabo dinamičnih nizov, kot so vektorji.
Grafe navadno izvajamo v Javi z uporabo zbirke HashMap. Elementi HashMap so v obliki parov ključ-vrednost. Seznam sosednosti grafov lahko predstavimo v HashMap-u.
Najpogostejši način za ustvarjanje grafa je uporaba ene od predstavitev grafov, kot je matrica sosednosti ali seznam sosednosti. O teh predstavitvah bomo razpravljali v nadaljevanju in nato graf implementirali v Javo s pomočjo seznama sosednosti, za katerega bomo uporabili ArrayList.
Predstavitev grafa v Javi
Predstavitev grafa pomeni pristop ali tehniko, pri kateri se podatki grafa shranijo v pomnilnik računalnika.
Imamo dva glavna prikaza grafov, kot je prikazano spodaj.
Matrika sosednosti
Matrica sosedstva je linearna predstavitev grafov. Ta matrika shranjuje preslikavo točk in robov grafa. V matrici sosedstva oglišča grafa predstavljajo vrstice in stolpce. To pomeni, da če bo graf imel N oglišč, bo imela matrika sosednosti velikost NxN.
Če je V niz oglišč grafa, je presečišče Mijna seznamu sosednosti = 1 pomeni, da obstaja rob med točkama i in j.
Da bomo ta koncept bolje razumeli, pripravimo matriko sosedstva za neusmerjeni graf.
Kot je razvidno iz zgornjega diagrama, vidimo, da sta za točki A presečišči AB in AE nastavljeni na 1, saj obstaja rob od A do B in A do E. Podobno je presečišče BA nastavljeno na 1, saj je to neusmerjeno graf in AB = BA. Podobno smo vsa ostala križišča, za katera obstaja rob, nastavili na 1.
Če je graf usmerjen, presečišče Mijbo nastavljena na 1 samo, če je prosti rob usmerjen od Vi do Vj.
To je prikazano na naslednji sliki.
Kot lahko vidimo iz zgornjega diagrama, obstaja rob od A do B. Torej je presečišče AB nastavljeno na 1, presečišče BA pa na 0. To je zato, ker ni roba, usmerjenega od B do A.
Upoštevajmo oglišči E in D. Vidimo, da obstajajo robovi od E do D, pa tudi od D do E. Zato smo nastavili obe presečišči na 1 v Matriki sosednosti.
Zdaj preidemo na tehtane grafe. Kot vemo za tehtani graf, je celo število, znano tudi kot teža, povezano z vsakim robom. To utež predstavljamo v matriki sosednosti za rob, ki obstaja. Ta utež je določena, kadar je rob iz ene točke v drugo namesto '1'.
Ta predstavitev je prikazana spodaj.
Seznam sosednosti
Namesto da grafi predstavljamo matriko sosednosti, ki je zaporedne narave, lahko uporabimo tudi povezano predstavitev. Ta povezana predstavitev je znana kot seznam sosednosti. Seznam sosednosti ni nič drugega kot povezan seznam in vsako vozlišče na seznamu predstavlja oglišče.
Prisotnost roba med dvema ogliščema je označena s kazalcem iz prvega v drugo točko. Ta seznam sosednosti se vzdržuje za vsako točko na grafu.
Ko prehodimo vsa sosednja vozlišča za določeno vozlišče, shranimo NULL v naslednje polje kazalca zadnjega vozlišča seznama sosednosti.
Zdaj bomo za prikaz seznama sosednosti uporabili zgornje grafe, ki smo jih uporabili za predstavitev matrice sosednosti.
Zgornja slika prikazuje seznam sosednosti za neusmerjeni graf. Vidimo, da ima vsako oglišče ali vozlišče svoj seznam sosednosti.
V primeru neusmerjenega grafa so skupne dolžine seznamov sosednosti običajno dvakrat večje od števila robov. V zgornjem grafu je skupno število robov 6, skupno ali vsota dolžine celotnega seznama sosednosti pa 12.
Zdaj pa pripravimo seznam sosednosti za usmerjeni graf.
Kot je razvidno iz zgornje slike, je v usmerjenem grafu skupna dolžina seznamov sosednosti grafa enaka številu robov v grafu. V zgornjem grafu je za ta graf 9 robov in vsota dolžin seznamov sosednosti = 9.
Zdaj pa si oglejmo naslednji tehtani usmerjeni graf. Upoštevajte, da je z vsakim robom tehtanega grafa povezana utež. Ko predstavljamo ta graf s seznamom sosednosti, moramo vsakemu vozlišču seznama dodati novo polje, ki bo označevalo težo roba.
Seznam sosednosti tehtanega grafa je prikazan spodaj.
Zgornji diagram prikazuje tehtani graf in njegov seznam sosednosti. Upoštevajte, da je na seznamu sosednosti nov prostor, ki označuje težo vsakega vozlišča.
Izvajanje grafa v Javi
Naslednji program prikazuje izvajanje grafa v Javi. Tu smo za prikaz grafa uporabili seznam sosednosti.
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 Izhod:
Graf Prehod Java
Za izvedbo kakršnega koli smiselnega dejanja, kot je iskanje prisotnosti kakršnih koli podatkov, moramo graf prehoditi tako, da je vsaka točka in rob grafa obiskana vsaj enkrat. To se naredi z uporabo algoritmov grafov, ki niso nič drugega kot nabor navodil, ki nam pomagajo prečkati graf.
Za prehod grafa v Javi sta podprta dva algoritma .
- Globinsko prvo prečkanje
- Prehod širine prvi
Prehod globine prvi
Iskanje po globini (DFS) je tehnika, ki se uporablja za prehod drevesa ali grafa. Tehnika DFS se začne s korenskim vozliščem, nato pa prečka sosednja vozlišča korenskega vozlišča tako, da gre globlje v graf. V tehniki DFS vozlišča prehodimo globinsko, dokler ni več otrok za raziskovanje.
Ko pridemo do listnega vozlišča (ni več podrejenih vozlišč), se DFS vrne nazaj in začne z drugimi vozlišči ter na podoben način izvede prečkanje. Tehnika DFS uporablja podatkovno strukturo skladov za shranjevanje vozlišč, ki jih prečkate.
Sledi algoritem za tehniko DFS.
Algoritem
1. korak: Začnite s korenskim vozliščem in ga vstavite v sklad
2. korak: Izvlecite element iz sklada in ga vstavite na seznam »obiskanih«
3. korak: Za vozlišče, označeno kot »obiskano« (ali na seznamu obiskanih), dodajte v sosednja vozlišča tega vozlišča, ki še niso označena kot obiskana.
4. korak: Ponavljajte koraka 2 in 3, dokler se sklad ne izprazni.
Ilustracija DFS tehnike
Zdaj bomo ponazorili tehniko DFS z ustreznim primerom grafa.
Spodaj je primer grafa. Vzdržujemo sklad za shranjevanje raziskanih vozlišč in seznam za shranjevanje obiskanih vozlišč.
Za začetek bomo začeli z A, jo označili kot obiskano in jo dodali na seznam obiskanih. Nato bomo upoštevali vsa sosednja vozlišča A in jih potisnili na sklad, kot je prikazano spodaj.
Nato iz sklopa izvlečemo vozlišče, tj. B, in ga označimo kot obiskano. Nato ga dodamo na seznam 'obiskanih'. To je predstavljeno spodaj.
Zdaj upoštevamo sosednja vozlišča B, ki sta A in C. Od tega je A že obiskan. Torej ga ignoriramo. Nato iztaknemo C iz sklada. Oznaka C kot obiskana. Sosednje vozlišče C, tj.E, se doda v sklad.
Nato iz sklopa izvlečemo naslednje vozlišče E in ga označimo kot obiskano. Sosednje vozlišče vozlišča E je že obiskano C. Torej ga ignoriramo.
Zdaj v skladu ostane samo vozlišče D. Torej jo označimo kot obiskano. Njeno sosednje vozlišče je A, ki je že obiskano. Torej ga ne dodamo v sklad.
V tem trenutku je kup prazen. To pomeni, da smo za dani graf zaključili prehod s prvo globino.
Obiskani seznam podaja končno zaporedje prečkanja s tehniko globine prve. Končno zaporedje DFS za zgornji graf je A-> B-> C-> E-> D.
Izvajanje DFS
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 Izhod:
Aplikacije DFS
# 1) Zaznajte cikel v grafu: DFS olajša zaznavanje cikla v grafu, ko se lahko vrnemo nazaj na rob.
# 2) Iskanje poti: Kot smo že videli na ilustraciji DFS, lahko glede na kateri koli dve točki najdemo pot med tema dvema točkama.
# 3) Najmanj zajeto drevo in najkrajša pot: Če zaženemo tehniko DFS na neutemeljenem grafu, dobimo najmanjše raztezajoče drevo in kratko pot.
# 4) Topološko razvrščanje: Topološko razvrščanje se uporablja, kadar moramo razporejati opravila. Med različnimi delovnimi mesti imamo odvisnosti. Topološko razvrščanje lahko uporabimo tudi za reševanje odvisnosti med povezovalci, načrtovalniki ukazov, serializacijo podatkov itd.
Prehod po širini
Tehnika širine najprej (BFS) uporablja čakalno vrsto za shranjevanje vozlišč grafa. V nasprotju s tehniko DFS v BFS prehodimo graf v širino. To pomeni, da pametno prehodimo raven grafa. Ko raziščemo vse točke in vozlišča na eni ravni, nadaljujemo na naslednjo stopnjo.
Spodaj je naveden algoritem za prvo tehniko prečkanja v širino .
Algoritem
Poglejmo algoritem za tehniko BFS.
Glede na graf G, za katerega moramo izvesti tehniko BFS.
- Korak 1: Začnite s korenskim vozliščem in ga vstavite v čakalno vrsto.
- 2. korak: Ponovite koraka 3 in 4 za vsa vozlišča na grafu.
- 3. korak: Odstranite korensko vozlišče iz čakalne vrste in ga dodajte na seznam obiskanih.
- 4. korak: Zdaj v čakalno vrsto dodajte vsa sosednja vozlišča korenskega vozlišča in ponovite korake od 2 do 4. za vsako vozlišče. [END OF LOOP]
- 6. korak: IZHOD
Ilustracija BFS
Naj ponazorimo tehniko BFS z uporabo spodnjega grafa. Upoštevajte, da imamo seznam z imenom »Obiskan« in čakalno vrsto. Za jasnost uporabimo isti graf, kot smo ga uporabili v primeru DFS.
Najprej začnemo s korenom, tj. Vozliščem A, in ga dodamo na obiskani seznam. Vsa sosednja vozlišča vozlišča A, tj. B, C in D, se dodajo v vrsto.
Nato vozlišče B odstranimo iz čakalne vrste. Dodamo ga na seznam Obiskanih in označimo kot obiskan. Nato raziščemo sosednja vozlišča B v čakalni vrsti (C je že v čakalni vrsti). Drugo sosednje vozlišče A je že obiskano, zato ga prezremo.
Nato vozlišče C odstranimo iz čakalne vrste in ga označimo kot obiskano. Na obiskani seznam dodamo C, sosednje vozlišče E pa v čakalno vrsto.
Nato črtamo D iz čakalne vrste in ga označimo kot obiskano. Sosednje vozlišče A vozlišča D je že obiskano, zato ga prezremo.
Zdaj je v čakalni vrsti samo vozlišče E. Označimo jo kot obiskano in jo dodamo na seznam obiskanih. Sosednje vozlišče E je C, ki je že obiskano. Torej ignorirajte.
V tem trenutku je vrsta prazna in obiskani seznam ima zaporedje, ki smo ga dobili kot prehod BFS. Zaporedje je A-> B-> C-> D-> E.
Izvajanje BFS
Naslednji program Java prikazuje izvajanje tehnike BFS.
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 Izhod:
programska oprema za prenos video posnetkov
Aplikacije BFS Traversal
# 1) Odvoz smeti: Eden od algoritmov, ki ga tehnika kopičenja smeti uporablja za kopiranje zbiranja smeti, je 'Cheneyev algoritem'. Ta algoritem uporablja tehniko prehoda najprej v širino.
# 2) Oddajanje v omrežjih: Oddajanje paketov z ene točke na drugo v omrežju poteka z uporabo tehnike BFS.
# 3) GPS navigacija: S tehniko BFS lahko med navigacijo s pomočjo GPS poiščemo sosednja vozlišča.
# 4) Spletna mesta za družabna omrežja: Tehnika BFS se uporablja tudi na spletnih mestih za družabno mreženje, da bi našli mrežo ljudi, ki obkrožajo določeno osebo.
# 5) Najkrajša pot in najmanjše drevo v neutemeljenem grafu: V neuteženem grafu lahko s pomočjo tehnike BFS poiščemo najmanjše drevo in najkrajšo pot med vozlišči.
Knjižnica Java Graph
Java ne zahteva, da programerji vedno izvajajo grafe v programu. Java ponuja veliko pripravljenih knjižnic, ki jih je mogoče neposredno uporabiti za uporabo grafov v programu. Te knjižnice imajo vse funkcije API-jev grafa, potrebne za polno uporabo grafa in njegovih različnih funkcij.
Spodaj je kratek uvod v nekatere knjižnice grafov v Javi.
# 1) Google Guava: Google Guava ponuja bogato knjižnico, ki podpira grafe in algoritme, vključno s preprostimi grafi, omrežji, vrednostnimi grafi itd.
# 2) Apache Commons: Apache Commons je projekt Apache, ki ponuja komponente podatkovne strukture Graph in API-je, ki imajo algoritme, ki delujejo na tej podatkovni strukturi grafa. Te komponente je mogoče ponovno uporabiti.
# 3) JGraphT: JGraphT je ena od pogosto uporabljenih knjižnic grafov Java. Ponuja funkcionalnost strukture podatkov grafov, ki vsebuje preprost graf, usmerjeni graf, tehtani graf itd., Pa tudi algoritme in API-je, ki delujejo na strukturi podatkov grafa.
# 4) SourceForge JUNG: JUNG pomeni 'Java Universal Network / Graph' in je javanski okvir. JUNG ponuja razširljiv jezik za analizo, vizualizacijo in modeliranje podatkov, ki jih želimo predstaviti kot graf.
JUNG ponuja tudi različne algoritme in rutine za razgradnjo, združevanje v skupine, optimizacijo itd.
Pogosto zastavljena vprašanja
V # 1) Kaj je graf v Javi?
Odgovor: Graf podatkovna struktura v glavnem shranjuje povezane podatke, na primer, mreža ljudi ali mreža mest. Struktura podatkov grafa je običajno sestavljena iz vozlišč ali točk, imenovanih oglišča. Vsaka točka je povezana z drugo točko s pomočjo povezav, imenovanih robovi.
Q # 2) Kakšne so vrste grafov?
Odgovor: Spodaj so navedene različne vrste grafov.
- Črtni graf: Črtni graf se uporablja za načrtovanje sprememb določene lastnosti glede na čas.
- Črtkasti graf: Palični grafi primerjajo številčne vrednosti entitet, kot so prebivalci v različnih mestih, odstotki pismenosti po državi itd.
Poleg teh glavnih tipov imamo na voljo tudi druge vrste, kot so piktograf, histogram, graf površine, razpršeni načrt itd.
V # 3) Kaj je povezan graf?
Odgovor: Povezani graf je graf, v katerem je vsako oglišče povezano z drugim ogliščem. V povezanem grafu lahko torej iz vsake druge točke dobimo vsako točko.
Q # 4) Kakšne so aplikacije grafa?
Odgovor: Grafi se uporabljajo v različnih aplikacijah. Graf lahko uporabimo za predstavitev zapletene mreže. Grafi se uporabljajo tudi v aplikacijah za družabna omrežja za označevanje omrežja ljudi, pa tudi za aplikacije, kot je iskanje sosednjih ljudi ali povezav.
Grafi se uporabljajo za označevanje poteka računanja v računalništvu.
V # 5) Kako shranite graf?
Odgovor: Graf lahko shranite v spomin na tri načine:
# 1) Vozlišča ali točke lahko shranimo kot predmete in robove kot kazalce.
#two) Grafe lahko shranimo tudi kot matrico sosednosti, katere vrstice in stolpci so enaki številu točk. Presečišče vsake vrstice in stolpca označuje prisotnost ali odsotnost roba. V netehtanem grafu je prisotnost roba označena z 1, medtem ko je v tehtanem grafu nadomeščena z utežjo roba.
# 3) Zadnji pristop k shranjevanju grafa je uporaba seznama sosednosti robov med oglišči ali vozlišči grafa. Vsako vozlišče ali oglišče ima svoj seznam sosednosti.
Zaključek
V tej vadnici smo podrobno obravnavali grafe v Javi. Raziskovali smo različne vrste grafov, izvedbo grafov in tehnike prečkanja. Grafe lahko uporabimo pri iskanju najkrajše poti med vozlišči.
V naših prihajajočih vajah bomo še naprej raziskovali grafe z razpravo o nekaj načinih iskanja najkrajše poti.
=> Tukaj si oglejte preproste vadbene serije Java.
Priporočeno branje
- Vadnica za odsev Java s primeri
- Kako uporabiti Dijkstrin algoritem v Javi
- Java SWING Vadnica: Vsebnik, komponente in obdelava dogodkov
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
- TreeMap v Javi - Vadnica z primeri Java TreeMap
- Dostopni modifikatorji v Javi - Vadnica s primeri
- Java String z vmesnikom String Buffer in String Builder
- Java String vsebuje () Vadnico metode s primeri