자바 그래프

1. 개요

이 튜토리얼에서는 그래프의 기본 개념을 데이터 구조로 이해합니다 .

또한 그래프에서 가능한 다양한 작업과 함께 Java로 구현하는 방법을 살펴 보겠습니다. 또한 그래프 구현을 제공하는 Java 라이브러리에 대해서도 설명합니다.

2. 그래프 데이터 구조

그래프는 소셜 미디어 플랫폼에서 사람들의 네트워크처럼 연결된 데이터를 저장하기위한 데이터 구조입니다 .

그래프는 꼭지점과 가장자리로 구성됩니다. 정점은 엔티티 (예 : 사람)를 나타내고 가장자리는 엔티티 간의 관계 (예 : 사람의 우정)를 나타냅니다.

이를 더 잘 이해하기 위해 간단한 그래프를 정의 해 보겠습니다.

여기에서 우리는 5 개의 꼭지점과 6 개의 모서리가있는 간단한 그래프를 정의했습니다. 원은 사람을 나타내는 정점이고 두 정점을 연결하는 선은 온라인 포털에서 친구를 나타내는 가장자리입니다.

간선의 속성에 따라이 간단한 그래프에는 몇 가지 변형이 있습니다. 다음 섹션에서 간단히 살펴 보겠습니다.

그러나이 튜토리얼의 Java 예제에 대해 여기에 제시된 간단한 그래프에만 초점을 맞출 것입니다.

2.1. 유향 그래프

지금까지 정의한 그래프에는 방향이없는 가장자리가 있습니다. 이러한 간선에 방향이있는 경우 결과 그래프를 방향성 그래프라고합니다.

예를 들어 온라인 포털에서 친구 요청을 보낸 사람을 나타낼 수 있습니다.

여기에서 모서리의 방향이 고정 된 것을 볼 수 있습니다. 가장자리는 양방향 일 수도 있습니다.

2.2. 가중 그래프

다시 말하지만, 간단한 그래프에는 편향되지 않거나 가중치가없는 간선이 있습니다. 대신 이러한 간선상대 가중치를 전달하는 경우이 그래프를 가중치 그래프라고합니다.

이것의 실제 적용의 예는 온라인 포털에서 우정이 얼마나 오래되었는지를 나타낼 수 있습니다.

여기에서 가장자리에 가중치가 연결되어 있음을 알 수 있습니다. 이것은 이러한 가장자리에 상대적인 의미를 제공합니다.

3. 그래프 표현

그래프는 인접 행렬 및 인접 목록과 같은 다양한 형태로 표현 될 수 있습니다. 각각은 다른 설정에서 장단점이 있습니다.

이 섹션에서는 이러한 그래프 표현을 소개합니다.

3.1. 인접 매트릭스

인접 행렬은 그래프 의 꼭지점 수와 동일한 차원을 갖는 정사각형 행렬입니다 .

행렬의 요소는 일반적으로 '0'또는 '1'값을 갖습니다. 값 '1'은 행과 열의 정점 사이의 인접성을 나타내고 그렇지 않으면 '0'값을 나타냅니다.

이전 섹션의 간단한 그래프에서 인접 행렬이 어떻게 보이는지 살펴 보겠습니다.

이 표현은 구현하기훨씬 쉽고 쿼리효율적 입니다. 그러나 점유 공간에 비해 효율성이 떨어집니다 .

3.2. 인접 목록

인접 목록은 목록 의 배열 일뿐 입니다. 배열의 크기는 그래프의 정점 수와 동일합니다.

배열의 특정 인덱스에있는 목록은 해당 배열 인덱스가 나타내는 정점의 인접 정점을 나타냅니다.

이전 섹션의 간단한 그래프에서 인접 목록이 어떻게 보이는지 살펴 보겠습니다.

이 표현은 생성하기비교적 어렵고 쿼리 효율성이 떨어집니다 . 그러나 더 나은 공간 효율성을 제공합니다 .

이 자습서에서는 그래프를 나타 내기 위해 인접 목록을 사용합니다.

4. 자바 그래프

Java에는 그래프 데이터 구조의 기본 구현이 없습니다.

그러나 Java Collections를 사용하여 그래프를 구현할 수 있습니다.

정점을 정의하는 것으로 시작하겠습니다.

class Vertex { String label; Vertex(String label) { this.label = label; } // equals and hashCode }

위의 정점 정의에는 레이블이 있지만 이것은 Person 또는 City 와 같은 가능한 엔티티를 나타낼 수 있습니다 .

Also, note that we have to override the equals() and hashCode() methods as these are necessary to work with Java Collections.

As we discussed earlier, a graph is nothing but a collection of vertices and edges which can be represented as either an adjacency matrix or an adjacency list.

Let's see how we can define this using an adjacency list here:

class Graph { private Map
    
      adjVertices; // standard constructor, getters, setters }
    

As we can see here, the class Graph is using Map from Java Collections to define the adjacency list.

There are several operations possible on a graph data structure, such as creating, updating or searching through the graph.

We'll go through some of the more common operations and see how we can implement them in Java.

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.

이러한 라이브러리는 그래프 데이터 구조를 기반으로 여러 구현을 제공합니다. 또한 현재 Facebook에서 사용자가 생성 한 그래프를 분석하는 데 사용되는 Apache Giraph와 그래프 데이터베이스 위에서 일반적으로 사용되는 Apache TinkerPop과 같은 그래프 기반의 더 강력한 프레임 워크 도 있습니다.

8. 결론

이 기사에서는 그래프를 그 표현과 함께 데이터 구조로 설명했습니다. Java Collections를 사용하여 Java에서 매우 간단한 그래프를 정의하고 그래프에 대한 공통 순회도 정의했습니다.

또한 그래프 구현을 제공하는 Java 플랫폼 외부에서 Java에서 사용할 수있는 다양한 라이브러리에 대해 간략하게 설명했습니다.

항상 그렇듯이 예제 코드는 GitHub에서 사용할 수 있습니다.