java graph tutorial how implement graph data structure
Tento komplexní výukový program Java Graph podrobně vysvětluje datovou strukturu grafu. Zahrnuje, jak vytvářet, implementovat, reprezentovat a procházet grafy v Javě:
Datová struktura grafu představuje hlavně síť spojující různé body. Tyto body se nazývají vrcholy a odkazy spojující tyto vrcholy se nazývají „Hrany“. Takže graf g je definován jako množina vrcholů V a hran E, které tyto vrcholy spojují.
Grafy se většinou používají k reprezentaci různých sítí, jako jsou počítačové sítě, sociální sítě atd. Lze je také použít k reprezentaci různých závislostí v softwaru nebo architektuře. Tyto grafy závislostí jsou velmi užitečné při analýze softwaru a také při jeho ladění.
=> Zkontrolujte VŠECHNY výukové programy Java zde.
Co se naučíte:
Datová struktura grafu Java
Níže je uveden graf s pěti vrcholy {A, B, C, D, E} a hranami danými {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Protože hrany nevykazují žádné směry, je tento graf znám jako „neorientovaný graf“.
Kromě výše uvedeného neorientovaného grafu existuje v Java několik variant grafu.
Pojďme si tyto varianty podrobně promluvit.
Různé varianty grafu
Následuje několik variant grafu.
# 1) Směrovaný graf
Směrovaný graf nebo digraf je datová struktura grafu, ve které mají hrany určitý směr. Pocházejí z jednoho vrcholu a kulminují do jiného vrcholu.
Následující diagram ukazuje příklad směrovaného grafu.
Ve výše uvedeném diagramu je hrana od vrcholu A k vrcholu B. Všimněte si však, že A až B nejsou stejné jako B až A jako v neorientovaném grafu, pokud není hrana specifikována od B po A.
jak provést útok ddos na webu
Směrovaný graf je cyklický, pokud existuje alespoň jedna cesta, která má svůj první a poslední vrchol stejný. Ve výše uvedeném diagramu cesta A-> B-> C-> D-> E-> A tvoří směrovaný cyklus nebo cyklický graf.
Naopak, směrovaný acyklický graf je graf, ve kterém neexistuje žádný směrovaný cyklus, tj. Neexistuje žádná cesta, která tvoří cyklus.
# 2) Vážený graf
Ve váženém grafu váhaje spojena s každou hranou grafu. Hmotnost obvykle označuje vzdálenost mezi dvěma vrcholy. Následující diagram ukazuje vážený graf. Protože nejsou zobrazeny žádné směry, jedná se o neorientovaný graf.
Vážený graf může být směrovaný nebo neorientovaný.
Jak vytvořit graf?
Java neposkytuje plnohodnotnou implementaci datové struktury grafu. Můžeme však graf programově reprezentovat pomocí kolekcí v Javě. Můžeme také implementovat graf pomocí dynamických polí, jako jsou vektory.
Obvykle implementujeme grafy v Javě pomocí kolekce HashMap. Prvky HashMap jsou ve formě párů klíč – hodnota. Můžeme reprezentovat seznam sousedních grafů v HashMap.
Nejběžnějším způsobem vytvoření grafu je použití jedné z reprezentací grafů, jako je matice sousedství nebo seznam sousedů. Budeme diskutovat o těchto reprezentacích dále a poté implementujeme graf v Javě pomocí seznamu sousedství, pro který použijeme ArrayList.
Grafická reprezentace v Javě
Grafická reprezentace znamená přístup nebo techniku, pomocí které jsou data grafu ukládána do paměti počítače.
Máme dvě hlavní reprezentace grafů, jak je uvedeno níže.
Matice sousedství
Adjacency Matrix je lineární znázornění grafů. Tato matice ukládá mapování vrcholů a okrajů grafu. V matici sousedství představují vrcholy grafu řádky a sloupce. To znamená, že pokud má graf N vrcholů, pak matice sousedství bude mít velikost NxN.
Pokud V je množina vrcholů grafu, pak průsečík Mijv seznamu sousedů = 1 znamená, že mezi vrcholy i a j existuje hrana.
Pro lepší pochopení tohoto pojmu jasně připravme Matici sousedství pro neorientovaný graf.
Jak je patrné z výše uvedeného diagramu, vidíme, že pro vrchol A jsou průsečíky AB a AE nastaveny na 1, protože existuje hrana z A do B a A na E. Podobně je průsečík BA nastaven na 1, protože se jedná o nepřímý graf a AB = BA. Podobně jsme nastavili všechny ostatní křižovatky, pro které je hrana, na 1.
V případě, že je graf směrován, průsečík Mijbude nastavena na 1, pouze pokud bude z Vi do Vj směřovat jasná hrana.
To je znázorněno na následujícím obrázku.
Jak vidíme z výše uvedeného diagramu, existuje hrana od A do B. Průnik AB je tedy nastaven na 1, ale průsečík BA je nastaven na 0. Je to proto, že z B do A není směrována žádná hrana.
Vezměme si vrcholy E a D. Vidíme, že existují hrany od E do D i od D do E. Proto jsme oba tyto průsečíky nastavili na 1 v Matici sousednosti.
Nyní přejdeme k váženým grafům. Jak víme pro vážený graf, s každou hranou je spojeno celé číslo známé také jako váha. Tuto váhu představujeme v sousednosti Matrix pro existující hranu. Tato váha je specifikována vždy, když je místo „1“ hrana z jednoho vrcholu do druhého.
Toto znázornění je uvedeno níže.
Seznam sousedů
Místo toho, abychom graf reprezentovali jako matici sousednosti, která má sekvenční charakter, můžeme také použít propojenou reprezentaci. Tato propojená reprezentace se nazývá seznam sousedství. Seznam sousedství není nic jiného než propojený seznam a každý uzel v seznamu představuje vrchol.
Přítomnost hrany mezi dvěma vrcholy je označena ukazatelem z prvního vrcholu na druhý. Tento seznam sousedství je udržován pro každý vrchol v grafu.
Když jsme projeli všechny sousední uzly pro konkrétní uzel, uložíme NULL do pole dalšího ukazatele posledního uzlu seznamu sousedů.
Nyní použijeme výše uvedené grafy, které jsme použili k reprezentaci matice sousedství, abychom demonstrovali seznam sousedů.
Výše uvedený obrázek ukazuje seznam sousedství pro neorientovaný graf. Vidíme, že každý vrchol nebo uzel má svůj seznam sousedství.
V případě neorientovaného grafu jsou celkové délky seznamů sousedství obvykle dvojnásobkem počtu hran. Ve výše uvedeném grafu je celkový počet hran 6 a celková nebo součet délky celého seznamu sousedství je 12.
Nyní si připravíme seznam sousedství pro směrovaný graf.
Jak je patrné z výše uvedeného obrázku, v směrovaném grafu se celková délka seznamů sousedů grafu rovná počtu hran v grafu. Ve výše uvedeném grafu je 9 okrajů a součet délek seznamů sousedství pro tento graf = 9.
Nyní uvažujme následující vážený směrovaný graf. Všimněte si, že každá hrana váženého grafu má přidruženou váhu. Když tedy reprezentujeme tento graf se seznamem sousedství, musíme do každého uzlu seznamu přidat nové pole, které bude označovat váhu hrany.
Seznam sousedů pro vážený graf je uveden níže.
Výše uvedený diagram ukazuje vážený graf a jeho seznam sousedů. Všimněte si, že v seznamu sousedství je nový prostor, který označuje váhu každého uzlu.
Implementace grafů v Javě
Následující program ukazuje implementaci grafu v Javě. Zde jsme k zobrazení grafu použili seznam sousedství.
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ýstup:
Graf Traversal Java
Chcete-li provést jakoukoli smysluplnou akci, jako je hledání přítomnosti jakýchkoli dat, musíme graf projít tak, aby každý vrchol a jeho okraj byly alespoň jednou navštíveny. To se provádí pomocí grafových algoritmů, které nejsou ničím jiným než souborem pokynů, které nám pomáhají procházet grafem.
K procházení grafu v Javě jsou podporovány dva algoritmy .
- Průchod první hloubkou
- Procházka první šířkou
Procházka do hloubky
Hledání do hloubky (DFS) je technika, která se používá k procházení stromu nebo grafu. Technika DFS začíná kořenovým uzlem a poté prochází sousedními uzly kořenového uzlu hlouběji do grafu. V technice DFS jsou uzly procházeny hloubkově, dokud nejsou k dispozici další děti k prozkoumání.
Jakmile dosáhneme uzlu listu (žádné další podřízené uzly), DFS ustoupí a začne s ostatními uzly a provede průchod podobným způsobem. Technika DFS používá strukturu dat zásobníku k ukládání uzlů, které jsou procházeny.
Následuje algoritmus pro techniku DFS.
Algoritmus
Krok 1: Začněte s kořenovým uzlem a vložte jej do zásobníku
Krok 2: Vyjměte položku ze zásobníku a vložte ji do „navštíveného“ seznamu
Krok 3: U uzlu označeného jako „navštívený“ (nebo v seznamu navštívených) přidejte do zásobníku sousední uzly tohoto uzlu, které ještě nejsou označeny jako navštívené.
Krok 4: Opakujte kroky 2 a 3, dokud není zásobník prázdný.
Ilustrace techniky DFS
Nyní ilustrujeme techniku DFS na vhodném příkladu grafu.
Níže je uveden příklad grafu. Udržujeme zásobník pro uložení prozkoumaných uzlů a seznam pro uložení navštívených uzlů.
Začneme písmenem A, označíme jej jako navštívené a přidáme jej do seznamu navštívených. Potom zvážíme všechny sousední uzly A a zatlačíme tyto uzly do zásobníku, jak je znázorněno níže.
Dále vysuneme uzel ze zásobníku, tj. B a označíme jej jako navštívený. Poté jej přidáme do seznamu „navštívených“. Toto je znázorněno níže.
Nyní vezmeme v úvahu sousední uzly B, které jsou A a C. Z tohoto A je již navštíven. Takže to ignorujeme. Dále vysuneme C ze zásobníku. Označte C jako navštívené. Sousední uzel C, tj. E, je přidán do zásobníku.
Dále vysuneme další uzel E ze zásobníku a označíme jej jako navštívený. Sousedním uzlem E uzlu je C, které je již navštíveno. Takže to ignorujeme.
Nyní v zásobníku zůstane pouze uzel D. Takže to označíme jako navštívené. Jeho sousedním uzlem je A, který je již navštíven. Takže ho nepřidáváme do zásobníku.
V tomto okamžiku je zásobník prázdný. To znamená, že jsme pro daný graf dokončili průchod první hloubkou.
Navštívený seznam udává konečnou sekvenci procházení pomocí techniky hloubky první. Konečná sekvence DFS pro výše uvedený graf je A-> B-> C-> E-> D.
Implementace 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ýstup:
Aplikace DFS
# 1) Detekujte cyklus v grafu: DFS usnadňuje detekci cyklu v grafu, když se můžeme vrátit zpět k okraji.
# 2) Hledání cest: Jak jsme již viděli na ilustraci DFS, vzhledem k jakýmkoli dvěma vrcholům můžeme najít cestu mezi těmito dvěma vrcholy.
# 3) Minimum překlenující strom a nejkratší cesta: Pokud spustíme techniku DFS na neváženém grafu, dá nám to minimální kostru a zkrácenou cestu.
# 4) Topologické třídění: Topologické třídění se používá, když musíme naplánovat úlohy. Máme závislosti mezi různými pracemi. Můžeme také použít topologické třídění pro řešení závislostí mezi linkery, plánovači instrukcí, serializací dat atd.
Procházka první šíří
Technika šíře první (BFS) používá k uložení uzlů grafu frontu. Oproti technice DFS procházíme v BFS graf po šířce. To znamená, že procházíme grafem na úrovni. Když prozkoumáme všechny vrcholy nebo uzly na jedné úrovni, přejdeme na další úroveň.
Níže je uveden algoritmus pro techniku průchodu první šíře .
Algoritmus
Podívejme se na algoritmus pro techniku BFS.
Daný graf G, pro který musíme provést techniku BFS.
- Krok 1: Začněte kořenovým uzlem a vložte jej do fronty.
- Krok 2: Opakujte kroky 3 a 4 pro všechny uzly v grafu.
- Krok 3: Odeberte kořenový uzel z fronty a přidejte jej do seznamu Navštívené.
- Krok 4: Nyní přidejte všechny sousední uzly kořenového uzlu do fronty a opakujte kroky 2 až 4 pro každý uzel. (END OF LOOP)
- Krok 6: VÝSTUP
Ilustrace BFS
Pojďme si ilustrovat techniku BFS pomocí ukázkového grafu uvedeného níže. Upozorňujeme, že jsme udržovali seznam s názvem „Navštíveno“ a frontu. Pro přehlednost používáme stejný graf, který jsme použili v příkladu DFS.
Nejprve začneme kořenem, tj. Uzlem A a přidáme jej do navštíveného seznamu. Všechny sousední uzly uzlu A, tj. B, C a D, jsou přidány do fronty.
Dále odstraníme uzel B z fronty. Přidáme jej do seznamu Navštívené a označíme jej jako navštívený. Dále prozkoumáme sousední uzly B ve frontě (C je již ve frontě). Další sousední uzel A je již navštíven, takže ho ignorujeme.
Dále odstraníme uzel C z fronty a označíme jej jako navštívený. Přidáme C do navštíveného seznamu a jeho sousední uzel E se přidá do fronty.
Dále odstraníme D z fronty a označíme ji jako navštívenou. Sousední uzel A uzlu D je již navštíven, takže ho ignorujeme.
Takže nyní je ve frontě pouze uzel E. Označíme jej jako navštívený a přidáme jej do seznamu navštívených. Sousedním uzlem E je C, který je již navštíven. Tak to ignorujte.
V tomto okamžiku je fronta prázdná a navštívený seznam má sekvenci, kterou jsme získali v důsledku procházení BFS. Sekvence je A-> B-> C-> D-> E.
Implementace BFS
Následující program Java ukazuje implementaci 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ýstup:
Aplikace BFS Traversal
# 1) Sběr odpadu: Jedním z algoritmů používaných technikou sběru odpadků ke kopírování sběru odpadků je „Cheneyho algoritmus“. Tento algoritmus používá techniku šíření první šíře.
# 2) Vysílání v sítích: Vysílání paketů z jednoho bodu do druhého v síti se provádí technikou BFS.
# 3) GPS navigace: Můžeme použít techniku BFS k nalezení sousedních uzlů při navigaci pomocí GPS.
# 4) Weby sociálních sítí: Technika BFS se také používá na webových stránkách sociálních sítí k vyhledání sítě lidí obklopujících konkrétní osobu.
# 5) Nejkratší cesta a minimální kostra v neváženém grafu: V neváženém grafu lze techniku BFS použít k vyhledání minimálního překlenovacího stromu a nejkratší cesty mezi uzly.
Knihovna grafů Java
Java neukládá programátorům povinnost vždy grafy v programu implementovat. Java poskytuje mnoho připravených knihoven, které lze přímo použít k využití grafů v programu. Tyto knihovny mají všechny funkce API grafu potřebné k plnému využití grafu a jeho různých funkcí.
Níže je uveden stručný úvod k některým knihovnám grafů v Javě.
# 1) Google Guava: Google Guava poskytuje bohatou knihovnu, která podporuje grafy a algoritmy včetně jednoduchých grafů, sítí, hodnotových grafů atd.
# 2) Apache Commons: Apache Commons je projekt Apache, který poskytuje komponenty datové struktury Graph a API, které mají algoritmy, které fungují na této datové struktuře grafu. Tyto komponenty jsou opakovaně použitelné.
# 3) JGraphT: JGraphT je jednou z nejrozšířenějších knihoven grafů Java. Poskytuje funkčnost datové struktury grafu obsahující jednoduchý graf, směrovaný graf, vážený graf atd., Jakož i algoritmy a API, které fungují na datové struktuře grafu.
# 4) SourceForge JUNG: JUNG znamená „Java Universal Network / Graph“ a je to Java framework. JUNG poskytuje rozšiřitelný jazyk pro analýzu, vizualizaci a modelování dat, která chceme reprezentovat jako graf.
JUNG také poskytuje různé algoritmy a rutiny pro rozklad, shlukování, optimalizaci atd.
Často kladené otázky
Otázka č. 1) Co je to graf v Javě?
Odpovědět: Struktura dat grafu ukládá hlavně připojená data, například, síť lidí nebo síť měst. Datová struktura grafu se obvykle skládá z uzlů nebo bodů zvaných vrcholy. Každý vrchol je spojen s jiným vrcholem pomocí odkazů zvaných hrany.
Otázka č. 2) Jaké jsou typy grafů?
Odpovědět: Níže jsou uvedeny různé typy grafů.
- Hranový graf: Čárový graf se používá k vykreslení změn v konkrétní vlastnosti ve vztahu k času.
- Sloupcový graf: Sloupcové grafy porovnávají číselné hodnoty entit, jako je počet obyvatel v různých městech, procenta gramotnosti v celé zemi atd.
Kromě těchto hlavních typů máme také další typy, jako je piktogram, histogram, plošný graf, bodový graf atd.
Otázka č. 3) Co je to připojený graf?
Odpovědět: Připojený graf je graf, ve kterém je každý vrchol spojen s jiným vrcholem. V připojeném grafu se tedy můžeme dostat na každý vrchol ze všech ostatních vrcholů.
Otázka č. 4) Jaké jsou aplikace grafu?
Odpovědět: Grafy se používají v různých aplikacích. Graf lze použít k reprezentaci složité sítě. Grafy se také používají v aplikacích sociálních sítí k označení sítě lidí, stejně jako pro aplikace, jako je hledání sousedních osob nebo připojení.
Grafy se používají k označení toku výpočtu v informatice.
Otázka č. 5) Jak ukládáte graf?
Odpověď: Existují tři způsoby, jak uložit graf do paměti:
# 1) Můžeme ukládat uzly nebo vrcholy jako objekty a hrany jako ukazatele.
#dva) Můžeme také ukládat grafy jako matici sousedství, jejíž řádky a sloupce jsou stejné jako počet vrcholů. Průsečík každého řádku a sloupce označuje přítomnost nebo nepřítomnost hrany. V neváženém grafu je přítomnost hrany označena 1, zatímco ve váženém grafu je nahrazena váhou hrany.
# 3) Posledním přístupem k ukládání grafu je použití seznamu sousedních hran mezi vrcholy nebo uzly grafu. Každý uzel nebo vrchol má svůj seznam sousedství.
Závěr
V tomto tutoriálu jsme podrobně diskutovali grafy v Javě. Prozkoumali jsme různé typy grafů, implementaci grafů a techniky procházení. Při hledání nejkratší cesty mezi uzly lze použít grafy.
V našich nadcházejících výukových programech budeme pokračovat v prozkoumávání grafů tím, že budeme diskutovat o několika způsobech hledání nejkratší cesty.
=> Dávejte pozor na jednoduchou sérii školení Java zde.
Doporučené čtení
- Výukový program Java Reflection s příklady
- Jak implementovat Dijkstrův algoritmus v Javě
- Výukový program Java SWING: Kontejner, komponenty a zpracování událostí
- Výukový program JAVA pro začátečníky: 100+ praktických výukových programů Java Video
- TreeMap v Javě - výuka s příklady Java TreeMap
- Modifikátory přístupu v Javě - výuka s příklady
- Výukový program Java String s funkcí String Buffer a String Builder
- Java String obsahuje () Výukový program metod s příklady
