java graph tutorial how implement graph data structure
Ten kompleksowy samouczek dotyczący grafów w języku Java szczegółowo wyjaśnia strukturę danych wykresów. Obejmuje to, jak tworzyć, wdrażać, przedstawiać i przeglądać wykresy w Javie:
Graficzna struktura danych przedstawia głównie sieć łączącą różne punkty. Punkty te nazywane są wierzchołkami, a połączenia łączące te wierzchołki nazywane są „krawędziami”. Zatem graf g definiuje się jako zbiór wierzchołków V i krawędzi E, które łączą te wierzchołki.
Wykresy są najczęściej używane do reprezentowania różnych sieci, takich jak sieci komputerowe, sieci społecznościowe itp. Mogą być również używane do reprezentowania różnych zależności w oprogramowaniu lub architekturach. Te wykresy zależności są bardzo przydatne do analizowania oprogramowania, a czasami także do debugowania go.
=> Sprawdź WSZYSTKIE samouczki Java tutaj.
Czego się nauczysz:
- Struktura danych grafu Java
- Jak stworzyć wykres?
- Implementacja wykresów w Javie
- Biblioteka grafów Java
- Wniosek
Struktura danych grafu Java
Poniżej przedstawiono wykres mający pięć wierzchołków {A, B, C, D, E} i krawędzie podane przez {{AB}, {AC}, {AD}, {BD}, {CE}, {ED}}. Ponieważ krawędzie nie pokazują żadnych kierunków, ten wykres jest znany jako „wykres nieukierunkowany”.
Oprócz przedstawionego powyżej wykresu pośredniego, istnieje kilka wariantów wykresu w Javie.
Omówmy szczegółowo te warianty.
Różne warianty wykresu
Poniżej przedstawiono niektóre warianty wykresu.
1) Wykres ukierunkowany
Wykres skierowany lub dwuznak to struktura danych wykresu, w której krawędzie mają określony kierunek. Pochodzą z jednego wierzchołka i kończą się w innym wierzchołku.
Poniższy diagram przedstawia przykład skierowanego wykresu.
Na powyższym schemacie istnieje krawędź od wierzchołka A do wierzchołka B. Należy jednak zauważyć, że A do B to nie to samo, co B do A, jak w grafie niekierunkowym, chyba że określono krawędź od B do A.
Graf skierowany jest cykliczny, jeśli istnieje co najmniej jedna ścieżka, której pierwszy i ostatni wierzchołek są takie same. Na powyższym schemacie ścieżka A-> B-> C-> D-> E-> A tworzy skierowany cykl lub cykliczny wykres.
Odwrotnie, skierowany graf acykliczny jest grafem, w którym nie ma ukierunkowanego cyklu, tj. Nie ma ścieżki, która tworzy cykl.
2) Wykres ważony
Na wykresie ważonym wagajest powiązany z każdą krawędzią wykresu. Waga zwykle wskazuje odległość między dwoma wierzchołkami. Poniższy diagram przedstawia wykres ważony. Ponieważ nie pokazano żadnych kierunków, jest to wykres nieukierunkowany.
Zwróć uwagę, że wykres ważony może być skierowany lub nieukierunkowany.
Jak stworzyć wykres?
Java nie zapewnia pełnej implementacji struktury danych wykresu. Jednak możemy programowo przedstawić wykres za pomocą kolekcji w Javie. Możemy również zaimplementować wykres za pomocą dynamicznych tablic, takich jak wektory.
Zazwyczaj implementujemy wykresy w Javie przy użyciu kolekcji HashMap. Elementy HashMap mają postać par klucz-wartość. Możemy przedstawić listę sąsiedztwa wykresów w HashMap.
Najczęstszym sposobem tworzenia wykresów jest użycie jednej z reprezentacji wykresów, takich jak macierz sąsiedztwa lub lista sąsiedztwa. Następnie omówimy te reprezentacje, a następnie zaimplementujemy wykres w Javie przy użyciu listy sąsiedztwa, dla której będziemy używać ArrayList.
Reprezentacja wykresu w języku Java
Reprezentacja graficzna oznacza podejście lub technikę, za pomocą której dane wykresu są przechowywane w pamięci komputera.
Mamy dwie główne reprezentacje wykresów, jak pokazano poniżej.
Macierz sąsiedztwa
Macierz sąsiedztwa to liniowa reprezentacja wykresów. Ta macierz przechowuje odwzorowanie wierzchołków i krawędzi wykresu. W macierzy sąsiedztwa wierzchołki wykresu reprezentują wiersze i kolumny. Oznacza to, że jeśli graf ma N wierzchołków, to macierz sąsiedztwa będzie miała rozmiar NxN.
Jeśli V jest zbiorem wierzchołków grafu, to przecięcie Mijna liście przylegania = 1 oznacza, że między wierzchołkami i i j istnieje krawędź.
Aby lepiej zrozumieć tę koncepcję, przygotujmy macierz sąsiedztwa dla wykresu nieukierunkowanego.
Jak widać na powyższym diagramie, widzimy, że dla wierzchołka A przecięcia AB i AE są ustawione na 1, ponieważ istnieje krawędź od A do B i od A do E.Podobnie przecięcie BA jest ustawione na 1, ponieważ jest to wykres i AB = BA. Podobnie wszystkie inne przecięcia, dla których istnieje krawędź, ustawiliśmy na 1.
W przypadku, gdy wykres jest skierowany, przecięcie Mijzostanie ustawiony na 1 tylko wtedy, gdy istnieje wyraźna krawędź skierowana z Vi do Vj.
Przedstawiono to na poniższej ilustracji.
Jak widać na powyższym diagramie, istnieje krawędź od A do B. Zatem przecięcie AB jest ustawione na 1, ale przecięcie BA jest ustawione na 0. Dzieje się tak, ponieważ nie ma krawędzi skierowanej z B do A.
Rozważmy wierzchołki E i D. Widzimy, że istnieją krawędzie od E do D oraz od D do E. Stąd oba te przecięcia ustawiliśmy na 1 w macierzy przylegania.
Teraz przechodzimy do wykresów ważonych. Jak wiemy w przypadku wykresu ważonego, z każdą krawędzią skojarzona jest liczba całkowita zwana również wagą. Reprezentujemy tę wagę w macierzy sąsiedztwa dla istniejącej krawędzi. Ta waga jest określana za każdym razem, gdy istnieje krawędź od jednego wierzchołka do drugiego zamiast „1”.
Ta reprezentacja jest pokazana poniżej.
Lista sąsiedztwa
Zamiast przedstawiać wykres jako macierz sąsiedztwa, która ma charakter sekwencyjny, możemy również użyć reprezentacji połączonej. Ta połączona reprezentacja jest nazywana listą sąsiedztwa. Lista sąsiedztwa to nic innego jak lista połączona, a każdy węzeł na liście reprezentuje wierzchołek.
Obecność krawędzi między dwoma wierzchołkami jest oznaczona wskaźnikiem od pierwszego do drugiego wierzchołka. Ta lista przylegania jest utrzymywana dla każdego wierzchołka na wykresie.
Kiedy przeszliśmy przez wszystkie sąsiednie węzły dla określonego węzła, przechowujemy NULL w następnym polu wskaźnika ostatniego węzła na liście przylegania.
Teraz użyjemy powyższych wykresów, których użyliśmy do przedstawienia macierzy sąsiedztwa, aby zademonstrować listę sąsiedztwa.
Powyższy rysunek przedstawia listę sąsiedztwa dla grafu niekierowanego. Widzimy, że każdy wierzchołek lub węzeł ma swoją listę przylegania.
W przypadku wykresu nieukierunkowanego łączne długości list przylegania są zwykle dwukrotnie większe od liczby krawędzi. Na powyższym wykresie całkowita liczba krawędzi wynosi 6, a całkowita lub suma długości wszystkich list przylegania wynosi 12.
Teraz przygotujmy listę sąsiedztwa dla skierowanego wykresu.
Jak widać na powyższym rysunku, na wykresie skierowanym całkowita długość list sąsiedztwa wykresu jest równa liczbie krawędzi na wykresie. Na powyższym wykresie istnieje 9 krawędzi i suma długości list sąsiedztwa dla tego wykresu = 9.
Rozważmy teraz następujący ważony wykres skierowany. Zwróć uwagę, że każda krawędź wykresu ważonego ma przypisaną wagę. Więc kiedy przedstawiamy ten wykres za pomocą listy sąsiedztwa, musimy dodać nowe pole do każdego węzła listy, które będzie oznaczać wagę krawędzi.
Lista sąsiedztwa dla wykresu ważonego jest pokazana poniżej.
Powyższy diagram przedstawia ważony wykres i listę jego sąsiedztwa. Zwróć uwagę, że na liście przylegania znajduje się nowa spacja, która oznacza wagę każdego węzła.
Implementacja wykresów w Javie
Poniższy program przedstawia implementację wykresu w Javie. Tutaj użyliśmy listy przylegania do przedstawienia wykresu.
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 Wynik:
Graph Traversal Java
Aby wykonać jakąkolwiek sensowną akcję, taką jak poszukiwanie obecności jakichkolwiek danych, musimy przejść przez wykres w taki sposób, aby każdy wierzchołek i krawędź wykresu były odwiedzane co najmniej raz. Odbywa się to za pomocą algorytmów grafowych, które są niczym innym jak zestawem instrukcji, które pomagają nam przejść przez wykres.
Obsługiwane są dwa algorytmy przechodzenia przez wykres w Javie .
- Przemierzanie w głąb
- Przejście wszerz
Trawersja w pierwszej głębokości
Przeszukiwanie w głąb (DFS) to technika używana do przechodzenia przez drzewo lub wykres. Technika DFS rozpoczyna się od węzła głównego, a następnie przechodzi przez sąsiednie węzły węzła głównego, wchodząc głębiej w wykres. W technice DFS, węzły są przemierzane w głąb, dopóki nie ma więcej dzieci do zbadania.
Gdy dotrzemy do węzła-liścia (nie ma już węzłów potomnych), DFS cofa się i zaczyna od innych węzłów i przeprowadza przemierzanie w podobny sposób. Technika DFS wykorzystuje strukturę danych stosu do przechowywania węzłów, przez które przechodzą.
Poniżej przedstawiono algorytm techniki DFS.
youtube video downloader na PC do pobrania za darmo
Algorytm
Krok 1: Zacznij od węzła głównego i włóż go do stosu
Krok 2: Zdejmij element ze stosu i umieść na liście „Odwiedzone”
Krok 3: W przypadku węzła oznaczonego jako „odwiedzony” (lub na liście odwiedzonych) dodaj do stosu sąsiednie węzły tego węzła, które nie są jeszcze oznaczone jako odwiedzone.
Krok 4: Powtarzaj kroki 2 i 3, aż stos będzie pusty.
Ilustracja Techniki DFS
Teraz zilustrujemy technikę DFS na odpowiednim przykładzie wykresu.
Poniżej przedstawiono przykładowy wykres. Utrzymujemy stos do przechowywania eksplorowanych węzłów i listę do przechowywania odwiedzonych węzłów.
Zaczniemy od A, oznaczymy jako odwiedzone i dodamy do listy odwiedzonych. Następnie rozważymy wszystkie sąsiednie węzły A i umieścimy te węzły na stosie, jak pokazano poniżej.
Następnie zdejmujemy węzeł ze stosu, czyli B i oznaczamy go jako odwiedzony. Następnie dodajemy go do listy „odwiedzonych”. Przedstawiono to poniżej.
Teraz rozważymy sąsiednie węzły B, które są A i C. Z tego A jest już odwiedzone. Więc ignorujemy to. Następnie usuwamy C ze stosu. Mark C jako odwiedzony. Sąsiedni węzeł C, czyli E jest dodawany do stosu.
Następnie zdejmujemy następny węzeł E ze stosu i oznaczamy go jako odwiedzony. Węzeł sąsiadujący z węzłem E to już odwiedzony węzeł C. Więc ignorujemy to.
Teraz na stosie pozostaje tylko węzeł D. Więc oznaczamy to jako odwiedzone. Jego sąsiedni węzeł to A, który jest już odwiedzony. Więc nie dodajemy go do stosu.
W tym momencie stos jest pusty. Oznacza to, że zakończyliśmy przemierzanie w pierwszej głębokości dla danego wykresu.
Lista odwiedzonych podaje końcową sekwencję przemierzania z użyciem techniki „najpierw w głąb”. Ostateczna sekwencja DFS dla powyższego wykresu to A-> B-> C-> E-> D.
Wdrożenie 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 Wynik:
Zastosowania DFS
# 1) Wykryj cykl na wykresie: DFS ułatwia wykrycie cyklu na wykresie, kiedy możemy cofnąć się do krawędzi.
# 2) Znajdowanie ścieżki: Jak już widzieliśmy na ilustracji DFS, biorąc pod uwagę dowolne dwa wierzchołki, możemy znaleźć ścieżkę między tymi dwoma wierzchołkami.
# 3) Minimum drzewo opinające i najkrótsza ścieżka: Jeśli uruchomimy technikę DFS na nieważonym wykresie, otrzymamy minimalne drzewo opinające i skróconą ścieżkę.
# 4) Sortowanie topologiczne: Sortowanie topologiczne jest używane, gdy musimy zaplanować zadania. Mamy zależności między różnymi zawodami. Możemy również użyć sortowania topologicznego do rozwiązywania zależności między linkerami, planistami instrukcji, serializacją danych itp.
Trawersa wszerz
Technika Breadth-First (BFS) wykorzystuje kolejkę do przechowywania węzłów wykresu. W przeciwieństwie do techniki DFS, w BFS przechodzimy przez wykres wszerz. Oznacza to, że przemierzamy poziom wykresu. Kiedy badamy wszystkie wierzchołki lub węzły na jednym poziomie, przechodzimy do następnego poziomu.
Poniżej podano algorytm dla techniki przechodzenia wszerz .
Algorytm
Zobaczmy algorytm techniki BFS.
Biorąc pod uwagę wykres G, dla którego musimy wykonać technikę BFS.
- Krok 1: Rozpocznij od węzła głównego i wstaw go do kolejki.
- Krok 2: Powtórz kroki 3 i 4 dla wszystkich węzłów na wykresie.
- Krok 3: Usuń węzeł główny z kolejki i dodaj go do listy Odwiedzonych.
- Krok 4: Teraz dodaj wszystkie sąsiednie węzły węzła głównego do kolejki i powtórz kroki od 2 do 4 dla każdego węzła. [END OF LOOP]
- Krok 6: WYJŚCIE
Ilustracja BFS
Zilustrujmy technikę BFS za pomocą przykładowego wykresu pokazanego poniżej. Pamiętaj, że utrzymaliśmy listę o nazwie „Odwiedzone” i kolejkę. Używamy tego samego wykresu, którego użyliśmy w przykładzie DFS dla celów przejrzystości.
Najpierw zaczynamy od roota, czyli węzła A i dodajemy go do listy odwiedzonych. Wszystkie sąsiednie węzły węzła A, tj. B, C i D, są dodawane do kolejki.
Następnie usuwamy węzeł B z kolejki. Dodajemy go do listy Odwiedzonych i oznaczamy jako odwiedzony. Następnie eksplorujemy sąsiednie węzły B w kolejce (C jest już w kolejce). Inny sąsiedni węzeł A jest już odwiedzony, więc go ignorujemy.
Następnie usuwamy węzeł C z kolejki i oznaczamy go jako odwiedzony. Dodajemy C do listy odwiedzonych, a sąsiedni węzeł E jest dodawany do kolejki.
jak korzystać z pliku torrent
Następnie usuwamy D z kolejki i oznaczamy jako odwiedzony. Sąsiedni węzeł A węzła D jest już odwiedzony, więc go ignorujemy.
Więc teraz tylko węzeł E jest w kolejce. Oznaczamy go jako odwiedzony i dodajemy do listy odwiedzonych. Sąsiednim węzłem E jest C, który jest już odwiedzony. Więc zignoruj to.
W tym momencie kolejka jest pusta, a odwiedzana lista zawiera sekwencję, którą uzyskaliśmy w wyniku przejścia BFS. Sekwencja to A-> B-> C-> D-> E.
Wdrożenie BFS
Poniższy program w języku Java przedstawia implementację techniki 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 Wynik:
Zastosowania BFS Traversal
# 1) Zbieranie śmieci: Jednym z algorytmów używanych przez technikę czyszczenia pamięci do kopiowania funkcji czyszczenia pamięci jest „algorytm Cheneya”. Ten algorytm wykorzystuje technikę przechodzenia wszerz.
# 2) Nadawanie w sieciach: Transmisja pakietów z jednego punktu do drugiego w sieci odbywa się za pomocą techniki BFS.
# 3) Nawigacja GPS: Możemy użyć techniki BFS, aby znaleźć sąsiednie węzły podczas nawigacji za pomocą GPS.
# 4) Serwisy społecznościowe: Technika BFS jest również używana w serwisach społecznościowych do wyszukiwania sieci osób otaczających daną osobę.
# 5) Najkrótsza ścieżka i minimalne drzewo rozpinające na wykresie nieważonym: Na wykresie nieważonym technikę BFS można wykorzystać do znalezienia minimalnego drzewa rozpinającego i najkrótszej ścieżki między węzłami.
Biblioteka grafów Java
Java nie nakłada na programistów obowiązku zawsze implementowania wykresów w programie. Java udostępnia wiele gotowych bibliotek, które można bezpośrednio wykorzystać do wykorzystania wykresów w programie. Te biblioteki mają wszystkie funkcje Graph API wymagane do pełnego wykorzystania wykresu i jego różnych funkcji.
Poniżej znajduje się krótkie wprowadzenie do niektórych bibliotek grafów w Javie.
1) Google Guava: Google Guava zapewnia bogatą bibliotekę obsługującą wykresy i algorytmy, w tym proste wykresy, sieci, wykresy wartości itp.
# 2) Apache Commons: Apache Commons to projekt Apache, który zapewnia komponenty struktury danych Graph i interfejsy API, które mają algorytmy działające na tej strukturze danych wykresu. Te komponenty są wielokrotnego użytku.
# 3) JGraphT: JGraphT jest jedną z powszechnie używanych bibliotek grafów Java. Zapewnia funkcjonalność struktury danych wykresu, zawierającą prosty wykres, wykres ukierunkowany, wykres ważony itp., A także algorytmy i interfejsy API działające na strukturze danych wykresu.
# 4) SourceForge JUNG: JUNG oznacza „Java Universal Network / Graph” i jest frameworkiem Java. JUNG zapewnia rozszerzalny język do analizy, wizualizacji i modelowania danych, które chcemy przedstawić w postaci wykresu.
JUNG zapewnia również różne algorytmy i procedury dekompozycji, grupowania, optymalizacji itp.
Często Zadawane Pytania
Pytanie 1) Co to jest wykres w Javie?
Odpowiedź: Graficzna struktura danych przechowuje głównie powiązane dane, na przykład, sieć ludzi lub sieć miast. Struktura danych wykresu zazwyczaj składa się z węzłów lub punktów zwanych wierzchołkami. Każdy wierzchołek jest połączony z innym wierzchołkiem za pomocą łączy zwanych krawędziami.
Pytanie nr 2) Jakie są rodzaje wykresów?
Odpowiedź: Poniżej wymieniono różne typy wykresów.
- Wykres liniowy: Wykres liniowy służy do wykreślania zmian określonej właściwości w czasie.
- Wykres słupkowy: Wykresy słupkowe porównują wartości liczbowe podmiotów, takich jak populacja w różnych miastach, odsetki umiejętności czytania i pisania w całym kraju itp.
Oprócz tych głównych typów mamy również inne typy, takie jak piktogram, histogram, wykres warstwowy, wykres punktowy itp.
P # 3) Co to jest połączony wykres?
Odpowiedź: Graf połączony to graf, w którym każdy wierzchołek jest połączony z innym wierzchołkiem. Stąd w połączonym grafie możemy dostać się do każdego wierzchołka z każdego innego wierzchołka.
Pytanie 4) Jakie są zastosowania wykresu?
Odpowiedź: Wykresy są używane w różnych zastosowaniach. Wykres może służyć do reprezentowania złożonej sieci. Wykresy są również używane w aplikacjach społecznościowych do oznaczania sieci osób, a także w aplikacjach takich jak znajdowanie sąsiadujących osób lub połączeń.
Wykresy służą do oznaczania przepływu obliczeń w informatyce.
Pytanie nr 5) Jak przechowujesz wykres?
Odpowiedź: Istnieją trzy sposoby przechowywania wykresu w pamięci:
# 1) Węzły lub wierzchołki możemy przechowywać jako obiekty, a krawędzie jako wskaźniki.
#dwa) Możemy również przechowywać wykresy jako macierz sąsiedztwa, której wiersze i kolumny są takie same jak liczba wierzchołków. Przecięcie każdego wiersza i kolumny oznacza obecność lub brak krawędzi. Na wykresie nieważonym obecność krawędzi jest oznaczana przez 1, podczas gdy na wykresie ważonym jest ona zastępowana przez wagę krawędzi.
# 3) Ostatnim podejściem do przechowywania wykresu jest użycie listy przylegania krawędzi między wierzchołkami lub węzłami grafu. Każdy węzeł lub wierzchołek ma swoją listę przylegania.
Wniosek
W tym samouczku szczegółowo omówiliśmy wykresy w Javie. Zbadaliśmy różne typy wykresów, implementację wykresów i techniki przechodzenia. Wykresy można wykorzystać do znalezienia najkrótszej ścieżki między węzłami.
W naszych nadchodzących samouczkach będziemy nadal badać wykresy, omawiając kilka sposobów znalezienia najkrótszej ścieżki.
=> Obejrzyj serię prostych szkoleń dotyczących języka Java.
rekomendowane lektury
- Samouczek dotyczący refleksji w języku Java z przykładami
- Jak zaimplementować algorytm Dijkstry w Javie
- Samouczek Java SWING: kontener, komponenty i obsługa zdarzeń
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
- TreeMap w Javie - samouczek z przykładami TreeMap w języku Java
- Modyfikatory dostępu w Javie - samouczek z przykładami
- Ciąg Java z buforem ciągów i samouczek dotyczący tworzenia ciągów
- Java String zawiera () Samouczek dotyczący metody z przykładami
