java graph tutorial how implement graph data structure
Aquest tutorial complet de Java Graph explica detalladament l'estructura de dades de Graph. Inclou com crear, implementar, representar i recórrer gràfics a Java:
Una estructura de dades de gràfics representa principalment una xarxa que connecta diversos punts. Aquests punts s’anomenen vèrtexs i els enllaços que connecten aquests vèrtexs s’anomenen 'Vores'. Per tant, un gràfic g es defineix com un conjunt de vèrtexs V i arestes E que connecten aquests vèrtexs.
Els gràfics s’utilitzen principalment per representar diverses xarxes com xarxes d’ordinadors, xarxes socials, etc. També es poden utilitzar per representar diverses dependències en programes o arquitectures. Aquests gràfics de dependència són molt útils per analitzar el programari i, de vegades, depurar-lo.
=> Consulteu TOTS els tutorials de Java aquí.
Què aprendreu:
- Estructura de dades de gràfics Java
- Com es crea un gràfic?
- Implementació de gràfics a Java
- Biblioteca de gràfics de Java
- Conclusió
Estructura de dades de gràfics Java
A continuació es mostra un gràfic que té cinc vèrtexs {A, B, C, D, E} i arestes donats per {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Com que les vores no mostren cap adreça, aquest gràfic es coneix com a 'gràfic sense direcció'.
A part del gràfic no dirigit que es mostra anteriorment, hi ha diverses variants del gràfic a Java.
Analitzem detalladament aquestes variants.
Diferents variants del gràfic
A continuació es mostren algunes de les variants del gràfic.
# 1) Gràfic dirigit
Un gràfic dirigit o dígraf és una estructura de dades de gràfics en què les vores tenen una direcció específica. S’originen a partir d’un vèrtex i culminen en un altre vèrtex.
El diagrama següent mostra l'exemple del gràfic dirigit.
En el diagrama anterior, hi ha una vora del vèrtex A al vèrtex B. Però tingueu en compte que A a B no és el mateix que B a A com en el gràfic no dirigit tret que hi hagi una vora especificada de B a A.
Un gràfic dirigit és cíclic si hi ha almenys un camí que té el seu primer i darrer vèrtex igual. Al diagrama anterior, un camí A-> B-> C-> D-> E-> A forma un cicle dirigit o un gràfic cíclic.
Per contra, un gràfic acíclic dirigit és un gràfic en el qual no hi ha cicle dirigit, és a dir, no hi ha cap camí que formi un cicle.
# 2) Gràfic ponderat
En un gràfic ponderat, un pess’associa a cada vora del gràfic. El pes normalment indica la distància entre els dos vèrtexs. El diagrama següent mostra el gràfic ponderat. Com que no es mostren adreces, aquest és el gràfic no dirigit.
Tingueu en compte que es pot dirigir o no dirigir un gràfic ponderat.
Com es crea un gràfic?
Java no proporciona una implementació completa de l'estructura de dades de gràfics. Tot i això, podem representar el gràfic per programació mitjançant Col·leccions a Java. També podem implementar un gràfic utilitzant matrius dinàmics com vectors.
Normalment, implementem gràfics a Java mitjançant la col·lecció HashMap. Els elements HashMap tenen la forma de parells clau-valor. Podem representar la llista d’adjacència de gràfics en un HashMap.
Una forma més comuna de crear un gràfic és mitjançant una de les representacions de gràfics com la matriu d’adjacència o la llista d’adjacències. A continuació, comentarem aquestes representacions i després implementarem el gràfic a Java mitjançant la llista d’adjacències per a la qual utilitzarem ArrayList.
Representació de gràfics a Java
Representació de gràfics: l'enfocament o la tècnica mitjançant la qual s'emmagatzemen les dades de gràfics a la memòria de l'ordinador.
Tenim dues representacions principals de gràfics com es mostra a continuació.
Matriu d’adjacència
Adjacency Matrix és una representació lineal de gràfics. Aquesta matriu emmagatzema el mapatge de vèrtexs i arestes del gràfic. A la matriu d'adjacència, els vèrtexs del gràfic representen files i columnes. Això significa que si el gràfic té N vèrtexs, llavors la matriu d’adjacència tindrà la mida NxN.
Si V és un conjunt de vèrtexs del gràfic, la intersecció Mija la llista d'adjacència = 1 significa que hi ha una vora existent entre els vèrtexs i i j.
Per entendre millor aquest concepte amb claredat, preparem una matriu d’adjacència per a un gràfic no dirigit.
Com es veu al diagrama anterior, veiem que per al vèrtex A, les interseccions AB i AE es defineixen a 1 ja que hi ha una vora de A a B i A a E. De la mateixa manera, la intersecció BA es posa a 1, ja que es tracta d’una gràfic i AB = BA. De la mateixa manera, hem establert totes les altres interseccions per a les quals hi ha una vora a 1.
En cas que la gràfica estigui dirigida, la intersecció Mijes posarà a 1 només si hi ha una vora clara dirigida de Vi a Vj.
Això es mostra a la següent il·lustració.
Com podem veure al diagrama anterior, hi ha una vora d'A a B. Així doncs, la intersecció AB s'estableix a 1, però la intersecció BA s'estableix a 0. Això és degut a que no hi ha cap vora dirigida de B a A.
Considerem els vèrtexs E i D. Veiem que hi ha arestes d'E a D, així com D a E. Per tant, hem establert aquestes dues interseccions a 1 en la matriu d'adjacència.
Ara passem a gràfics ponderats. Com sabem pel gràfic ponderat, a cada vora s’associa un enter també conegut com a pes. Representem aquest pes a la matriu d’adjacència de la vora que existeix. Aquest pes s’especifica sempre que hi ha una vora d’un vèrtex a un altre en lloc de ‘1’.
Aquesta representació es mostra a continuació.
Llista d'adjacència
En lloc de representar un gràfic com una matriu d’adjacència de naturalesa seqüencial, també podem utilitzar la representació vinculada. Aquesta representació enllaçada es coneix com a llista d’adjacències. Una llista d’adjacències no és altra cosa que una llista enllaçada i cada node de la llista representa un vèrtex.
La presència d’una vora entre dos vèrtexs es denota amb un punter des del primer vèrtex fins al segon. Aquesta llista d’adjacències es manté per a cada vèrtex del gràfic.
Quan hem recorregut tots els nodes adjacents per a un node concret, emmagatzemem NULL al següent camp de punter de l'últim node de la llista d'adjacència.
Ara farem servir els gràfics anteriors que hem utilitzat per representar la matriu d’adjacència per demostrar la llista d’adjacències.
La figura anterior mostra la llista d’adjacència del gràfic no dirigit. Veiem que cada vèrtex o node té la seva llista d’adjacències.
En el cas del gràfic no dirigit, les longituds totals de les llistes d’adjacència solen ser el doble del nombre d’arestes. Al gràfic anterior, el nombre total d’arestes és 6 i el total o suma de la longitud de tota la llista d’adjacències és 12.
Ara preparem una llista d’adjacència per al gràfic dirigit.
Com es veu a la figura anterior, al gràfic dirigit la longitud total de les llistes d’adjacència del gràfic és igual al nombre d’arestes del gràfic. Al gràfic anterior, hi ha 9 arestes i la suma de les longituds de les llistes d’adjacència d’aquest gràfic = 9.
Considerem ara el següent gràfic dirigit ponderat. Tingueu en compte que cada vora del gràfic ponderat té un pes associat. Per tant, quan representem aquest gràfic amb la llista d’adjacència, hem d’afegir un camp nou a cada node de llista que denoti el pes de la vora.
A continuació es mostra la llista d’adjacències del gràfic ponderat.
El diagrama anterior mostra el gràfic ponderat i la seva llista d’adjacències. Tingueu en compte que hi ha un nou espai a la llista d’adjacències que indica el pes de cada node.
Implementació de gràfics a Java
El programa següent mostra la implementació d'un gràfic a Java. Aquí hem utilitzat la llista d’adjacències per representar el gràfic.
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 Sortida:
Gràfic Java transversal
Per realitzar qualsevol acció significativa, com ara cercar la presència de qualsevol dada, hem de recórrer el gràfic de manera que cada vèrtex i la vora del gràfic es visiti almenys una vegada. Això es fa mitjançant algoritmes de gràfics que no són res més que un conjunt d’instruccions que ens ajuden a recórrer el gràfic.
Hi ha dos algorismes compatibles per recórrer el gràfic a Java .
convertidor de youtube a mp3 amb editor d’etiquetes
- Primera travessia de profunditat
- Primera travessia d'amplada
Traversal de primera profunditat
La cerca en profunditat (DFS) és una tècnica que s’utilitza per recórrer un arbre o un gràfic. La tècnica DFS comença amb un node arrel i després recorre els nodes adjacents del node arrel aprofundint en el gràfic. En la tècnica DFS, els nodes es recorren en profunditat fins que no hi hagi més nens que explorar.
Un cop arribem al node fulla (ja no hi ha nodes fills), el DFS retrocedeix i comença amb altres nodes i realitza el recorregut de manera similar. La tècnica DFS utilitza una estructura de dades de pila per emmagatzemar els nodes que s'estan travessant.
A continuació es mostra l’algorisme de la tècnica DFS.
Algorisme
Pas 1: Comenceu amb el node arrel i inseriu-lo a la pila
Pas 2: traieu l'element de la pila i inseriu-lo a la llista de 'visitats'
Pas 3: per al node marcat com a 'visitat' (o a la llista de visitats), afegiu a la pila els nodes adjacents d'aquest node que encara no estan marcats com a visitats.
Pas 4: Repetiu els passos 2 i 3 fins que la pila estigui buida.
Il·lustració de la tècnica DFS
Ara il·lustrarem la tècnica DFS utilitzant un exemple adequat de gràfic.
A continuació es mostra un exemple de gràfic. Mantenim la pila per emmagatzemar els nodes explorats i una llista per emmagatzemar els nodes visitats.
Començarem per A per començar, el marcarem com a visitat i l’afegirem a la llista de visitats. A continuació, considerarem tots els nodes adjacents d'A i empènyerem aquests nodes cap a la pila com es mostra a continuació.
A continuació, traiem un node de la pila, és a dir, B i el marquem com a visitat. Després l’afegim a la llista de ‘visitats’. Això es representa a continuació.
Ara considerem els nodes adjacents de B que són A i C. D'aquest A ja es visita. Així que ho ignorem. A continuació, fem sortir C de la pila. Marqueu C com a visitat. El node adjacent de C és a dir, E s’afegeix a la pila.
preguntes i respostes d’entrevistes conductuals per a analistes de negocis
A continuació, traiem el següent node E de la pila i el marquem com a visitat. El node adjacent del node E és C que ja es visita. Així que ho ignorem.
Ara només queda el node D a la pila. Per tant, el marquem com a visitat. El seu node adjacent és A que ja es visita. Per tant, no l’afegim a la pila.
En aquest moment, la pila està buida. Això significa que hem completat el recorregut de la primera profunditat del gràfic donat.
La llista visitada proporciona la seqüència final de recorregut mitjançant la tècnica de profunditat-primer. La seqüència DFS final per al gràfic anterior és A-> B-> C-> E-> D.
Implementació de 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 Sortida:
Aplicacions de DFS
# 1) Detectar un cicle en un gràfic: DFS facilita la detecció d’un cicle en un gràfic quan podem retrocedir a una vora.
# 2) Recorregut: Com ja hem vist a la il·lustració DFS, donats dos vèrtexs qualsevol podem trobar el camí entre aquests dos vèrtexs.
# 3) Mínim que abasta l'arbre i el camí més curt: Si executem la tècnica DFS al gràfic no ponderat, ens proporciona l’arbre d’extensió mínim i el camí curt.
# 4) Classificació topològica: L’ordenació topològica s’utilitza quan hem de programar els treballs. Tenim dependències entre diverses feines. També podem utilitzar l’ordenació topològica per resoldre dependències entre enllaçadors, planificadors d’instruccions, serialització de dades, etc.
Primera amplada transversal
La tècnica Breadth-first (BFS) utilitza una cua per emmagatzemar els nodes del gràfic. A diferència de la tècnica DFS, a BFS recorrem el gràfic de manera ampla. Això significa que recorrem el nivell del gràfic amb prudència. Quan explorem tots els vèrtexs o nodes a un nivell, passem al següent nivell.
A continuació es mostra un algoritme per a la tècnica de la primera amplada .
Algorisme
Vegem l'algorisme de la tècnica BFS.
Donat un gràfic G per al qual hem de realitzar la tècnica BFS.
- Pas 1: Comenceu pel node arrel i inseriu-lo a la cua.
- Pas 2: Repetiu els passos 3 i 4 per a tots els nodes del gràfic.
- Pas 3: Traieu el node arrel de la cua i afegiu-lo a la llista Visitats.
- Pas 4: Ara afegiu tots els nodes adjacents del node arrel a la cua i repeteix els passos 2 a 4 per a cada node. (FI DEL LLAÇ)
- Pas 6: SORTIR
Il·lustració de BFS
Il·lustrem la tècnica BFS mitjançant un exemple de gràfic que es mostra a continuació. Tingueu en compte que hem mantingut una llista anomenada 'Visitat' i una cua. Utilitzem el mateix gràfic que hem utilitzat a l’exemple de DFS amb finalitats de claredat.
Primer, comencem amb l’arrel, és a dir, el node A i l’afegim a la llista de visites. Tots els nodes adjacents del node A, és a dir, B, C i D, s’afegeixen a la cua.
A continuació, eliminem el node B de la cua. L’afegim a la llista de visitats i el marquem com a visitat. A continuació, explorem els nodes adjacents de B a la cua (C ja està a la cua). Ja es visita un altre node adjacent A, de manera que l’ignorem.
A continuació, eliminem el node C de la cua i el marquem com a visitat. Afegim C a la llista de visites i s’afegeix el node adjacent E a la cua.
A continuació, suprimim D de la cua i el marquem com a visitat. El node adjacent A del node D ja està visitat, de manera que l’ignorem.
Per tant, ara només hi ha el node E a la cua. El marquem com a visitat i l’afegim a la llista de visitats. El node adjacent d’E és C que ja es visita. Per tant, ignora-ho.
En aquest moment, la cua està buida i la llista visitada té la seqüència que hem obtingut com a resultat del recorregut de BFS. La seqüència és: A-> B-> C-> D-> E.
Implementació de BFS
El següent programa Java mostra la implementació de la tècnica 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 Sortida:
Aplicacions de BFS Traversal
# 1) Recollida d'escombraries: Un dels algoritmes que utilitza la tècnica de recollida d’escombraries per copiar la recollida d’escombraries és “l’algorisme de Cheney”. Aquest algorisme utilitza una tècnica de recorregut de primera amplada.
# 2) Emissió a les xarxes: L’emissió de paquets d’un punt a un altre en una xarxa es fa mitjançant la tècnica BFS.
# 3) Navegació GPS: Podem utilitzar la tècnica BFS per trobar nodes adjacents mentre naveguem amb GPS.
# 4) Llocs web de xarxes socials: La tècnica BFS també s'utilitza en llocs web de xarxes socials per trobar la xarxa de persones que envolten una persona en particular.
# 5) Camí més curt i arbre d’extensió mínim en un gràfic no ponderat: Al gràfic sense ponderar, es pot utilitzar la tècnica BFS per trobar un arbre d’extensió mínim i el camí més curt entre els nodes.
Biblioteca de gràfics de Java
Java no fa obligatori que els programadors implementin sempre els gràfics del programa. Java proporciona moltes biblioteques preparades que es poden utilitzar directament per fer ús de gràfics al programa. Aquestes biblioteques tenen totes les funcions de l'API de gràfics necessàries per fer un ús complet del gràfic i de les seves diverses funcions.
A continuació es mostra una breu introducció a algunes de les biblioteques de gràfics de Java.
# 1) Google Guava: Google Guava proporciona una rica biblioteca que admet gràfics i algorismes, inclosos gràfics senzills, xarxes, gràfics de valors, etc.
# 2) Apache Commons: Apache Commons és un projecte Apache que proporciona components d’estructura de dades de gràfics i API que tenen algoritmes que operen en aquesta estructura de dades de gràfics. Aquests components són reutilitzables.
# 3) JGraphT: JGraphT és una de les biblioteques de gràfics Java àmpliament utilitzades. Proporciona funcions d’estructura de dades de gràfics que contenen gràfics simples, gràfics dirigits, gràfics ponderats, etc., així com algorismes i API que funcionen a l’estructura de dades de gràfics.
# 4) SourceForge JUNG: JUNG significa 'Java Universal Network / Graph' i és un framework Java. JUNG proporciona un llenguatge extensible per a l'anàlisi, la visualització i el modelatge de les dades que volem que es representin com a gràfic.
JUNG també proporciona diversos algoritmes i rutines de descomposició, agrupació, optimització, etc.
Preguntes freqüents
P # 1) Què és un gràfic a Java?
Resposta: Una estructura de dades gràfiques emmagatzema principalment dades connectades, per exemple, una xarxa de persones o una xarxa de ciutats. Una estructura de dades de gràfics consisteix normalment en nodes o punts anomenats vèrtexs. Cada vèrtex està connectat a un altre vèrtex mitjançant enllaços anomenats arestes.
Q # 2) Quins són els tipus de gràfics?
Resposta: A continuació es detallen diferents tipus de gràfics.
- Gràfic lineal: S'utilitza un gràfic lineal per representar els canvis d'una propietat concreta en relació amb el temps.
- Gràfic de barres: Els gràfics de barres comparen valors numèrics d’entitats com la població de diverses ciutats, percentatges d’alfabetització a tot el país, etc.
A part d’aquests tipus principals, també tenim altres tipus com pictograma, histograma, gràfic d’àrea, gràfic de dispersió, etc.
P # 3) Què és un gràfic connectat?
Resposta: Un gràfic connectat és un gràfic en el qual cada vèrtex està connectat a un altre vèrtex. Per tant, al gràfic connectat podem arribar a tots els vèrtexs de tots els altres vèrtexs.
Q # 4) Quines són les aplicacions del gràfic?
Resposta: Els gràfics s’utilitzen en diverses aplicacions. El gràfic es pot utilitzar per representar una xarxa complexa. Els gràfics també s’utilitzen en aplicacions de xarxes socials per indicar la xarxa de persones, així com per a aplicacions com trobar persones o connexions adjacents.
Els gràfics s’utilitzen per denotar el flux de càlcul en informàtica.
Q # 5) Com s’emmagatzema un gràfic?
Resposta: Hi ha tres maneres d'emmagatzemar un gràfic a la memòria:
# 1) Podem emmagatzemar nodes o vèrtexs com a objectes i vores com a punteres.
# 2) També podem emmagatzemar gràfics com a matriu d’adjacència les files i columnes de les quals són el mateix que el nombre de vèrtexs. La intersecció de cada fila i columna denota la presència o absència d'una vora. En el gràfic no ponderat, la presència d’una vora es denota per 1 mentre que en el gràfic ponderat se substitueix pel pes de la vora.
# 3) L'últim enfocament per emmagatzemar un gràfic és utilitzar una llista d'adjacència d'arestes entre vèrtexs o nodes de gràfics. Cada node o vèrtex té la seva llista d’adjacència.
Conclusió
En aquest tutorial, hem debatut detalladament sobre els gràfics de Java. Hem explorat els diversos tipus de gràfics, la implementació de gràfics i les tècniques de recorregut. Es poden utilitzar gràfics per trobar el camí més curt entre nodes.
Als nostres propers tutorials, continuarem explorant gràfics discutint algunes maneres de trobar el camí més curt.
=> Vigileu aquí les sèries de formació Java senzilles.
Lectura recomanada
- Tutorial de reflexió de Java amb exemples
- Com implementar l’algorisme de Dijkstra a Java
- Tutorial Java SWING: Gestió de contenidors, components i esdeveniments
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- TreeMap a Java: tutorial amb exemples de Java TreeMap
- Modificadors d'accés a Java: tutorial amb exemples
- Java String amb buffer de cadenes i tutorial de Generador de cadenes
- Java String conté () Tutorial de mètode amb exemples
