Menu

Výukový program pre graf Java - Ako implementovať dátovú štruktúru grafu

  • Hlavná
  • Iné
  • Výukový program pre graf Java - Ako implementovať dátovú štruktúru grafu

java graph tutorial how implement graph data structure

oracle pl sql rozhovor otázky pre 8 rokov skúseností

Tento komplexný výukový program Java Graph podrobne vysvetľuje štruktúru dát grafu. Zahŕňa ako vytvárať, implementovať, reprezentovať a prechádzať grafy v Jave:

Grafová dátová štruktúra predstavuje hlavne sieť spájajúcu rôzne body. Tieto body sa nazývajú vrcholy a spojenia spájajúce tieto vrcholy sa nazývajú „Hrany“. Takže graf g je definovaný ako množina vrcholov V a hrán E, ktoré tieto vrcholy spájajú.

Grafy sa väčšinou používajú na znázornenie rôznych sietí, ako sú počítačové siete, sociálne siete atď. Môžu sa tiež použiť na vyjadrenie rôznych závislostí v softvéri alebo architektúre. Tieto grafy závislostí sú veľmi užitočné pri analýze softvéru a tiež pri jeho ladení.

=> Skontrolujte VŠETKY návody Java tu.

Štruktúra dát grafu

Čo sa dozviete:

Dátová štruktúra Java Graph

