1. Przegląd
W tym samouczku zrozumiemy podstawowe pojęcia dotyczące wykresu jako struktury danych .
Zbadamy również jego implementację w Javie wraz z różnymi operacjami możliwymi na wykresie. Omówimy również biblioteki Java oferujące implementacje grafów.
2. Wykres struktury danych
Wykres to struktura danych służąca do przechowywania połączonych danych, podobnie jak sieć osób na platformie mediów społecznościowych.
Graf składa się z wierzchołków i krawędzi. Wierzchołek reprezentuje byt (na przykład ludzie), a krawędź reprezentuje relacje między bytami (na przykład przyjaźnie osoby).
Zdefiniujmy prosty wykres, aby lepiej to zrozumieć:
Tutaj zdefiniowaliśmy prosty wykres z pięcioma wierzchołkami i sześcioma krawędziami. Okręgi to wierzchołki przedstawiające ludzi, a linie łączące dwa wierzchołki to krawędzie przedstawiające znajomych na portalu internetowym.
Istnieje kilka odmian tego prostego wykresu w zależności od właściwości krawędzi. Przyjrzyjmy się im pokrótce w następnych sekcjach.
Skoncentrujemy się jednak tylko na prostym wykresie przedstawionym tutaj dla przykładów Java w tym samouczku.
2.1. Kierowany wykres
Wykres, który do tej pory zdefiniowaliśmy, ma krawędzie bez żadnego kierunku. Jeśli te krawędzie mają w sobie kierunek , wynikowy wykres nazywany jest wykresem skierowanym.
Przykładem może być przedstawienie, kto wysyła zaproszenie do znajomych w ramach przyjaźni na portalu internetowym:
Tutaj widzimy, że krawędzie mają ustalony kierunek. Krawędzie również mogą być dwukierunkowe.
2.2. Wykres ważony
Ponownie, nasz prosty wykres ma krawędzie, które są bezstronne lub nieważone. Jeśli zamiast tego te krawędzie mają względną wagę , ten wykres jest znany jako wykres ważony.
Przykładem praktycznego zastosowania tego może być przedstawienie, ile lat ma przyjaźń na portalu internetowym:
Tutaj widzimy, że krawędzie mają przypisane wagi. Zapewnia to względne znaczenie tym krawędziom.
3. Graficzne reprezentacje
Wykres można przedstawić w różnych formach, takich jak macierz sąsiedztwa i lista sąsiedztwa. Każdy z nich ma swoje wady i zalety w innej konfiguracji.
W tej sekcji przedstawimy te reprezentacje wykresów.
3.1. Macierz sąsiedztwa
Macierz sąsiedztwa to kwadratowa macierz o wymiarach odpowiadających liczbie wierzchołków na wykresie.
Elementy macierzy mają zazwyczaj wartości „0” lub „1”. Wartość „1” oznacza przyleganie wierzchołków w wierszu i kolumnie, a wartość „0” w przeciwnym razie.
Zobaczmy, jak wygląda macierz sąsiedztwa dla naszego prostego wykresu z poprzedniej sekcji:
Ta reprezentacja jest dość łatwiejsza do zaimplementowania i wydajna również w przypadku zapytań . Jest to jednak mniej wydajne w stosunku do zajmowanej przestrzeni .
3.2. Lista sąsiedztwa
Lista sąsiedztwa to nic innego jak tablica list . Rozmiar tablicy odpowiada liczbie wierzchołków na wykresie.
Lista pod określonym indeksem tablicy reprezentuje sąsiednie wierzchołki wierzchołka reprezentowanego przez ten indeks tablicy.
Zobaczmy, jak wygląda lista sąsiedztwa dla naszego prostego wykresu z poprzedniej sekcji:
Ta reprezentacja jest stosunkowo trudna do utworzenia i mniej wydajna w przypadku zapytań . Jednak zapewnia lepszą wydajność przestrzenną .
Użyjemy listy sąsiedztwa do przedstawienia wykresu w tym samouczku.
4. Wykresy w Javie
Java nie ma domyślnej implementacji struktury danych wykresu.
Możemy jednak zaimplementować wykres za pomocą kolekcji Java.
Zacznijmy od zdefiniowania wierzchołka:
class Vertex { String label; Vertex(String label) { this.label = label; } // equals and hashCode }Powyższa definicja wierzchołka zawiera tylko etykietę, ale może ona reprezentować dowolną możliwą jednostkę, taką jak osoba lub miasto.
Należy również zauważyć, że musimy przesłonić metody equals () i hashCode () , ponieważ są one niezbędne do pracy z kolekcjami Java.
Jak omówiliśmy wcześniej, graf to nic innego jak zbiór wierzchołków i krawędzi, które można przedstawić jako macierz sąsiedztwa lub listę sąsiedztwa.
Zobaczmy, jak możemy to zdefiniować, używając listy sąsiedztwa tutaj:
class Graph { private Map
adjVertices; // standard constructor, getters, setters }
Jak widać, klasa Graph używa Map from Java Collections do definiowania listy sąsiedztwa.
Na strukturze danych wykresu możliwych jest kilka operacji, takich jak tworzenie, aktualizacja lub przeszukiwanie wykresu .
Omówimy niektóre z bardziej typowych operacji i zobaczymy, jak możemy je zaimplementować w Javie.
5. Graph Mutation Operations
To start with, we'll define some methods to mutate the graph data structure.
Let's define methods to add and remove vertices:
void addVertex(String label) { adjVertices.putIfAbsent(new Vertex(label), new ArrayList()); } void removeVertex(String label) { Vertex v = new Vertex(label); adjVertices.values().stream().forEach(e -> e.remove(v)); adjVertices.remove(new Vertex(label)); }These methods simply add and remove elements from the vertices Set.
Now, let's also define a method to add an edge:
void addEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); adjVertices.get(v1).add(v2); adjVertices.get(v2).add(v1); }This method creates a new Edge and updates the adjacent vertices Map.
In a similar way, we'll define the removeEdge() method:
void removeEdge(String label1, String label2) { Vertex v1 = new Vertex(label1); Vertex v2 = new Vertex(label2); List eV1 = adjVertices.get(v1); List eV2 = adjVertices.get(v2); if (eV1 != null) eV1.remove(v2); if (eV2 != null) eV2.remove(v1); }Next, let's see how we can create the simple graph we have drawn earlier using the methods we've defined so far:
Graph createGraph() { Graph graph = new Graph(); graph.addVertex("Bob"); graph.addVertex("Alice"); graph.addVertex("Mark"); graph.addVertex("Rob"); graph.addVertex("Maria"); graph.addEdge("Bob", "Alice"); graph.addEdge("Bob", "Rob"); graph.addEdge("Alice", "Mark"); graph.addEdge("Rob", "Mark"); graph.addEdge("Alice", "Maria"); graph.addEdge("Rob", "Maria"); return graph; }We'll finally define a method to get the adjacent vertices of a particular vertex:
List getAdjVertices(String label) { return adjVertices.get(new Vertex(label)); }6. Traversing a Graph
Now that we have graph data structure and functions to create and update it defined, we can define some additional functions for traversing the graph. We need to traverse a graph to perform any meaningful action, like search within the graph.
There are two possible ways to traverse a graph, depth-first traversal and breadth-first traversal.
6.1. Depth-First Traversal
A depth-first traversal starts at an arbitrary root vertex and explores vertices as deeper as possible along each branch before exploring vertices at the same level.
Let's define a method to perform the depth-first traversal:
Set depthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Stack stack = new Stack(); stack.push(root); while (!stack.isEmpty()) { String vertex = stack.pop(); if (!visited.contains(vertex)) { visited.add(vertex); for (Vertex v : graph.getAdjVertices(vertex)) { stack.push(v.label); } } } return visited; }Here, we're using a Stack to store the vertices that need to be traversed.
Let's run this on the graph we created in the previous subsection:
assertEquals("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal(graph, "Bob").toString());Please note that we're using vertex “Bob” as our root for traversal here, but this can be any other vertex.
6.2. Breadth-First Traversal
Comparatively, a breadth-first traversal starts at an arbitrary root vertex and explores all neighboring vertices at the same level before going deeper in the graph.
Now let's define a method to perform the breadth-first traversal:
Set breadthFirstTraversal(Graph graph, String root) { Set visited = new LinkedHashSet(); Queue queue = new LinkedList(); queue.add(root); visited.add(root); while (!queue.isEmpty()) { String vertex = queue.poll(); for (Vertex v : graph.getAdjVertices(vertex)) { if (!visited.contains(v.label)) { visited.add(v.label); queue.add(v.label); } } } return visited; }Note that a breadth-first traversal makes use of Queue to store the vertices which need to be traversed.
Let's again run this traversal on the same graph:
assertEquals( "[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal(graph, "Bob").toString());Again, the root vertex which is “Bob” here can as well be any other vertex.
7. Java Libraries for Graphs
It's not necessary to always implement the graph from scratch in Java. There are several open source and mature libraries available which offers graph implementations.
In the next few subsections, we'll go through some of these libraries.
7.1. JGraphT
JGraphT is one of the most popular libraries in Java for the graph data structure. It allows the creation of a simple graph, directed graph, weighted graph, amongst others.
Additionally, it offers many possible algorithms on the graph data structure. One of our previous tutorials covers JGraphT in much more detail.
7.2. Google Guava
Google Guava is a set of Java libraries that offer a range of functions including graph data structure and its algorithms.
It supports creating simple Graph, ValueGraph, and Network. These can be defined as Mutable or Immutable.
7.3. Apache Commons
Apache Commons is an Apache project that offers reusable Java components. This includes Commons Graph which offers a toolkit to create and manage graph data structure. This also provides common graph algorithms to operate on the data structure.
7.4. Sourceforge JUNG
Java Universal Network/Graph (JUNG) is a Java framework that provides extensible language for modeling, analysis, and visualization of any data that can be represented as a graph.
JUNG supports a number of algorithms which includes routines like clustering, decomposition, and optimization.
Te biblioteki zapewniają szereg implementacji opartych na strukturze danych wykresu. Istnieją również potężniejsze frameworki oparte na grafach , takie jak Apache Giraph, obecnie używane na Facebooku do analizowania wykresów utworzonych przez ich użytkowników, oraz Apache TinkerPop, powszechnie używane w bazach danych grafów.
8. Wniosek
W tym artykule omówiliśmy wykres jako strukturę danych wraz z jej reprezentacjami. Zdefiniowaliśmy bardzo prosty wykres w Javie przy użyciu kolekcji Java, a także zdefiniowaliśmy typowe przejścia dla wykresu.
Rozmawialiśmy również krótko o różnych bibliotekach dostępnych w Javie poza platformą Java, która zapewnia implementacje grafów.
Jak zawsze, kod przykładów jest dostępny w serwisie GitHub.