Javaを使用してグラフトラバーサルアルゴリズムを実装する方法

Java を使用してグラフ トラバーサル アルゴリズムを実装する方法

グラフは離散数学における重要なデータ構造であり、物事間の関係を記述するためによく使用されます。グラフ トラバーサル アルゴリズムとは、特定のノードから開始して特定のルールに従ってグラフ内のすべてのノードを順番に訪問するプロセスを指します。一般的に使用されるグラフ走査アルゴリズムには、深さ優先検索 (DFS) と幅優先検索 (BFS) が含まれます。この記事では、Java 言語を使用してこれら 2 つのグラフ走査アルゴリズムを実装する方法を紹介し、具体的なサンプル コードを提供します。

1. 深さ優先検索 (DFS)

深さ優先検索は、開始ノードから開始して、将来のノードに遭遇しなくなるまで、隣接するノードを再帰的に訪問する事前順序走査アルゴリズムです。訪問した隣接ノードに移動し、その後、前のノードに戻り、グラフ全体が走査されるまで、訪問していない隣接ノードを訪問し続けます。

次は、深さ優先検索によってグラフを移動するためのサンプル コードです:

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void DFSUtil(int v, Boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    void DFS(int v) {
        Boolean visited[] = new Boolean[V];
        Arrays.fill(visited, false);
 
        DFSUtil(v, visited);
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.DFS(2);
    }
}

出力結果:

从顶点2开始的遍历结果：
2 0 1 3

2. 幅優先検索 (BFS)

幅優先検索は、開始ノードから開始して、グラフ全体が走査されるまでレイヤーごとにノードを訪問する水平走査アルゴリズムです。キューを使用して幅優先検索を実装し、キューから一度に 1 つのノードを取得し、未訪問の隣接ノードをキューに追加します。

次は、幅優先検索によってグラフを移動するためのサンプル コードです:

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void BFS(int v) {
        boolean visited[] = new boolean[V];
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        visited[v] = true;
        queue.add(v);
 
        while (queue.size() != 0) {
            v = queue.poll();
            System.out.print(v + " ");
 
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.BFS(2);
    }
}

出力結果:

从顶点2开始的遍历结果：
2 0 3 1

上記のサンプル コードでは、隣接リストを使用して次のことを行います。はグラフの構造を表し、エッジを追加してグラフを構築します。次に、DFS メソッドと BFS メソッドをそれぞれ呼び出して、グラフを走査します。出力結果は、トラバーサル アルゴリズムによって取得されたノード シーケンスです。

概要:

この記事の概要とサンプル コードを通じて、Java 言語を使用して深さ優先検索や幅優先検索などのグラフ トラバーサル アルゴリズムを実装する方法を学習できます。これら 2 つの走査アルゴリズムは、Web クローラー、迷路解決、その他の分野など、現実に広く使用されています。グラフ走査アルゴリズムをマスターすると、関連する問題を迅速かつ効果的に解決できます。

以上がJavaを使用してグラフトラバーサルアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。