java graph tutorial how implement graph data structure
Questo tutorial completo sui grafici Java spiega in dettaglio la struttura dei dati del grafico. Include come creare, implementare, rappresentare e attraversare grafici in Java:
Una struttura dati a grafo rappresenta principalmente una rete che collega vari punti. Questi punti sono definiti come vertici e i collegamenti che collegano questi vertici sono chiamati 'Bordi'. Quindi un grafo g è definito come un insieme di vertici V e archi E che collegano questi vertici.
I grafici sono usati principalmente per rappresentare varie reti come reti di computer, social network, ecc. Possono anche essere usati per rappresentare varie dipendenze in software o architetture. Questi grafici delle dipendenze sono molto utili per analizzare il software e, a volte, anche per il debug.
=> Controlla TUTTI i tutorial Java qui.
Cosa imparerai:
- Struttura dei dati del grafico Java
- Come creare un grafico?
- Implementazione del grafico in Java
- Libreria Java Graph
- Conclusione
Struttura dei dati del grafico Java
Di seguito è riportato un grafo con cinque vertici {A, B, C, D, E} e archi dati da {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Poiché i bordi non mostrano alcuna direzione, questo grafico è noto come 'grafico non orientato'.
Oltre al grafico non orientato mostrato sopra, ci sono diverse varianti del grafico in Java.
Discutiamo queste varianti in dettaglio.
Diverse varianti di grafico
Le seguenti sono alcune delle varianti del grafico.
# 1) Grafico diretto
Un grafico orientato o digrafo è una struttura dati del grafico in cui i bordi hanno una direzione specifica. Hanno origine da un vertice e culminano in un altro vertice.
Il diagramma seguente mostra l'esempio di grafico diretto.
Nel diagramma sopra, c'è un bordo dal vertice A al vertice B. Ma si noti che A a B non è lo stesso da B ad A come nel grafico non orientato a meno che non sia specificato un bordo da B ad A.
Un grafo orientato è ciclico se c'è almeno un percorso che ha il primo e l'ultimo vertice uguali. Nel diagramma sopra, un percorso A-> B-> C-> D-> E-> A forma un ciclo diretto o un grafico ciclico.
Al contrario, un grafico aciclico diretto è un grafico in cui non esiste un ciclo diretto, ovvero non esiste un percorso che forma un ciclo.
# 2) Grafico ponderato
In un grafico ponderato, un pesoè associato a ciascun bordo del grafico. Il peso normalmente indica la distanza tra i due vertici. Il diagramma seguente mostra il grafico ponderato. Poiché non vengono mostrate direzioni, questo è il grafico non orientato.
Notare che un grafico ponderato può essere diretto o non orientato.
Come creare un grafico?
Java non fornisce un'implementazione completa della struttura dei dati del grafico. Tuttavia, possiamo rappresentare il grafico a livello di codice utilizzando le raccolte in Java. Possiamo anche implementare un grafico utilizzando array dinamici come vettori.
Di solito, implementiamo grafici in Java utilizzando la raccolta HashMap. Gli elementi HashMap sono sotto forma di coppie chiave-valore. Possiamo rappresentare l'elenco di adiacenza del grafico in una HashMap.
Un modo più comune per creare un grafico è utilizzare una delle rappresentazioni dei grafici come la matrice di adiacenza o l'elenco di adiacenza. Discuteremo successivamente queste rappresentazioni e poi implementeremo il grafico in Java usando l'elenco di adiacenza per il quale useremo ArrayList.
Rappresentazione grafica in Java
Rappresentazione grafica indica l'approccio o la tecnica che utilizza i dati del grafico archiviati nella memoria del computer.
Abbiamo due rappresentazioni principali di grafici come mostrato di seguito.
Matrice di adiacenza
La matrice di adiacenza è una rappresentazione lineare di grafici. Questa matrice memorizza la mappatura dei vertici e dei bordi del grafico. Nella matrice di adiacenza, i vertici del grafico rappresentano righe e colonne. Ciò significa che se il grafo ha N vertici, la matrice di adiacenza avrà dimensione NxN.
Se V è un insieme di vertici del grafo, l'intersezione Mijnella lista delle adiacenze = 1 significa che esiste un bordo esistente tra i vertici i e j.
Per comprendere meglio questo concetto in modo chiaro, prepariamo una matrice di adiacenza per un grafo non orientato.
Come si vede dal diagramma sopra, vediamo che per il vertice A, le intersezioni AB e AE sono impostate a 1 poiché c'è un bordo da A a B e da A a E. Allo stesso modo l'intersezione BA è impostata a 1, poiché questo è un non orientato grafico e AB = BA. Allo stesso modo, abbiamo impostato tutte le altre intersezioni per le quali esiste un bordo a 1.
Nel caso in cui il grafico sia diretto, l'intersezione Mijsarà impostato a 1 solo se c'è un bordo chiaro diretto da Vi a Vj.
Ciò è mostrato nell'illustrazione seguente.
Come possiamo vedere dal diagramma sopra, c'è un bordo da A a B. Quindi l'intersezione AB è impostata a 1 ma l'intersezione BA è impostata a 0. Questo perché non c'è un bordo diretto da B ad A.
Considera i vertici E e D. Vediamo che ci sono archi da E a D così come da D a E. Quindi abbiamo impostato entrambe queste intersezioni a 1 in Matrice di adiacenza.
Passiamo ora ai grafici ponderati. Come sappiamo per il grafico ponderato, ad ogni bordo è associato un numero intero noto anche come peso. Rappresentiamo questo peso nella matrice di adiacenza per il bordo esistente. Questo peso viene specificato ogni volta che è presente un bordo da un vertice a un altro invece di '1'.
Questa rappresentazione è mostrata di seguito.
Elenco di adiacenza
Invece di rappresentare un grafico come una matrice di adiacenza di natura sequenziale, possiamo anche usare la rappresentazione collegata. Questa rappresentazione collegata è nota come elenco di adiacenza. Un elenco di adiacenza non è altro che un elenco collegato e ogni nodo nell'elenco rappresenta un vertice.
La presenza di un bordo tra due vertici è indicata da un puntatore dal primo al secondo vertice. Questo elenco di adiacenze viene mantenuto per ogni vertice nel grafico.
Quando abbiamo attraversato tutti i nodi adiacenti per un particolare nodo, memorizziamo NULL nel campo puntatore successivo dell'ultimo nodo della lista di adiacenza.
Ora useremo i grafici sopra che abbiamo usato per rappresentare la matrice di adiacenza per dimostrare l'elenco di adiacenza.
La figura sopra mostra l'elenco di adiacenza per il grafico non orientato. Vediamo che ogni vertice o nodo ha la sua lista di adiacenza.
Nel caso del grafo non orientato, le lunghezze totali delle liste di adiacenza sono solitamente il doppio del numero di archi. Nel grafico sopra, il numero totale di archi è 6 e il totale o la somma della lunghezza di tutta la lista di adiacenza è 12.
Ora prepariamo un elenco di adiacenza per il grafico diretto.
Come si vede dalla figura sopra, nel grafico orientato la lunghezza totale delle liste di adiacenza del grafico è uguale al numero di archi nel grafico. Nel grafico sopra, ci sono 9 archi e la somma delle lunghezze delle liste di adiacenza per questo grafico = 9.
Consideriamo ora il seguente grafico orientato ponderato. Notare che ogni bordo del grafico ponderato ha un peso associato ad esso. Quindi, quando rappresentiamo questo grafico con la lista di adiacenza, dobbiamo aggiungere un nuovo campo a ciascun nodo della lista che denoterà il peso del bordo.
Di seguito è riportato l'elenco delle adiacenze per il grafico ponderato.
Il diagramma sopra mostra il grafico ponderato e il suo elenco di adiacenza. Nota che c'è un nuovo spazio nell'elenco delle adiacenze che denota il peso di ogni nodo.
Implementazione del grafico in Java
Il seguente programma mostra l'implementazione di un grafico in Java. Qui abbiamo usato l'elenco di adiacenza per rappresentare il grafico.
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 Produzione:
Graph Traversal Java
Per eseguire qualsiasi azione significativa come la ricerca della presenza di dati, è necessario attraversare il grafico in modo tale che ogni vertice e il bordo del grafico vengano visitati almeno una volta. Questo viene fatto utilizzando algoritmi di grafi che non sono altro che un insieme di istruzioni che ci aiutano ad attraversare il grafico.
Esistono due algoritmi supportati per attraversare il grafico in Java .
- Prima traversata in profondità
- Attraversamento in larghezza
Prima traversata in profondità
La ricerca in profondità (DFS) è una tecnica utilizzata per attraversare un albero o un grafico. La tecnica DFS inizia con un nodo radice e quindi attraversa i nodi adiacenti del nodo radice andando più in profondità nel grafico. Nella tecnica DFS, i nodi vengono attraversati in profondità finché non ci sono più figli da esplorare.
Una volta raggiunto il nodo foglia (non più nodi figlio), il DFS esegue il backtrack e inizia con altri nodi ed esegue l'attraversamento in modo simile. La tecnica DFS utilizza una struttura di dati dello stack per archiviare i nodi che vengono attraversati.
Di seguito è riportato l'algoritmo per la tecnica DFS.
Algoritmo
Passaggio 1: inizia con il nodo radice e inseriscilo nello stack
Passaggio 2: estrai l'elemento dalla pila e inseriscilo nell'elenco 'visitato'
Passaggio 3: per il nodo contrassegnato come 'visitato' (o nell'elenco dei visitati), aggiungi i nodi adiacenti di questo nodo che non sono ancora contrassegnati come visitati, allo stack.
Passaggio 4: ripetere i passaggi 2 e 3 finché lo stack non è vuoto.
Illustrazione Della Tecnica DFS
Ora illustreremo la tecnica DFS utilizzando un esempio appropriato di grafico.
Di seguito è riportato un grafico di esempio. Manteniamo lo stack per memorizzare i nodi esplorati e un elenco per memorizzare i nodi visitati.
Inizieremo con A, contrassegnarlo come visitato e aggiungerlo all'elenco dei visitati. Quindi prenderemo in considerazione tutti i nodi adiacenti di A e li inseriremo nello stack come mostrato di seguito.
Successivamente, estraiamo un nodo dallo stack, ad esempio B, e lo contrassegniamo come visitato. Lo aggiungiamo quindi all'elenco dei 'visitati'. Questo è rappresentato di seguito.
Consideriamo ora i nodi adiacenti di B che sono A e C. Di questo A è già visitato. Quindi lo ignoriamo. Successivamente, estraiamo C dallo stack. Segna C come visitato. Il nodo adiacente di C cioè E viene aggiunto alla pila.
Successivamente, estraiamo il nodo successivo E dallo stack e lo contrassegniamo come visitato. Il nodo adiacente del nodo E è C già visitato. Quindi lo ignoriamo.
Ora solo il nodo D rimane nello stack. Quindi lo contrassegniamo come visitato. Il suo nodo adiacente è A che è già visitato. Quindi non lo aggiungiamo allo stack.
A questo punto la pila è vuota. Ciò significa che abbiamo completato il primo attraversamento in profondità per il grafico dato.
L'elenco dei visitati fornisce la sequenza finale di attraversamento utilizzando la tecnica della profondità iniziale. La sequenza DFS finale per il grafico sopra è A-> B-> C-> E-> D.
Implementazione di 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 Produzione:
Applicazioni di DFS
# 1) Rileva un ciclo in un grafico: DFS facilita il rilevamento di un ciclo in un grafico quando possiamo tornare indietro a un bordo.
# 2) Pathfinding: Come abbiamo già visto nell'illustrazione DFS, dati due vertici qualsiasi possiamo trovare il percorso tra questi due vertici.
# 3) Minimo spanning tree e percorso più breve: Se eseguiamo la tecnica DFS sul grafo non pesato, ci fornisce l'albero di copertura minimo e il percorso in corto.
# 4) Ordinamento topologico: L'ordinamento topologico viene utilizzato quando dobbiamo pianificare i lavori. Abbiamo dipendenze tra vari lavori. Possiamo anche utilizzare l'ordinamento topologico per risolvere le dipendenze tra linker, scheduler di istruzioni, serializzazione dei dati, ecc.
Traversata in larghezza
La tecnica Breadth-first (BFS) utilizza una coda per memorizzare i nodi del grafico. A differenza della tecnica DFS, in BFS attraversiamo il grafico in larghezza. Ciò significa che attraversiamo il livello del grafico in modo saggio. Quando esploriamo tutti i vertici o nodi a un livello, procediamo al livello successivo.
Di seguito è riportato un algoritmo per la tecnica di attraversamento in ampiezza .
domande e risposte dell'intervista tecnica per analisti aziendali
Algoritmo
Vediamo l'algoritmo per la tecnica BFS.
Dato un grafo G per il quale dobbiamo eseguire la tecnica BFS.
- Passo 1: Inizia con il nodo radice e inseriscilo nella coda.
- Passo 2: Ripetere i passaggi 3 e 4 per tutti i nodi nel grafico.
- Passaggio 3: Rimuovere il nodo radice dalla coda e aggiungerlo all'elenco Visitato.
- Passaggio 4: Ora aggiungi tutti i nodi adiacenti del nodo radice alla coda e ripeti i passaggi da 2 a 4 per ciascun nodo. (FINE LOOP)
- Passaggio 6: USCITA
Illustrazione Di BFS
Cerchiamo di illustrare la tecnica BFS utilizzando un grafico di esempio mostrato di seguito. Tieni presente che abbiamo mantenuto un elenco denominato 'Visitato' e una coda. Usiamo lo stesso grafico che abbiamo usato nell'esempio DFS per motivi di chiarezza.
Innanzitutto, iniziamo con la radice, ovvero il nodo A, e lo aggiungiamo all'elenco dei visitati. Tutti i nodi adiacenti del nodo A, cioè B, C e D, vengono aggiunti alla coda.
Successivamente, rimuoviamo il nodo B dalla coda. Lo aggiungiamo all'elenco Visitato e lo contrassegniamo come visitato. Successivamente, esploriamo i nodi adiacenti di B nella coda (C è già in coda). Un altro nodo adiacente A è già visitato, quindi lo ignoriamo.
Successivamente, rimuoviamo il nodo C dalla coda e lo contrassegniamo come visitato. Aggiungiamo C alla lista visitata e il suo nodo adiacente E viene aggiunto alla coda.
Successivamente, eliminiamo D dalla coda e lo contrassegniamo come visitato. Il nodo adiacente A del nodo D è già visitato, quindi lo ignoriamo.
Quindi ora solo il nodo E è in coda. Lo contrassegniamo come visitato e lo aggiungiamo all'elenco dei visitati. Il nodo adiacente di E è C già visitato. Quindi ignoralo.
A questo punto la coda è vuota e la lista visitata ha la sequenza che abbiamo ottenuto a seguito dell'attraversamento BFS. La sequenza è, A-> B-> C-> D-> E.
Implementazione di BFS
Il seguente programma Java mostra l'implementazione della tecnica 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 Produzione:
Applicazioni di BFS Traversal
# 1) Raccolta dei rifiuti: Uno degli algoritmi utilizzati dalla tecnica della garbage collection per copiare la garbage collection è 'l'algoritmo di Cheney'. Questo algoritmo utilizza una tecnica di attraversamento in ampiezza.
# 2) Trasmissione in rete: La trasmissione di pacchetti da un punto a un altro in una rete viene eseguita utilizzando la tecnica BFS.
# 3) Navigazione GPS: Possiamo utilizzare la tecnica BFS per trovare nodi adiacenti durante la navigazione tramite GPS.
# 4) Siti di social networking: La tecnica BFS viene utilizzata anche nei siti Web di social networking per trovare la rete di persone che circondano una determinata persona.
# 5) Percorso più breve e albero di copertura minimo nel grafico non ponderato: Nel grafico non ponderato, la tecnica BFS può essere utilizzata per trovare uno spanning tree minimo e il percorso più breve tra i nodi.
Libreria Java Graph
Java non rende obbligatorio per i programmatori implementare sempre i grafici nel programma. Java fornisce molte librerie pronte che possono essere utilizzate direttamente per utilizzare i grafici nel programma. Queste librerie dispongono di tutte le funzionalità API del grafico necessarie per sfruttare appieno il grafico e le sue varie funzionalità.
Di seguito è riportata una breve introduzione ad alcune delle librerie grafiche in Java.
# 1) Google Guava: Google Guava fornisce una ricca libreria che supporta grafici e algoritmi inclusi semplici grafici, reti, grafici di valori, ecc.
# 2) Apache Commons: Apache Commons è un progetto Apache che fornisce componenti della struttura dati Graph e API che hanno algoritmi che operano su questa struttura dati Graph. Questi componenti sono riutilizzabili.
# 3) JGraphT: JGraphT è una delle librerie grafiche Java ampiamente utilizzate. Fornisce la funzionalità della struttura dei dati del grafico contenente un grafico semplice, un grafico diretto, un grafico pesato, ecc., Nonché algoritmi e API che funzionano sulla struttura dei dati del grafico.
# 4) FonteForge JUNG: JUNG sta per 'Java Universal Network / Graph' ed è un framework Java. JUNG fornisce un linguaggio estensibile per l'analisi, la visualizzazione e la modellazione dei dati che vogliamo siano rappresentati come un grafico.
JUNG fornisce anche vari algoritmi e routine per la scomposizione, il clustering, l'ottimizzazione, ecc.
Domande frequenti
D # 1) Che cos'è un grafico in Java?
Risposta: Una struttura dati a grafo memorizza principalmente i dati connessi, per esempio, una rete di persone o una rete di città. Una struttura dati a grafo consiste in genere di nodi o punti chiamati vertici. Ogni vertice è connesso a un altro vertice utilizzando collegamenti chiamati bordi.
Q # 2) Quali sono i tipi di grafici?
Risposta: Di seguito sono elencati diversi tipi di grafici.
- Grafico a linee: Un grafico a linee viene utilizzato per tracciare le modifiche in una particolare proprietà rispetto al tempo.
- Istogramma: I grafici a barre confrontano i valori numerici di entità come la popolazione in varie città, le percentuali di alfabetizzazione in tutto il paese, ecc.
Oltre a questi tipi principali, abbiamo anche altri tipi come pittogramma, istogramma, grafico ad area, grafico a dispersione, ecc.
D # 3) Cos'è un grafico connesso?
Risposta: Un grafo connesso è un grafo in cui ogni vertice è connesso a un altro vertice. Quindi, nel grafo connesso, possiamo arrivare a ogni vertice da ogni altro vertice.
Q # 4) Quali sono le applicazioni del grafico?
qual è il miglior convertitore video
Risposta: I grafici vengono utilizzati in una varietà di applicazioni. Il grafico può essere utilizzato per rappresentare una rete complessa. I grafici vengono utilizzati anche nelle applicazioni di social networking per indicare la rete di persone e per applicazioni come la ricerca di persone o connessioni adiacenti.
I grafici sono usati per denotare il flusso di calcolo nell'informatica.
Q # 5) Come si memorizza un grafico?
Risposta: Esistono tre modi per memorizzare un grafico in memoria:
# 1) Possiamo memorizzare nodi o vertici come oggetti e bordi come puntatori.
#Due) Possiamo anche memorizzare grafici come matrici di adiacenza le cui righe e colonne sono uguali al numero di vertici. L'intersezione di ogni riga e colonna indica la presenza o l'assenza di un bordo. Nel grafico non ponderato la presenza di un bordo è indicata con 1 mentre nel grafico ponderato è sostituita dal peso del bordo.
# 3) L'ultimo approccio per memorizzare un grafo consiste nell'usare un elenco di adiacenze di archi tra i vertici oi nodi del grafo. Ogni nodo o vertice ha il suo elenco di adiacenze.
Conclusione
In questo tutorial, abbiamo discusso in dettaglio i grafici in Java. Abbiamo esplorato i vari tipi di grafici, implementazione di grafici e tecniche di attraversamento. I grafici possono essere utilizzati per trovare il percorso più breve tra i nodi.
Nei nostri prossimi tutorial, continueremo a esplorare i grafici discutendo alcuni modi per trovare il percorso più breve.
=> Guarda qui la serie di formazione su Java semplice.
Lettura consigliata
- Tutorial Java Reflection con esempi
- Come implementare l'algoritmo di Dijkstra in Java
- Tutorial Java SWING: contenitore, componenti e gestione degli eventi
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
- TreeMap in Java - Tutorial con esempi di Java TreeMap
- Modificatori di accesso in Java - Tutorial con esempi
- Java String con String Buffer e String Builder Tutorial
- Tutorial sul metodo Java String contains () con esempi
