java graph tutorial how implement graph data structure
Acest tutorial cuprinzător Java Graph explică în detaliu structura datelor grafice. Acesta include modul de creare, implementare, reprezentare și traversare a graficelor în Java:
O structură de date grafice reprezintă în principal o rețea care conectează diverse puncte. Aceste puncte sunt denumite vârfuri, iar legăturile care leagă aceste vârfuri se numesc „muchii”. Deci, un grafic g este definit ca un set de vârfuri V și muchii E care leagă aceste vârfuri.
Graficele sunt utilizate în cea mai mare parte pentru a reprezenta diverse rețele, cum ar fi rețelele de calculatoare, rețelele sociale etc. Acestea pot fi, de asemenea, utilizate pentru a reprezenta diferite dependențe în software sau arhitecturi. Aceste grafice de dependență sunt foarte utile în analiza software-ului și, uneori, în depanarea acestuia.
=> Verificați TOATE Tutorialele Java aici.
Ce veți învăța:
software-ul DVD rip and burn gratuit
- Structura de date Java Graph
- Cum se creează un grafic?
- Implementarea graficului în Java
- Biblioteca de grafice Java
- Concluzie
Structura de date Java Graph
Dat mai jos este un grafic având cinci vârfuri {A, B, C, D, E} și muchii date de {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Deoarece marginile nu prezintă nicio direcție, acest grafic este cunoscut sub numele de „grafic nedirectat”.
În afară de graficul neorientat prezentat mai sus, există mai multe variante ale graficului în Java.
Să discutăm în detaliu aceste variante.
Diferite variante de grafic
Următoarele sunt câteva dintre variantele graficului.
# 1) Grafic regizat
Un grafic direcționat sau un grafic este o structură de date a graficului în care marginile au o direcție specifică. Ele provin dintr-un vârf și culminează într-un alt vârf.
Următoarea diagramă arată exemplul graficului direcționat.
În diagrama de mai sus, există o margine de la vârful A la vârful B. Dar rețineți că A la B nu este același cu B la A ca în graficul nedirecționat, cu excepția cazului în care există o margine specificată de la B la A.
Un grafic direcționat este ciclic dacă există cel puțin o cale care are primul și ultimul vârf la fel. În diagrama de mai sus, o cale A-> B-> C-> D-> E-> A formează un ciclu direcționat sau un grafic ciclic.
În schimb, un grafic aciclic direcționat este un grafic în care nu există un ciclu direcționat, adică nu există o cale care să formeze un ciclu.
# 2) Grafic ponderat
Într-un grafic ponderat, o greutateeste asociat cu fiecare margine a graficului. Greutatea indică în mod normal distanța dintre cele două vârfuri. Următoarea diagramă arată graficul ponderat. Deoarece nu sunt afișate direcții, acesta este graficul neorientat.
Rețineți că un grafic ponderat poate fi direcționat sau neorientat.
Cum se creează un grafic?
Java nu oferă o implementare completă a structurii datelor grafice. Cu toate acestea, putem reprezenta graficul programatic folosind Colecții în Java. De asemenea, putem implementa un grafic folosind matrici dinamice precum vectori.
De obicei, implementăm grafice în Java folosind colecția HashMap. Elementele HashMap sunt sub formă de perechi cheie-valoare. Putem reprezenta lista de adiacență a graficului într-un HashMap.
Un mod cel mai obișnuit de a crea un grafic este prin utilizarea uneia dintre reprezentările graficelor, cum ar fi matricea de adiacență sau lista de adiacențe. Vom discuta aceste reprezentări în continuare și apoi vom implementa graficul în Java folosind lista de adiacențe pentru care vom folosi ArrayList.
Reprezentarea graficului în Java
Reprezentarea graficului înseamnă abordarea sau tehnica prin care datele graficului sunt stocate în memoria computerului.
Avem două reprezentări principale ale graficelor așa cum se arată mai jos.
Matricea adiacenței
Adjacency Matrix este o reprezentare liniară a graficelor. Această matrice stochează maparea vârfurilor și marginilor grafului. În matricea de adiacență, vârfurile graficului reprezintă rânduri și coloane. Aceasta înseamnă că dacă graficul are N vârfuri, atunci matricea de adiacență va avea dimensiunea NxN.
Dacă V este un set de vârfuri ale graficului, atunci intersecția Mijîn lista de adiacență = 1 înseamnă că există o margine între vârfurile i și j.
Pentru a înțelege mai bine acest concept, permiteți-ne să pregătim o matrice de adiacență pentru un grafic neorientat.
După cum se vede din diagrama de mai sus, vedem că pentru vârful A, intersecțiile AB și AE sunt setate la 1 deoarece există o margine de la A la B și de la A la E. În mod similar, intersecția BA este setată la 1, deoarece acesta este grafic și AB = BA. În mod similar, am setat toate celelalte intersecții pentru care există o margine la 1.
În cazul în care graficul este direcționat, intersecția Mijva fi setat la 1 numai dacă există o margine liberă direcționată de la Vi la Vj.
Acest lucru este prezentat în următoarea ilustrație.
După cum putem vedea din diagrama de mai sus, există o margine de la A la B. Deci, intersecția AB este setată la 1, dar intersecția BA este setată la 0. Acest lucru se datorează faptului că nu există o margine direcționată de la B la A.
Luați în considerare vârfurile E și D. Vedem că există muchii de la E la D, precum și de la D la E. Prin urmare, am stabilit ambele aceste intersecții la 1 în Matricea de adiacență.
Acum trecem la grafice ponderate. După cum știm pentru graficul ponderat, un număr întreg, cunoscut și sub numele de greutate, este asociat cu fiecare margine. Reprezentăm această greutate în Matricea de adiacență pentru marginea care există. Această greutate este specificată ori de câte ori există o margine de la un vârf la altul în loc de „1”.
Această reprezentare este prezentată mai jos.
Lista adiacenței
În loc să reprezentăm un grafic ca o matrice de adiacență care are o natură secvențială, putem folosi și reprezentarea legată. Această reprezentare legată este cunoscută sub numele de lista de adiacență. O listă de adiacență nu este altceva decât o listă legată și fiecare nod din listă reprezintă un vârf.
Prezența unei margini între două vârfuri este notată de un indicator de la primul vârf la al doilea. Această listă de adiacență este menținută pentru fiecare vârf din grafic.
După ce am parcurs toate nodurile adiacente pentru un anumit nod, stocăm NULL în câmpul următor al ultimului nod din lista de adiacențe.
Acum vom folosi graficele de mai sus pe care le-am folosit pentru a reprezenta matricea de adiacență pentru a demonstra lista de adiacențe.
Figura de mai sus prezintă lista de adiacență pentru graficul neorientat. Vedem că fiecare vârf sau nod are lista sa de adiacență.
În cazul graficului nedirecționat, lungimile totale ale listelor de adiacență sunt de obicei de două ori mai mari decât numărul de margini. În graficul de mai sus, numărul total de margini este 6, iar suma totală sau suma lungimii listei de adiacență este 12.
Acum, să pregătim o listă de adiacență pentru graficul direcționat.
După cum se vede din figura de mai sus, în graficul direcționat lungimea totală a listelor de adiacență a graficului este egală cu numărul de muchii din grafic. În graficul de mai sus, există 9 muchii și suma lungimilor listelor de adiacență pentru acest grafic = 9.
Acum să luăm în considerare următorul grafic direcționat ponderat. Rețineți că fiecare margine a graficului ponderat are o greutate asociată. Deci, atunci când reprezentăm acest grafic cu lista de adiacență, trebuie să adăugăm un câmp nou la fiecare nod de listă care va indica greutatea muchiei.
Lista de adiacențe pentru graficul ponderat este prezentată mai jos.
Ripper DVD gratuit pentru Windows 7
Diagrama de mai sus prezintă graficul ponderat și lista sa de adiacență. Rețineți că există un nou spațiu în lista de adiacență care denotă greutatea fiecărui nod.
Implementarea graficului în Java
Următorul program arată implementarea unui grafic în Java. Aici am folosit lista de adiacențe pentru a reprezenta graficul.
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 Ieșire:
Grafic Traversal Java
Pentru a efectua orice acțiune semnificativă, cum ar fi căutarea prezenței oricăror date, trebuie să traversăm graficul astfel încât fiecare vârf și marginea graficului să fie vizitate cel puțin o dată. Acest lucru se face folosind algoritmi de grafic care nu sunt altceva decât un set de instrucțiuni care ne ajută să traversăm graficul.
Există doi algoritmi suportați pentru a traversa graficul în Java .
- Traversarea adâncimii
- Lățimea primei traversări
Traversal de prima adâncime
Căutarea în profunzime (DFS) este o tehnică utilizată pentru a traversa un copac sau un grafic. Tehnica DFS începe cu un nod rădăcină și apoi traversează nodurile adiacente ale nodului rădăcină mergând mai adânc în grafic. În tehnica DFS, nodurile sunt traversate în profunzime până când nu mai sunt copii de explorat.
Odată ce am ajuns la nodul frunzei (nu mai există noduri copil), DFS retrogradează și începe cu alte noduri și efectuează traversarea în mod similar. Tehnica DFS utilizează o structură de date stivă pentru a stoca nodurile care sunt traversate.
Urmează algoritmul pentru tehnica DFS.
Algoritm
Pasul 1: Începeți cu nodul rădăcină și introduceți-l în stivă
Pasul 2: scoateți elementul din stivă și introduceți-l în lista „vizitat”
Pasul 3: Pentru nodul marcat ca „vizitat” (sau în lista vizitată), adăugați în stivă nodurile adiacente ale acestui nod care nu sunt încă marcate ca vizitate.
Pasul 4: Repetați pașii 2 și 3 până când stiva este goală.
Ilustrarea tehnicii DFS
Acum vom ilustra tehnica DFS folosind un exemplu adecvat de grafic.
Dat mai jos este un exemplu de grafic. Menținem stiva pentru a stoca nodurile explorate și o listă pentru a stoca nodurile vizitate.
Pentru început, vom începe cu A, îl vom marca ca vizitat și îl vom adăuga la lista vizitată. Apoi vom lua în considerare toate nodurile adiacente ale lui A și vom împinge aceste noduri pe stivă așa cum se arată mai jos.
Apoi, scoatem un nod din stivă, adică B și îl marcăm ca vizitat. Apoi îl adăugăm la lista „vizitată”. Aceasta este reprezentată mai jos.
Acum luăm în considerare nodurile adiacente ale lui B care sunt A și C. Din acest A este deja vizitat. Așa că o ignorăm. Apoi, scoatem C din stivă. Marcați C ca vizitat. Nodul adiacent al lui C adică E este adăugat la stivă.
Apoi, scoatem următorul nod E din stivă și îl marcăm ca vizitat. Nodul adiacent al nodului E este C care este deja vizitat. Așa că o ignorăm.
Acum doar nodul D rămâne în stivă. Așa că o marcăm ca fiind vizitată. Nodul său adiacent este A, care este deja vizitat. Deci nu îl adăugăm la stivă.
În acest moment stiva este goală. Aceasta înseamnă că am finalizat prima traversare a adâncimii pentru graficul dat.
Lista vizitată oferă secvența finală a traversării utilizând tehnica de adâncime-întâi. Secvența DFS finală pentru graficul de mai sus este A-> B-> C-> E-> D.
Implementarea 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 Ieșire:
Aplicații ale DFS
# 1) Detectați un ciclu într-un grafic: DFS facilitează detectarea unui ciclu într-un grafic atunci când putem retrograda pe o margine.
# 2) Căutare: După cum am văzut deja în ilustrația DFS, având în vedere oricare două vârfuri, putem găsi calea dintre aceste două vârfuri.
# 3) Minim arborele care se întinde și cea mai scurtă cale: Dacă executăm tehnica DFS pe graficul neponderat, aceasta ne oferă arborele minim de întindere și calea scurtcircuitată.
# 4) Sortare topologică: Sortarea topologică este utilizată atunci când trebuie să programăm lucrările. Avem dependențe între diferite locuri de muncă. De asemenea, putem folosi sortarea topologică pentru rezolvarea dependențelor dintre linkere, planificatoare de instrucțiuni, serializarea datelor etc.
Largime-primul Traversal
Tehnica Breadth-first (BFS) folosește o coadă pentru a stoca nodurile graficului. Spre deosebire de tehnica DFS, în BFS traversăm graficul în funcție de latime. Acest lucru înseamnă că traversăm nivelul graficului cu înțelepciune. Când explorăm toate vârfurile sau nodurile la un nivel, trecem la nivelul următor.
Dat mai jos este un algoritm pentru tehnica de traversare a lățimii .
Algoritm
Să vedem algoritmul pentru tehnica BFS.
Având în vedere un grafic G pentru care trebuie să realizăm tehnica BFS.
- Pasul 1: Începeți cu nodul rădăcină și introduceți-l în coadă.
- Pasul 2: Repetați pașii 3 și 4 pentru toate nodurile din grafic.
- Pasul 3: Eliminați nodul rădăcină din coadă și adăugați-l la lista Vizitat.
- Pasul 4: Acum adăugați la coadă toate nodurile adiacente ale nodului rădăcină și repetați pașii de la 2 la 4 pentru fiecare nod. (END OF LOOP)
- Pasul 6: IEȘIRE
Ilustrația BFS
Să ilustrăm tehnica BFS folosind un exemplu de grafic prezentat mai jos. Rețineți că am menținut o listă numită „Vizitat” și o coadă. Folosim același grafic pe care l-am folosit în exemplul DFS în scopuri de claritate.
În primul rând, începem cu rădăcina, adică nodul A și îl adăugăm la lista vizitată. Toate nodurile adiacente ale nodului A adică B, C și D sunt adăugate la coadă.
Apoi, eliminăm nodul B din coadă. Îl adăugăm la lista Vizitat și îl marcăm ca vizitat. Apoi, explorăm nodurile adiacente ale lui B în coadă (C este deja în coadă). Un alt nod adiacent A este deja vizitat, așa că îl ignorăm.
Apoi, eliminăm nodul C din coadă și îl marcăm ca vizitat. Adăugăm C la lista vizitată și nodul său adiacent E este adăugat la coadă.
Apoi, ștergem D din coadă și îl marcăm ca vizitat. Nodul adiacent al nodului D este deja vizitat, așa că îl ignorăm.
Deci, acum doar nodul E se află în coadă. Îl marcăm ca vizitat și îl adăugăm la lista vizitată. Nodul adiacent al lui E este C care este deja vizitat. Deci, ignoră-l.
În acest moment, coada este goală și lista vizitată are secvența pe care am obținut-o ca urmare a traversării BFS. Secvența este, A-> B-> C-> D-> E.
Implementarea BFS
Următorul program Java arată implementarea tehnicii 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 Ieșire:
Aplicații ale BFS Traversal
# 1) Colectarea gunoiului: Unul dintre algoritmii utilizați de tehnica de colectare a gunoiului pentru a copia colectarea gunoiului este „algoritmul lui Cheney”. Acest algoritm folosește o tehnică de traversare în primul rând.
# 2) Difuzarea în rețele: Transmiterea pachetelor de la un punct la altul într-o rețea se face folosind tehnica BFS.
# 3) Navigare GPS: Putem folosi tehnica BFS pentru a găsi noduri adiacente în timp ce navigați folosind GPS.
# 4) Site-uri de rețele sociale: Tehnica BFS este utilizată și în site-urile de rețele sociale pentru a găsi rețeaua de persoane care înconjoară o anumită persoană.
# 5) Calea cea mai scurtă și arborele minim care se întinde în graficul neponderat: În graficul neponderat, tehnica BFS poate fi utilizată pentru a găsi un copac minim care se întinde și cea mai scurtă cale între noduri.
Biblioteca de grafice Java
Java nu face obligatoriu ca programatorii să implementeze întotdeauna graficele din program. Java oferă o mulțime de biblioteci gata care pot fi utilizate direct pentru a utiliza graficele din program. Aceste biblioteci au toate funcționalitățile API grafice necesare pentru a utiliza pe deplin graficul și diversele sale caracteristici.
Mai jos este prezentată o scurtă introducere a unora dintre bibliotecile de grafice din Java.
# 1) Google Guava: Google Guava oferă o bibliotecă bogată care acceptă grafice și algoritmi, inclusiv grafice simple, rețele, grafice de valoare etc.
# 2) Apache Commons: Apache Commons este un proiect Apache care oferă componente ale structurii de date grafice și API-uri care au algoritmi care operează pe această structură de date grafice. Aceste componente sunt reutilizabile.
# 3) JGraphT: JGraphT este una dintre bibliotecile de grafice Java utilizate pe scară largă. Oferă funcționalitatea structurii de date a graficului care conține grafic simplu, grafic direcționat, grafic ponderat etc., precum și algoritmi și API-uri care funcționează pe structura de date a graficului.
# 4) SourceForge JUNG: JUNG înseamnă „Java Universal Network / Graph” și este un framework Java. JUNG oferă un limbaj extensibil pentru analiză, vizualizare și modelare a datelor pe care dorim să le reprezentăm ca grafic.
JUNG oferă, de asemenea, diferiți algoritmi și rutine pentru descompunere, grupare, optimizare etc.
întrebări frecvente
Q # 1) Ce este un grafic în Java?
Răspuns: O structură de date grafice stochează în principal datele conectate, de exemplu, o rețea de oameni sau o rețea de orașe. O structură de date grafice constă de obicei din noduri sau puncte numite vârfuri. Fiecare vârf este conectat la un alt vârf folosind legături numite margini.
Q # 2) Care sunt tipurile de grafice?
Răspuns: Diferite tipuri de grafice sunt enumerate mai jos.
- Grafic liniar: Un grafic liniar este utilizat pentru a trasa modificările într-o anumită proprietate în raport cu timpul.
- Grafic de bare: Graficele cu bare compară valorile numerice ale entităților precum populația din diferite orașe, procentele de alfabetizare din toată țara etc.
În afară de aceste tipuri principale, avem și alte tipuri, cum ar fi pictograma, histograma, graficul de suprafață, graficul de dispersie etc.
Q # 3) Ce este un grafic conectat?
Răspuns: Un grafic conectat este un grafic în care fiecare vârf este conectat la un alt vârf. Prin urmare, în graficul conectat, putem ajunge la fiecare vârf din orice alt vârf.
Q # 4) Care sunt aplicațiile graficului?
curățare și reparații gratuite de registre Windows
Răspuns: Graficele sunt utilizate într-o varietate de aplicații. Graficul poate fi folosit pentru a reprezenta o rețea complexă. Graficele sunt, de asemenea, utilizate în aplicațiile de rețele sociale pentru a indica rețeaua de oameni, precum și pentru aplicații precum găsirea de persoane adiacente sau conexiuni.
Graficele sunt utilizate pentru a indica fluxul de calcul în informatică.
Q # 5) Cum stocați un grafic?
Răspuns: Există trei moduri de a stoca un grafic în memorie:
# 1) Putem stoca noduri sau vârfuri ca obiecte și margini ca indicatori.
#Două) De asemenea, putem stoca grafice ca matrice de adiacență ale căror rânduri și coloane sunt identice cu numărul de vârfuri. Intersecția fiecărui rând și coloană denotă prezența sau absența unei margini. În graficul neponderat, prezența unei muchii este notată cu 1 în timp ce în graficul ponderat este înlocuită cu greutatea muchiei.
# 3) Ultima abordare a stocării unui grafic este prin utilizarea unei liste de adiacență a muchiilor între nodurile sau nodurile grafului. Fiecare nod sau vârf are lista sa de adiacență.
Concluzie
În acest tutorial, am discutat în detaliu grafice în Java. Am explorat diferitele tipuri de grafice, implementarea graficelor și tehnici de traversare. Graficele pot fi folosite pentru a găsi cea mai scurtă cale între noduri.
În tutorialele noastre viitoare, vom continua să explorăm grafice discutând câteva modalități de a găsi cea mai scurtă cale.
=> Urmăriți aici seria de antrenament Java simplă.
Lectură recomandată
- Tutorial de reflecție Java cu exemple
- Cum să implementăm algoritmul Dijkstra în Java
- Tutorial Java SWING: Container, componente și gestionarea evenimentelor
- Tutorial JAVA pentru începători: peste 100 de cursuri video Java practice
- TreeMap în Java - Tutorial cu exemple de TreeMap Java
- Modificatori de acces în Java - Tutorial cu exemple
- Java String cu buffer de șiruri și tutorial de generare de șiruri
- Șirul Java conține () Tutorial metodă cu exemple
