1概要

このチュートリアルでは、グラフの基本概念をデータ構造として理解します。

また、グラフ上で可能なさまざまな操作とともに、Javaでのその実装についても調べます。グラフ実装を提供するJavaライブラリについても説明します。


2グラフデータ構造

グラフは、ソーシャルメディアプラットフォーム上の人々のネットワークのように、接続されたデータを格納するためのデータ構造です。

グラフは頂点と辺で構成されています。

頂点はエンティティ

(たとえば人)を表し、

エッジはエンティティ間の関係

(たとえば人の友情)を表します。

これをよりよく理解するために単純なグラフを定義しましょう。

ここでは、5つの頂点と6つの辺を持つ単純なグラフを定義しました。円は人を表す頂点で、2つの頂点を結ぶ線はオンラインポータル上の友達を表す辺です。

エッジの特性に応じて、この単純なグラフにはいくつかのバリエーションがあります。次のセクションでそれらを簡単に見ていきましょう。

ただし、このチュートリアルでは、Javaの例としてここに提示されている単純なグラフにのみ焦点を当てます。


2.1. 有向グラフ

これまでに定義したグラフには、方向のない辺があります。これらの辺がその方向を向いている場合、結果として得られるグラフは有向グラフとして知られています。

この例としては、オンラインポータルの友情で誰が友達リクエストを送信するかを表すことができます。


https://www.baeldung.com/uploads/graph2-125×125.jpg%20125w

リンク:/uploads/Directed-Graph-1-300×300.jpg[]

ここでは、エッジの方向が固定されていることがわかります。縁部も双方向にすることができる。


2.2. 加重グラフ

繰り返しますが、この単純なグラフには、偏りのない、または重み付けされていないエッジがあります。その代わりにこれらの

辺が相対的な重み

を持つ場合、このグラフは加重グラフとして知られています。

この実用的なアプリケーションの例は、オンラインポータル上で友好関係が比較的古いことを表すことです。

ここで、エッジにはそれらに関連する重みがあることがわかります。これはこれらの辺に相対的な意味を与えます。

3.

グラフ表現

グラフは、隣接行列や隣接リストなどのさまざまな形式で表現できます。それぞれの長所と短所は異なります。

このセクションでは、これらのグラフ表現を紹介します。


3.1. 隣接マトリックス

隣接行列は、

グラフ内の頂点数

に等しい次元を持つ正方行列です。

行列の要素は通常、値 ‘0’または ‘1’を持ちます。値「1」は、行と列の頂点間の隣接関係を示し、それ以外の場合は値「0」を示します。

前のセクションの簡単なグラフで、隣接行列がどのように見えるかを見てみましょう。

この表現は、実装がかなり簡単で、照会も効率的です。しかし、それは

占有スペースに関してはあまり効率的ではありません


3.2. 隣接リスト

隣接リストは、

リストの配列

にすぎません。配列のサイズは、グラフ内の頂点数と同じです。

配列の特定のインデックスにあるリストは、その配列インデックスによって表される頂点の隣接する頂点を表します。

前のセクションの簡単なグラフで、隣接リストがどのように見えるかを見てみましょう。

この表現は、

作成するのが比較的難しく、照会するのが非効率的です

。しかし、それは

より良いスペース効率

を提供します。

このチュートリアルでは、グラフを表すために隣接リストを使用します。


4 Java

のグラフ

Javaはグラフデータ構造のデフォルト実装を持っていません。

ただし、Javaコレクションを使用してグラフを実装できます。

  • 頂点を定義することから始めましょう:**

class Vertex {
    String label;
    Vertex(String label) {
        this.label = label;
    }

   //equals and hashCode
}

上記の頂点の定義は単にラベルを特徴としていますが、これは

Person

や__Cityのようなあらゆる可能なエンティティを表すことができます。

また、

equals()

メソッドと

hashCode()

メソッドは、Javaコレクションを操作するために必要なので、これらをオーバーライドする必要があります。

前に説明したように、グラフは隣接行列または隣接リストとして表すことができる頂点と辺の集合に他なりません。

ここで隣接リストを使ってこれを定義する方法を見てみましょう:

class Graph {
    private Map<Vertex, List<Vertex>> adjVertices;

   //standard constructor, getters, setters
}

ここでわかるように、クラス

Graph

は、隣接リストを定義するためにJavaコレクションの

Map

を使用しています。

  • グラフの作成、更新、または検索** など、グラフデータ構造に対して可能な操作はいくつかあります。

より一般的な操作をいくつか説明し、それらをJavaで実装する方法を確認します。


5グラフ突然変異操作

はじめに、グラフのデータ構造を変更するためのメソッドをいくつか定義します。

頂点を追加および削除するためのメソッドを定義しましょう。

void addVertex(String label) {
    adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}

void removeVertex(String label) {
    Vertex v = new Vertex(label);
    adjVertices.values()
      .stream()
      .map(e -> e.remove(v))
      .collect(Collectors.toList());
    adjVertices.remove(new Vertex(label));
}