Ďalej je uvedený graf s piatimi vrcholmi {A, B, C, D, E} a hranami danými znakmi {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Pretože okraje nezobrazujú žiadne smery, tento graf sa nazýva „neorientovaný graf“.

Neusmernený graf
Neusmernený graf

Okrem neorientovaného grafu zobrazeného vyššie existuje v Jave niekoľko variantov grafu.

Poďme si tieto varianty podrobne rozobrať.

Rôzne varianty grafu

Nasleduje niekoľko variantov grafu.

# 1) Nasmerovaný graf

Smerovaný graf alebo digraf je dátová štruktúra grafu, v ktorej majú hrany konkrétny smer. Vychádzajú z jedného vrcholu a kulminujú do iného vrcholu.

Nasledujúca schéma zobrazuje príklad smerovaného grafu.

smerovaný graf
Nasmerovaný graf

Vo vyššie uvedenom diagrame je hrana od vrcholu A po vrchol B. Všimnite si však, že A až B nie sú rovnaké ako B až A, ako v neusmernenom grafe, pokiaľ nie je hrana určená od B po A.

Smerovaný graf je cyklický, ak existuje aspoň jedna cesta, ktorá má prvý a posledný vrchol rovnako. Vo vyššie uvedenom diagrame tvorí cesta A-> B-> C-> D-> E-> A usmernený cyklus alebo cyklický graf.

Naopak, usmernený acyklický graf je graf, v ktorom neexistuje žiadny riadený cyklus, t. J. Neexistuje žiadna cesta, ktorá tvorí cyklus.

# 2) Vážený graf

Vo váženom grafe váhaje spojená s každou hranou grafu. Váha zvyčajne označuje vzdialenosť medzi dvoma vrcholmi. Nasledujúci diagram zobrazuje vážený graf. Pretože nie sú zobrazené žiadne pokyny, jedná sa o neusmernený graf.

vážený graf
Vážený graf

Vážený graf môže byť nasmerovaný alebo neusmernený.

Ako vytvoriť graf?

Java neposkytuje plnohodnotnú implementáciu dátovej štruktúry grafu. Graf však môžeme programovo reprezentovať pomocou zbierok v Jave. Môžeme tiež implementovať graf pomocou dynamických polí, ako sú vektory.

Grafy zvyčajne implementujeme v Jave pomocou kolekcie HashMap. Prvky HashMap sú vo forme párov kľúč - hodnota. Zoznam susedných grafov môžeme reprezentovať v HashMape.

Najbežnejším spôsobom, ako vytvoriť graf, je použitie jednej z reprezentácií grafov, ako je matica susedstva alebo zoznam susedstiev. O týchto znázorneniach budeme diskutovať ďalej a potom implementujeme graf v Jave pomocou zoznamu susedstiev, pre ktorý použijeme ArrayList.

Reprezentácia grafov v Jave

Grafické znázornenie znamená prístup alebo techniku, pomocou ktorej sa údaje grafu ukladajú do pamäte počítača.

Máme dve hlavné znázornenia grafov, ako je uvedené nižšie.

Matica susedstva

Adjacency Matrix je lineárne znázornenie grafov. Táto matica ukladá mapovanie vrcholov a hrán grafu. V matici susedstva vrcholy grafu predstavujú riadky a stĺpce. To znamená, že ak má graf N vrcholov, potom matica susednosti bude mať veľkosť NxN.

Ak V je množina vrcholov grafu, potom priesečník Mijv zozname susedstiev = 1 znamená, že medzi vrcholmi i a j existuje hrana.

Aby sme lepšie pochopili tento pojem, pripravme si maticu susednosti pre neorientovaný graf.

Matica susedstva

Ako je zrejmé z vyššie uvedeného diagramu, vidíme, že pre vrchol A sú križovatky AB a AE nastavené na 1, pretože existuje hrana z A do B a A do E. Podobne je križovatka BA nastavená na 1, pretože ide o neorientovaný smer graf a AB = BA. Podobne sme nastavili všetky ostatné križovatky, pre ktoré je hrana, na 1.

V prípade, že je graf nasmerovaný, priesečník Mijsa nastaví na 1, iba ak je z Vi na Vj zreteľná hrana.

To je znázornené na nasledujúcom obrázku.

Matica susedstva - smerovaný graf

Ako vidíme z vyššie uvedeného diagramu, je tu hrana od A do B. Takže križovatka AB je nastavená na 1, ale križovatka BA je nastavená na 0. Je to preto, že z B do A nie je hrana nasmerovaná.

Uvažujme o vrcholoch E a D. Vidíme, že existujú hrany od E po D, ako aj od D po E. Preto sme obidve tieto križovatky nastavili na 1 v susednej matici.

Teraz prejdeme k váženým grafom. Ako vieme pre vážený graf, s každou hranou je spojené celé číslo známe tiež ako váha. Túto váhu reprezentujeme v susednosti Matrix pre existujúcu hranu. Táto váha je určená vždy, keď existuje hrana z jedného vrcholu do druhého namiesto „1“.

Toto znázornenie je zobrazené nižšie.

Matica susednosti - smerovaný vážený graf

Zoznam susedov

Namiesto toho, aby sme graf reprezentovali ako maticu susednosti, ktorá má sekvenčnú povahu, môžeme použiť aj prepojenú reprezentáciu. Toto prepojené zobrazenie je známe ako zoznam susedov. Zoznam susedstiev nie je nič iné ako prepojený zoznam a každý uzol v zozname predstavuje vrchol.

Prítomnosť hrany medzi dvoma vrcholmi je označená ukazovateľom od prvého vrcholu k druhému. Tento zoznam susedných vzťahov sa zachováva pre každý vrchol v grafe.

Keď sme prekonali všetky susedné uzly pre konkrétny uzol, uložíme NULL do nasledujúceho pointerového poľa posledného uzla zoznamu susednosti.

Teraz použijeme vyššie uvedené grafy, ktoré sme použili na predstavenie matice susedstva, aby sme demonštrovali zoznam susedstiev.

preukázať zoznam susedov.

Vyššie uvedený obrázok zobrazuje zoznam susedstiev pre neorientovaný graf. Vidíme, že každý vrchol alebo uzol má svoj zoznam susednosti.

V prípade neusmerneného grafu sú celkové dĺžky zoznamov susedných vzťahov zvyčajne dvojnásobkom počtu hrán. Vo vyššie uvedenom grafe je celkový počet hrán 6 a celková alebo súčet dĺžok všetkých zoznamov susedných vzťahov 12.

Teraz si pripravme zoznam susedstiev pre smerovaný graf.

celková dĺžka susedstva

Ako je zrejmé z vyššie uvedeného obrázku, v usmernenom grafe sa celková dĺžka zoznamov susednosti grafu rovná počtu hrán v grafe. Vo vyššie uvedenom grafe je 9 hrán a súčet dĺžok zoznamov susednosti pre tento graf = 9.

Uvažujme teraz o nasledujúcom váženom usmernenom grafe. Upozorňujeme, že každá hrana váženého grafu má priradenú váhu. Takže keď reprezentujeme tento graf zoznamom susednosti, musíme do každého uzla zoznamu pridať nové pole, ktoré bude označovať váhu okraja.

Zoznam susedstiev pre vážený graf je uvedený nižšie.

vážený graf

Vyššie uvedený diagram zobrazuje vážený graf a zoznam jeho susedov. Upozorňujeme, že v zozname susedstiev je nový priestor, ktorý označuje váhu každého uzla.

Implementácia grafov v Jave

Nasledujúci program ukazuje implementáciu grafu v Jave. Tu sme použili zoznam susedstiev na znázornenie grafu.

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

Výkon:

výkon

Graf Traversal Java

Ak chcete vykonať akúkoľvek zmysluplnú akciu, napríklad vyhľadať prítomnosť akýchkoľvek údajov, musíme grafom prejsť, aby bol každý vrchol a okraj grafu navštívený aspoň raz. To sa deje pomocou algoritmov grafov, ktoré nie sú ničím iným ako súborom pokynov, ktoré nám pomáhajú prechádzať grafom.

Na prechádzanie grafom v Jave sú podporované dva algoritmy .

  1. Prechod do hĺbky
  2. Prvý priechod šírkou

Traverz do hĺbky

Vyhľadávanie do hĺbky (DFS) je technika, ktorá sa používa na prechádzanie stromom alebo grafom. Technika DFS začína koreňovým uzlom a potom prechádza cez susedné uzly koreňového uzla hlbšie do grafu. V technike DFS sa uzly prechádzajú hĺbkovo, až kým nebudú viac detí na preskúmanie.

Akonáhle dosiahneme listový uzol (už žiadne podradené uzly), DFS ustúpi a začne s ostatnými uzlami a vykoná prechod podobným spôsobom. Technika DFS používa na ukladanie uzlov, cez ktoré sa prechádza, štruktúru dát zo zásobníka.

Nasleduje algoritmus pre techniku ​​DFS.

Algoritmus

Krok 1: Začnite s koreňovým uzlom a vložte ho do zásobníka

Krok 2: Vyberte položku zo stohu a vložte ju do „navštíveného“ zoznamu

Krok 3: Pre uzol označený ako „navštívený“ (alebo v zozname navštívených) pridajte do zásobníka susedné uzly tohto uzla, ktoré ešte nie sú označené ako navštívené.

Krok 4: Opakujte kroky 2 a 3, kým nie je zásobník prázdny.

Ilustrácia techniky DFS

anime stránky na pozeranie anime zadarmo

Teraz si ukážeme techniku ​​DFS na vhodnom príklade grafu.

Ďalej je uvedený príklad grafu. Udržiavame zásobník na ukladanie preskúmaných uzlov a zoznam na ukladanie navštívených uzlov.

Technika DFS

Začneme písmenom A, začneme s tým, že ho označíme ako navštívené a pridáme do zoznamu navštívených. Potom zvážime všetky susedné uzly A a zatlačíme ich na uzol, ako je to znázornené nižšie.

uzol zo zásobníka

Ďalej vysunieme uzol zo zásobníka, tj. B, a označíme ho ako navštívený. Potom ho pridáme do „navštíveného“ zoznamu. Toto je znázornené nižšie.

susedné uzly

Teraz uvažujeme susedné uzly B, ktoré sú A a C. Z tohto A je už navštívený. Takže to ignorujeme. Ďalej vysunieme C zo stohu. Označte C ako navštívené. Susedný uzol C, t. J. Je pridaný do stohu.

ďalší uzol

Ďalej vysunieme ďalší uzol E zo zásobníka a označíme ho ako navštívený. Susedným uzlom uzla E je C, ktorý je už navštívený. Takže to ignorujeme.

D zostáva v zásobníku

Teraz v zásobníku zostáva iba uzol D. Takže to označíme ako navštívené. Jeho susedným uzlom je A, ktorý je už navštívený. Takže to nepridávame do stohu.

priechod do hĺbky

V tomto okamihu je zásobník prázdny. To znamená, že sme pre daný graf dokončili priechod prvej hĺbky.

Navštívený zoznam poskytuje konečnú sekvenciu prechodu pomocou techniky hĺbky prvý. Konečná sekvencia DFS pre vyššie uvedený graf je A-> B-> C-> E-> D.

Implementácia 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

Výkon:

výkon

Aplikácie DFS

# 1) Zistite cyklus v grafe: DFS uľahčuje detekciu cyklu v grafe, keď môžeme ustúpiť na hranu.

# 2) Nájdenie cesty: Ako sme už videli na ilustrácii DFS, vzhľadom na ľubovoľné dva vrcholy môžeme nájsť cestu medzi týmito dvoma vrcholmi.

# 3) Minimum klenutý strom a najkratšia cesta: Ak spustíme techniku ​​DFS na neváženom grafe, dá nám to minimálny rozsahový strom a skratovanú cestu.

# 4) Topologické triedenie: Topologické triedenie sa používa, keď musíme naplánovať úlohy. Máme závislosti medzi rôznymi zamestnaniami. Môžeme tiež použiť topologické triedenie na riešenie závislostí medzi linkermi, plánovačmi inštrukcií, serializáciou dát atď.

Prechod na šírku

Technika šírky na šírku (BFS) používa na uloženie uzlov grafu front. Pokiaľ ide o techniku ​​DFS, v BFS prechádzame grafom po šírke. To znamená, že prechádzame grafom po úrovniach. Keď preskúmame všetky vrcholy alebo uzly na jednej úrovni, postúpime do ďalšej úrovne.

Ďalej je uvedený algoritmus pre techniku ​​priečneho šírenia .

Algoritmus

Pozrime sa na algoritmus pre techniku ​​BFS.

Daný graf G, pre ktorý musíme vykonať techniku ​​BFS.

  • Krok 1: Začnite koreňovým uzlom a vložte ho do poradia.
  • Krok 2: Zopakujte kroky 3 a 4 pre všetky uzly v grafe.
  • Krok 3: Odstráňte koreňový uzol z frontu a pridajte ho do zoznamu Navštívené.
  • Krok 4: Teraz pridajte do fronty všetky susedné uzly koreňového uzla a pre každý uzol opakujte kroky 2 až 4. [KONIEC SLUČKY]
  • Krok 6: VÝCHOD

Ilustrácia BFS

Ukážme si techniku ​​BFS na príklade grafu uvedeného nižšie. Upozorňujeme, že sme udržiavali zoznam s názvom Navštívené a poradie. Na účely prehľadnosti používame rovnaký graf, aký sme použili v príklade DFS.

Ilustrácia BFS

Najprv začneme rootom, teda uzlom A a pridáme ho do zoznamu navštívených. Všetky susedné uzly uzla A, t. J. B, C a D, sa pridajú do frontu.

Navštívený zoznam a značka

Ďalej odstránime uzol B z frontu. Pridáme ho do zoznamu Navštívené a označíme ako navštívený. Ďalej preskúmame susedné uzly B vo fronte (C je už vo fronte). Ďalší susedný uzol A je už navštívený, takže ho ignorujeme.

Navštívený zoznam a značka

Ďalej odstránime uzol C z frontu a označíme ho ako navštívený. Pridáme C do navštíveného zoznamu a jeho susedný uzol E sa pridá do poradia.

poradie a známka

Ďalej odstránime D z frontu a označíme ho ako navštívený. Susedný uzol A uzla D je už navštívený, takže ho ignorujeme.

D je susedný uzol A

Takže teraz je vo fronte iba uzol E. Označíme ho ako navštívený a pridáme do zoznamu navštívených. Susedným uzlom E je C, ktorý je už navštívený. Tak to ignoruj.

výsledok prechodu BFS

V tomto okamihu je rad prázdny a navštívený zoznam má postupnosť, ktorú sme získali v dôsledku prechodu BFS. Sekvencia je A-> B-> C-> D-> E.

Implementácia BFS

Nasledujúci program Java ukazuje implementáciu techniky 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

Výkon:

výkon

Aplikácie BFS Traversal

# 1) Zber odpadu: Jedným z algoritmov používaných technikou odvozu odpadu na kopírovanie zberu odpadu je „Cheneyho algoritmus“. Tento algoritmus využíva techniku ​​priečneho šírenia.

# 2) Vysielanie v sieťach: Vysielanie paketov z jedného bodu do druhého v sieti sa vykonáva pomocou techniky BFS.

# 3) GPS navigácia: Na nájdenie susedných uzlov pri navigácii pomocou GPS môžeme použiť techniku ​​BFS.

# 4) Webové stránky sociálnych sietí: Technika BFS sa tiež používa na webových stránkach sociálnych sietí na nájdenie siete ľudí obklopujúcich konkrétnu osobu.

# 5) Najkratšia cesta a minimálny rozpätie stromu v neváženom grafe: V neváženom grafe je možné pomocou techniky BFS nájsť minimálny rozpätie stromu a najkratšiu cestu medzi uzlami.

Knižnica grafov Java

Program Java nestanovuje, že programátori musia vždy implementovať grafy v programe. Java poskytuje veľa pripravených knižníc, ktoré možno priamo použiť na použitie grafov v programe. Tieto knižnice majú všetky funkcie grafického rozhrania API potrebné na úplné využitie grafu a jeho rôznych funkcií.

Ďalej je uvedený stručný úvod do niektorých knižníc grafov v prostredí Java.

# 1) Google Guava: Google Guava poskytuje bohatú knižnicu, ktorá podporuje grafy a algoritmy vrátane jednoduchých grafov, sietí, hodnotových grafov atď.

# 2) Apache Commons: Apache Commons je projekt Apache, ktorý poskytuje komponenty dátovej štruktúry Graph a API, ktoré majú algoritmy fungujúce na tejto dátovej štruktúre grafu. Tieto komponenty sú opakovane použiteľné.

# 3) JGraphT: JGraphT je jednou z najbežnejšie používaných knižníc grafov v jazyku Java. Poskytuje funkčnosť dátovej štruktúry grafu, ktorá obsahuje jednoduchý graf, smerovaný graf, vážený graf atď., Ako aj algoritmy a API, ktoré pracujú s dátovou štruktúrou grafu.

# 4) SourceForge JUNG: JUNG znamená “Java Universal Network / Graph” a je to Java framework. JUNG poskytuje rozšíriteľný jazyk pre analýzu, vizualizáciu a modelovanie údajov, ktoré chceme reprezentovať ako graf.

JUNG tiež poskytuje rôzne algoritmy a postupy na rozklad, zhlukovanie, optimalizáciu atď.

často kladené otázky

Otázka č. 1) Čo je graf v prostredí Java?

