Java におけるグラフデータ構造

はじめに

このチュートリアルでは、Java でグラフデータ構造を作成および操作する方法を学びます。グラフは、オブジェクト間の関係を表すために使用される基本的なデータ構造です。異なる種類のグラフ、それらを表現する方法、および頂点やエッジの追加と削除、幅優先探索、深さ優先探索などの一般的な操作の実装方法を探求します。

ノードクラスを作成する

まず、グラフ内の頂点を表すための Node クラスを作成します。各ノードには名前と、値や重みなどの他の情報がある場合があります。

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

グラフクラスを作成する

次に、グラフ自体を表す Graph クラスを作成します。エッジとその端点を格納するために隣接リストを使用します。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1!= null) {
            list1.remove(node2);
        }
        if (list2!= null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

グラフを作成する

さて、グラフを作成していくことにしましょう。そして、ノードとエッジを追加します。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

幅優先探索

ここでは、幅優先順序でグラフ内のノードを探索する幅優先探索アルゴリズムを実装します。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

実行方法の例：

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

深さ優先探索

ここでは、深さ優先順序でグラフ内のノードを探索する深さ優先探索アルゴリズムを実装します。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

実行方法の例：

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

ノードを削除する

グラフからノードを削除し、そのノードに接続されているエッジも削除することができます。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

エッジを削除する

グラフ内の 2 つのノード間のエッジを削除することができます。

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

まとめ

このチュートリアルでは、ノードと隣接リスト表現を使って Java でグラフデータ構造を作成する方法を学びました。また、グラフを操作するための操作を実装しました。これには、ノードとエッジの追加と削除が含まれます。最後に、幅優先探索と深さ優先探索の 2 つの探索アルゴリズムを実装しました。