これらのメソッドは単に

vertices Set

に要素を追加したり削除したりします。

それでは、エッジを追加するメソッドも定義しましょう。

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);
}

このメソッドは新しい

Edge

を作成し、隣接する頂点__Mapを更新します。

同様に、

removeEdge()

メソッドを定義します。

void removeEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    List<Vertex> eV1 = adjVertices.get(v1);
    List<Vertex> eV2 = adjVertices.get(v2);
    if (eV1 != null)
        eV1.remove(v2);
    if (eV2 != null)
        eV2.remove(v1);
}

次に、これまでに定義した方法を使用して、先ほど作成した単純なグラフを作成する方法を見てみましょう。

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;
}

特定の頂点の隣接頂点を取得するメソッドを最後に定義します。

List<Vertex> getAdjVertices(String label) {
    return adjVertices.get(new Vertex(label));
}


6. グラフをたどる

グラフのデータ構造と、それを作成および更新するための関数が定義されたので、グラフをトラバースするための追加の関数をいくつか定義できます。グラフ内の検索など、意味のある操作を実行するには、グラフをトラバースする必要があります。

グラフをたどるには、深さ優先のトラバースと幅優先のトラバースの2つの方法があります。

6.1. 深さ優先探索

深さ優先探索は、任意の根の頂点から始まり、同じレベルで頂点を探索する前に、各ブランチに沿って可能な限り深い頂点を探索します。

深さ優先探索を実行する方法を定義しましょう。

Set<String> depthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Stack<String> stack = new Stack<String>();
    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;
}

ここでは、

移動する必要がある頂点を格納するために

Stack

を使用しています

前のサブセクションで作成したグラフでこれを実行しましょう。

assertEquals("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal(graph, "Bob").toString());

ここでは、トラバースのルートとして頂点「Bob」を使用していますが、これは他のどの頂点でもかまいません。


6.2. 幅優先トラバーサル

比較的、幅優先トラバーサルは任意の根の頂点から始まり、グラフ内でより深くなる前に** すべての隣接頂点を同じレベルで探索します。

それでは、幅優先探索を実行する方法を定義しましょう。

Set<String> breadthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Queue<String> queue = new LinkedList<String>();
    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;
}

幅優先探索



Queue

を利用して探索する必要がある頂点を格納します

同じトラバーサルをもう一度実行してみましょう。

assertEquals("[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal(graph, "Bob").toString());

繰り返しになりますが、ここで「Bob」となっているルート頂点は、他のどの頂点でもかまいません。


7. グラフ用のJavaライブラリ

グラフを常にゼロからJavaで実装する必要はありません。

グラフの実装を提供する利用可能なオープンソースと成熟したライブラリがいくつかあります。

次のいくつかのサブセクションでは、これらのライブラリのいくつかを見ていきます。


7.1. JGraphT


JGraphT

は、グラフデータ構造に関してJavaで最も人気のあるライブラリの1つです。それは、とりわけ、単純なグラフ、有向グラフ、加重グラフの作成を可能にします。

さらに、それはグラフデータ構造上で多くの可能なアルゴリズムを提供します。以前のチュートリアルの1つは、https://www.baeldung.com/jgrapht[JGraphT]の詳細です。


7.2. Google Guava


Google Guava

は、グラフデータ構造とそのアルゴリズムを含むさまざまな機能を提供する一連のJavaライブラリです。

単純な

Graph



ValueGraph

、および

Network

の作成をサポートします。これらは

Mutable

または

Immutable

として定義できます。


7.3. Apache Commons


Apache Commons

は再利用可能なJavaコンポーネントを提供するApacheプロジェクトです。これには、グラフデータ構造を作成および管理するためのツールキットを提供するCommons Graphが含まれます。これは、データ構造を操作するための一般的なグラフアルゴリズムも提供します。


7.4. Sourceforge JUNG


Java Universal Network/Graph(JUNG)

は、グラフとして表現できるデータのモデリング、分析、および視覚化のための拡張可能な言語を提供するJavaフレームワークです。

JUNGは、クラスタリング、分解、最適化などのルーチンを含む多数のアルゴリズムをサポートしています。

これらのライブラリは、グラフデータ構造に基づいていくつかの実装を提供します。

Apache Giraph

のような、グラフに基づいた** より強力なフレームワークもあります。これは、Facebookでユーザーによって作成されたグラフの分析に現在使用されています。 .org/[Apache TinkerPop]、グラフデータベースの上でよく使われます。


8結論

この記事では、データ構造としてのグラフとその表現について説明しました。 Javaコレクションを使用してJavaで非常に単純なグラフを定義し、そのグラフの共通トラバーサルも定義しました。

また、グラフ実装を提供するJavaプラットフォーム以外のJavaで利用可能なさまざまなライブラリについても簡単に説明しました。

いつものように、例のコードはhttps://github.com/eugenp/tutorials/tree/master/core-java[GitHubで利用可能]にあります。