Odpoveď: Grafová dátová štruktúra uchováva hlavne spojené údaje, napríklad, sieť ľudí alebo sieť miest. Dátová štruktúra grafu sa zvyčajne skladá z uzlov alebo bodov nazývaných vrcholy. Každý vrchol je spojený s iným vrcholom pomocou odkazov nazývaných hrany.

Otázka č. 2) Aké sú typy grafov?

Odpoveď: Rôzne typy grafov sú uvedené nižšie.

  1. Čiarový graf: Čiarový graf sa používa na vykreslenie zmien konkrétnej vlastnosti v pomere k času.
  2. Stĺpcový graf: Stĺpcové grafy porovnávajú číselné hodnoty entít, ako je populácia v rôznych mestách, percentuálna gramotnosť v celej krajine atď.

Okrem týchto hlavných typov máme aj ďalšie typy ako piktogram, histogram, plošný graf, bodový diagram atď.

Otázka č. 3) Čo je to pripojený graf?

Odpoveď: Pripojený graf je graf, v ktorom je každý vrchol spojený s iným vrcholom. V spojenom grafe sa teda môžeme dostať na každý vrchol z každého druhého vrcholu.

Otázka č. 4) Aké sú použitia grafu?

Odpoveď: Grafy sa používajú v rôznych aplikáciách. Graf je možné použiť na znázornenie zložitej siete. Grafy sa tiež používajú v aplikáciách sociálnych sietí na označenie siete ľudí, ako aj na aplikácie ako hľadanie susedných osôb alebo spojenia.

