java graph tutorial how implement graph data structure
Den här omfattande Java-grafhandledningen förklarar detaljerad grafstruktur. Det inkluderar hur man skapar, implementerar, representerar och korsar grafer i Java:
En grafdatastruktur representerar huvudsakligen ett nätverk som ansluter olika punkter. Dessa punkter kallas som hörn och länkarna som förbinder dessa hörn kallas 'Kanter'. Så ett diagram g definieras som en uppsättning hörn V och kanter E som förbinder dessa hörn.
Grafer används oftast för att representera olika nätverk som datanätverk, sociala nätverk etc. De kan också användas för att representera olika beroenden i programvara eller arkitekturer. Dessa beroende grafer är mycket användbara för att analysera programvaran och ibland felsöka den.
=> Kontrollera ALLA Java-handledning här.
Vad du kommer att lära dig:
- Datastruktur för Java-graf
- Hur man skapar en graf?
- Grafimplementering i Java
- Java Graph Library
- Slutsats
Datastruktur för Java-graf
Nedan visas en graf med fem hörn {A, B, C, D, E} och kanter ges av {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Eftersom kanterna inte visar några riktningar kallas den här grafen för ”oriktad graf”.
Förutom den oriktade grafen som visas ovan finns det flera varianter av grafen i Java.
Låt oss diskutera dessa varianter i detalj.
Olika varianter av diagram
Följande är några av varianterna i diagrammet.
# 1) Riktad graf
En riktad graf eller digraph är en grafdatastruktur där kanterna har en specifik riktning. De härstammar från ett toppunkt och kulminerar till ett annat toppunkt.
Följande diagram visar exemplet på riktad graf.
I ovanstående diagram finns det en kant från toppunkt A till toppunkt B. Men observera att A till B inte är samma som B till A som i en riktad graf såvida det inte finns en kant som anges från B till A.
En riktad graf är cyklisk om det finns minst en väg som har sin första och sista topp som samma. I ovanstående diagram bildar en väg A-> B-> C-> D-> E-> A en riktad cykel eller cyklisk graf.
Omvänt är en riktad acyklisk graf en graf där det inte finns någon riktad cykel, dvs. det finns ingen väg som bildar en cykel.
# 2) Vägt diagram
I ett viktat diagram, en viktär associerad med varje kant i diagrammet. Vikten anger normalt avståndet mellan de två hörnpunkterna. Följande diagram visar det viktade diagrammet. Eftersom inga riktningar visas är detta den oriktade grafen.
Observera att ett viktat diagram kan riktas eller inte riktas.
Hur man skapar en graf?
Java tillhandahåller inte en fullständig implementering av grafdatastrukturen. Vi kan dock representera diagrammet programmatiskt med hjälp av samlingar i Java. Vi kan också implementera en graf med dynamiska matriser som vektorer.
Vanligtvis implementerar vi grafer i Java med HashMap-samlingen. HashMap-element är i form av nyckel-värdepar. Vi kan representera listan för diagramadapter i en HashMap.
Ett vanligt sätt att skapa en graf är att använda en av representationerna av grafer som angränsningsmatris eller angränsningslista. Vi kommer att diskutera dessa representationer nästa och sedan implementera diagrammet i Java med hjälp av den angränsningslista som vi kommer att använda ArrayList för.
Diagramrepresentation i Java
Grafrepresentation avser tillvägagångssättet eller tekniken där grafdata lagras i datorns minne.
Vi har två huvudrepresentationer av diagram som visas nedan.
Adjacency matris
Adjacency Matrix är en linjär representation av grafer. Denna matris lagrar kartläggningen av kurvor och kanter i diagrammet. I angränsningsmatrisen representerar kurvorna i diagrammet rader och kolumner. Detta betyder att om diagrammet har N-hörn, kommer angränsningsmatrisen att ha storleken NxN.
Om V är en uppsättning vertikaler i diagrammet så korsar MI ji angränsningslistan = 1 betyder att det finns en kant mellan hörn i och j.
För att bättre förstå detta koncept tydligt, låt oss förbereda en angränsande matris för en oriktad graf.
Som framgår av ovanstående diagram ser vi att för toppunkt A är korsningarna AB och AE inställda på 1 eftersom det finns en kant från A till B och A till E. På samma sätt är korsningen BA inställd på 1, eftersom detta är en oriktad graf och AB = BA. På samma sätt har vi satt alla andra korsningar där det finns en kant till 1.
Om grafen är riktad, kommer korsningen MI jsätts till 1 endast om det finns en tydlig kant som riktas från Vi till Vj.
Detta visas i följande illustration.
Visual Studio Team Foundation Server 2015-handledning
Som vi kan se från ovanstående diagram finns det en kant från A till B. Så korsningen AB är satt till 1 men korsningen BA är inställd på 0. Detta beror på att det inte finns någon kant riktad från B till A.
Tänk på hörn E och D. Vi ser att det finns kanter från E till D såväl som D till E. Vi har därför satt båda dessa korsningar till 1 i angränsande matris.
Nu går vi vidare till viktade diagram. Som vi vet för det viktade diagrammet är ett heltal som också kallas vikt associerat med varje kant. Vi representerar denna vikt i angränsningsmatrisen för den kant som finns. Denna vikt anges när det finns en kant från ett toppunkt till ett annat istället för '1'.
Denna representation visas nedan.
Adjacency List
Istället för att representera en graf som en angränsningsmatris som är sekventiell till sin natur kan vi också använda länkad representation. Denna länkade representation kallas angränsningslistan. En angränsningslista är inget annat än en länkad lista och varje nod i listan representerar ett toppunkt.
Närvaron av en kant mellan två hörn anges med en pekare från det första toppunktet till det andra. Denna angränsningslista bibehålls för varje toppunkt i diagrammet.
När vi har korsat alla intilliggande noder för en viss nod lagrar vi NULL i nästa pekfält i den sista noden i angränsningslistan.
Nu kommer vi att använda ovanstående diagram som vi använde för att representera angränsningsmatrisen för att visa angränsningslistan.
Ovanstående figur visar angränsningslistan för den icke-riktade grafen. Vi ser att varje toppunkt eller nod har sin angränsningslista.
När det gäller den icke-riktade grafen är de totala längderna på angränsningslistor vanligtvis dubbelt så många kanter. I ovanstående diagram är det totala antalet kanter 6 och summan eller summan av längden på hela angränsningslistan är 12.
Låt oss nu förbereda en närliggande lista för den riktade grafen.
Som framgår av figuren ovan är den totala längden på angränsningslistorna i diagrammet i det riktade diagrammet lika med antalet kanter i diagrammet. I ovanstående diagram finns det nio kanter och summan av längderna på angränsningslistor för denna graf = 9.
Låt oss nu överväga följande viktade riktade diagram. Observera att varje kant i det viktade diagrammet har en vikt associerad med sig. Så när vi representerar den här grafen med angränsningslistan måste vi lägga till ett nytt fält i varje listnod som kommer att beteckna vikten på kanten.
Nära till listan för det viktade diagrammet visas nedan.
Ovanstående diagram visar det viktade diagrammet och dess angränsningslista. Observera att det finns ett nytt mellanslag i angränsningslistan som anger vikten på varje nod.
Grafimplementering i Java
Följande program visar implementeringen av en graf i Java. Här har vi använt angränsningslistan för att representera grafen.
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 Produktion:
Graph Traversal Java
För att utföra någon meningsfull åtgärd som att söka efter närvaron av data måste vi korsa diagrammet så att varje toppunkt och kanten på diagrammet besöks minst en gång. Detta görs med hjälp av grafalgoritmer som bara är en uppsättning instruktioner som hjälper oss att korsa diagrammet.
Det finns två algoritmer som stöds för att korsa grafen i Java .
- Djup-första genomgång
- Bredd-första genomgång
Djup-första genomgång
Djup-första sökning (DFS) är en teknik som används för att korsa ett träd eller ett diagram. DFS-tekniken börjar med en rotnod och passerar sedan rotnodens intilliggande noder genom att gå djupare in i diagrammet. I DFS-tekniken korsas noderna djupt tills det inte finns fler barn att utforska.
När vi väl har kommit till bladnoden (inga fler barnnoder) spårar DFS tillbaka och börjar med andra noder och utför genomkörning på liknande sätt. DFS-teknik använder en stapeldatastruktur för att lagra de noder som passeras.
Nedan följer algoritmen för DFS-tekniken.
Algoritm
Steg 1: Börja med rotnoden och sätt in den i stacken
Steg 2: Popa objektet från stapeln och sätt in det i 'besökt' -listan
Steg 3: För nod markerad som 'besökt' (eller i besökt lista), lägg till angränsande noder för denna nod som ännu inte är markerade besökta, till stacken.
Steg 4: Upprepa steg 2 och 3 tills stacken är tom.
Illustration av DFS-teknik
Nu kommer vi att illustrera DFS-tekniken med ett korrekt exempel på en graf.
Nedan följer ett exempeldiagram. Vi har stack för att lagra utforskade noder och en lista för att lagra besökta noder.
Vi börjar med A till att börja med, markerar det som besökt och lägger till det i den besökta listan. Sedan kommer vi att överväga alla intilliggande noder av A och trycka dessa noder på stapeln som visas nedan.
Därefter poppar vi en nod från stacken, dvs. B och markerar den som besökt. Vi lägger sedan till den i listan med 'besökta'. Detta visas nedan.
Nu betraktar vi de intilliggande noderna av B som är A och C. Av detta har A redan besökt. Så vi ignorerar det. Därefter poppar vi C från stacken. Markera C som besökt. Den intilliggande noden på C, dvs E, läggs till stapeln.
automatiserat testverktyg för webbapplikationer
Därefter poppar vi nästa nod E från stacken och markerar den som besökt. Nod E: s intilliggande nod är C som redan har besökts. Så vi ignorerar det.
Nu är bara nod D kvar i stacken. Så vi markerar det som besökt. Dess angränsande nod är A som redan har besökts. Så vi lägger inte till den i stacken.
Vid denna tidpunkt är stacken tom. Det betyder att vi har slutfört djup-första genomgången för den angivna grafen.
Den besökta listan ger den slutliga sekvensen av traversal med hjälp av den första djuptekniken. Den slutliga DFS-sekvensen för ovanstående graf är A-> B-> C-> E-> D.
DFS-implementering
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 Produktion:
Tillämpningar av DFS
# 1) Upptäck en cykel i ett diagram: DFS underlättar att upptäcka en cykel i en graf när vi kan gå tillbaka till en kant.
# 2) Pathfinding: Som vi redan har sett i DFS-illustrationen, med tanke på två hörn, kan vi hitta vägen mellan dessa två hörn.
# 3) Minimum spännande träd och kortaste väg: Om vi kör DFS-tekniken på den icke-viktade grafen ger det oss det minsta spännande trädet och den kortslutna sökvägen.
# 4) Topologisk sortering: Topologisk sortering används när vi måste schemalägga jobben. Vi har beroenden mellan olika jobb. Vi kan också använda topologisk sortering för att lösa beroenden mellan länkar, instruktionsplanerare, dataserialisering etc.
Bredd-första genomgång
Breadth-first (BFS) -teknik använder en kö för att lagra noderna i diagrammet. I motsats till DFS-tekniken passerar vi i BFS grafen bredvid. Det betyder att vi korsar grafen nivåvis. När vi utforskar alla hörn eller noder på en nivå fortsätter vi till nästa nivå.
Nedan följer en algoritm för bredd-första traversal-tekniken .
Algoritm
Låt oss se algoritmen för BFS-tekniken.
Givet ett diagram G för vilket vi behöver utföra BFS-tekniken.
- Steg 1: Börja med rotnoden och sätt in den i kön.
- Steg 2: Upprepa steg 3 och 4 för alla noder i diagrammet.
- Steg 3: Ta bort rotnoden från kön och lägg till den i listan Besökta.
- Steg 4: Lägg nu till alla intilliggande noder i rotnoden i kön och upprepa steg 2 till 4 för varje nod. (SLUT AV LOOP)
- Steg 6: UTGÅNG
Illustration av BFS
Låt oss illustrera BFS-tekniken med hjälp av ett exempeldiagram som visas nedan. Observera att vi har upprätthållit en lista med namnet 'Besökt' och en kö. Vi använder samma graf som vi använde i DFS-exemplet för tydlighetsändamål.
Först börjar vi med root dvs. nod A och lägger till den i den besökta listan. Alla intilliggande noder i noden A, dvs B, C och D läggs till i kön.
Därefter tar vi bort nod B från kön. Vi lägger till den i listan Besökta och markerar den som besökt. Därefter utforskar vi de intilliggande noderna B i kön (C finns redan i kön). En annan intilliggande nod A är redan besökt så vi ignorerar den.
Därefter tar vi bort nod C från kön och markerar den som besökt. Vi lägger till C i den besökta listan och dess intilliggande nod E läggs till i kön.
Därefter tar vi bort D från kön och markerar den som besökt. Nod D: s intilliggande nod A är redan besökt, så vi ignorerar den.
Så nu är bara nod E i kön. Vi markerar det som besökt och lägger till det i den besökta listan. Den angränsande noden till E är C som redan har besökts. Så ignorera det.
Vid den här tiden är kön tom och den besökta listan har den sekvens vi fick som ett resultat av BFS-traversal. Sekvensen är A-> B-> C-> D-> E.
BFS-implementering
Följande Java-program visar implementeringen av BFS-tekniken.
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 Produktion:
Tillämpningar av BFS Traversal
# 1) Insamling av sopor: En av algoritmerna som används av skräpsamlingstekniken för att kopiera skräpsamlingen är 'Cheneys algoritm'. Denna algoritm använder en bredd-första traversal teknik.
# 2) Sändning i nätverk: Sändning av paket från en punkt till en annan i ett nätverk görs med hjälp av BFS-tekniken.
# 3) GPS-navigering: Vi kan använda BFS-tekniken för att hitta angränsande noder när vi navigerar med GPS.
# 4) Sociala nätverkswebbplatser: BFS-teknik används också på webbplatser för sociala nätverk för att hitta nätverket av människor som omger en viss person.
# 5) Kortaste väg och minsta spännande träd i ovägt diagram: I det oviktade diagrammet kan BFS-tekniken användas för att hitta ett minimalt spännande träd och den kortaste vägen mellan noderna.
Java Graph Library
Java gör det inte obligatoriskt för programmerare att alltid implementera graferna i programmet. Java erbjuder många färdiga bibliotek som kan användas direkt för att använda grafer i programmet. Dessa bibliotek har all graf API-funktionalitet som krävs för att utnyttja grafen och dess olika funktioner till fullo.
Nedan ges en kort introduktion till några av grafbiblioteken i Java.
# 1) Google Guava: Google Guava tillhandahåller ett rikt bibliotek som stöder grafer och algoritmer inklusive enkla grafer, nätverk, värdediagram etc.
# 2) Apache Commons: Apache Commons är ett Apache-projekt som tillhandahåller komponenter i diagramdata och API: er som har algoritmer som fungerar på denna grafdatastruktur. Dessa komponenter kan återanvändas.
# 3) JGraphT: JGraphT är ett av de allmänt använda Java-grafbiblioteken. Det tillhandahåller grafdatastrukturfunktionalitet som innehåller enkel graf, riktad graf, viktad graf, etc. samt algoritmer och API: er som arbetar med grafdatastrukturen.
# 4) SourceForge JUNG: JUNG står för “Java Universal Network / Graph” och är ett Java-ramverk. JUNG ger ett utdragbart språk för analys, visualisering och modellering av de data som vi vill ska representeras som ett diagram.
JUNG tillhandahåller också olika algoritmer och rutiner för sönderdelning, kluster, optimering etc.
Vanliga frågor
F # 1) Vad är en graf i Java?
Svar: En grafdatastruktur lagrar huvudsakligen ansluten data, till exempel, ett nätverk av människor eller ett nätverk av städer. En grafdatastruktur består vanligtvis av noder eller punkter som kallas vertices. Varje toppunkt är anslutet till ett annat toppunkt med hjälp av länkar som kallas kanter.
F # 2) Vilka är typerna av grafer?
Svar: Olika typer av grafer listas nedan.
- Linjediagram: Ett linjediagram används för att plotta ändringarna i en viss egenskap relativt tiden.
- Stapeldiagram: I stapeldiagram jämförs numeriska värden för enheter som befolkningen i olika städer, läskunnighetsprocent över hela landet etc.
Förutom dessa huvudtyper har vi också andra typer som piktogram, histogram, areagraf, spridningsdiagram etc.
F # 3) Vad är ett anslutet diagram?
Svar: Ett anslutet diagram är ett diagram där varje toppunkt är kopplat till ett annat toppunkt. Därför kan vi i det anslutna diagrammet komma till varje toppunkt från varje annat toppunkt.
F # 4) Vilka är tillämpningarna i diagrammet?
databasintervjufrågor och svar pdf
Svar: Grafer används i en mängd olika applikationer. Grafen kan användas för att representera ett komplext nätverk. Grafer används också i sociala nätverksapplikationer för att beteckna nätverk av människor såväl som för applikationer som att hitta angränsande personer eller anslutningar.
Grafer används för att beteckna dataflödet inom datavetenskap.
F # 5) Hur lagrar du ett diagram?
Svar: Det finns tre sätt att lagra en graf i minnet:
# 1) Vi kan lagra noder eller hörn som objekt och kanter som pekare.
#två) Vi kan också lagra grafer som angränsningsmatris vars rader och kolumner är samma som antalet hörn. Skärningspunkten för varje rad och kolumn anger närvaron eller frånvaron av en kant. I det icke-viktade diagrammet betecknas närvaron av en kant med 1 medan den i det viktade diagrammet ersätts med vikten på kanten.
# 3) Det sista tillvägagångssättet för att lagra en graf är att använda en angränsningslista över kanter mellan diagramhörn eller noder. Varje nod eller toppunkt har sin angränsningslista.
Slutsats
I denna handledning har vi diskuterat diagram i Java i detalj. Vi undersökte de olika typerna av grafer, grafimplementering och genomgångstekniker. Grafer kan användas för att hitta den kortaste vägen mellan noder.
I våra kommande handledning fortsätter vi att utforska diagram genom att diskutera några sätt att hitta den kortaste vägen.
=> Se upp den enkla Java-träningsserien här.
Rekommenderad läsning
- Java Reflection Tutorial med exempel
- Hur man implementerar Dijkstras algoritm i Java
- Java SWING-handledning: Container, komponenter och händelsehantering
- JAVA-handledning för nybörjare: 100+ praktiska Java-videohandledning
- TreeMap In Java - Handledning med Java TreeMap-exempel
- Åtkomstmodifierare i Java - Handledning med exempel
- Java String med String Buffer och String Builder Tutorial
- Java String innehåller () Metodhandledning med exempel