bezplatná ochrana brány firewall pre systém Windows 10

Grafy sa používajú na označenie toku výpočtov v informatike.

Otázka č. 5) Ako ukladáte graf?

Odpoveď: Existujú tri spôsoby, ako uložiť graf do pamäte:

# 1) Uzly alebo vrcholy môžeme ukladať ako objekty a hrany ako ukazovatele.

#dva) Môžeme tiež uložiť grafy ako maticu susednosti, ktorej riadky a stĺpce sú rovnaké ako počet vrcholov. Priesečník každého riadku a stĺpca označuje prítomnosť alebo neprítomnosť okraja. V neváženom grafe je prítomnosť okraja označená číslom 1, zatiaľ čo vo váženom grafe je nahradená váhou okraja.

# 3) Posledným prístupom k ukladaniu grafov je použitie zoznamu susedných hrán medzi vrcholmi alebo uzlami grafu. Každý uzol alebo vrchol má svoj zoznam susedstiev.

Záver

V tomto výučbe sme podrobne diskutovali o grafoch v Jave. Preskúmali sme rôzne typy grafov, implementáciu grafov a techniky prechodu. Pri hľadaní najkratšej cesty medzi uzlami je možné použiť grafy.

V našich pripravovaných tutoriáloch budeme pokračovať v skúmaní grafov diskusiou o niekoľkých spôsoboch hľadania najkratšej cesty.

=> Dajte si pozor na jednoduchú sériu školení Java tu.

Odporúčané čítanie

^