Java優先度検索(DFS/BFS)の実用化

深さ優先検索DFS は深さ優先検索です。簡単に言うと、このプロセスは、それ以上深くは進めなくなり、各ノードには 1 回しかアクセスできないまで、考えられるすべての分岐パスをドリルダウンします。幅優先検索 BFS は幅優先検索です。ノードを展開して取得したすべての子ノードは、先入れ先出し キュー に追加されます。

DFS/BFS 検索アルゴリズム分析

定理 1: 開始点に接続されているすべての頂点をマークするために深さ優先検索に必要な時間は、頂点の次数の合計に比例します。

2 つの点 v と w があるとします。v が最初に w を訪問すると、辺 v-w は未チェックの状態から一度訪問されます。 w が v を訪問すると、辺 w-v が再度チェックされますが、この時点でこの辺はすでに 2 回訪問されていることがわかります。これ以外に、エッジ v-w (w-v) が訪問される可能性は他にありません。したがって、グラフ内の各エッジは 2 回アクセスされることがわかります。エッジ × 2 = 頂点 Σ 次数 (各頂点の次数の合計)。つまり正比例するのです。

定理 2: 一般に、深さ優先探索を使用して解決できる問題は、幅優先探索に変換できます。

深さ優先検索の利点は次のとおりです: 再帰理解しやすく、シンプルです。ただし、深さ優先探索には明確な目的がありませんが、幅優先探索は近くから遠くへ順番に探索し、最適解を見つけることができる場合が多く、ループは再帰よりも効率的であり、スタックオーバーフローのリスク。疎なグラフでの幅優先検索の効率は、深さ優先検索よりもはるかに高速であり、密なグラフでもほぼ同じです。幅優先検索が必ずしも必要でない場合は、深さ優先検索の使用を試みることができます。

定理 3: グラフ記録方法として隣接リストを使用する場合、深さ優先検索と幅優先検索の時間計算量は両方とも O(V+E) です。

要素へのアクセスに必要な時間は、主にグラフデータの記録方法に依存し、深さ優先検索か幅優先検索かにかかわらず、計算が完了する前にグラフ全体をチェックする必要があります。データを記録する方法として隣接行列を使用する場合、計算量は O(n²) となり、隣接リストには (頂点 + エッジの数 × 2) のデータのみが含まれます。エッジ数の半分だけを実行する必要があり、残りの半分の操作はチェックすることで省略できます。したがって、グラフ記録方法として隣接リストを使用する場合、DFS と BFS の両方の時間計算量は O(V+E) になります。

基本的なデータ構造 - グラフクラス

深さ優先アルゴリズムと幅優先アルゴリズムは、グラフ理論に基づいたアルゴリズムです。アプリケーションを実装する前に、まず基本的な 無向グラフ クラス データ構造を実装します。
Graph クラスは V を使用して固定点を定義し、E を使用してエッジを定義し、LinkedListInteger>[ ] を使用して隣接リストを定義します。

package Graph;

import java.util.LinkedList;

public class Graph {

    private final int V;
    private int E;
    private LinkedList<Integer>[] adj;

    public Graph(int V) {
        this.V = V;
        this.E = 0;
        adj = (LinkedList<Integer>[]) new LinkedList[V];
        for (int v = 0; v < V; v++)
            adj[v] = new LinkedList<>();
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    public LinkedList<Integer> adj(int v) {
        return adj[v];
    }

    public int degree(int v,Graph g){
        int count = 0;
        for(int s : adj(v))
            count++;
        return count;
    }

}

Graph クラスのジェネリック 配列

ジェネリック配列はここでのみ宣言され、通常の配列型変換によって実装されますが、セキュリティの隠れたリスクもあることに注意してください。
以下のようなプログラムはコンパイルに成功しますが、実行時にジェネリックが消去されるため、エラーが発生します。オブジェクト配列クラス間の代入はエラーを報告しません。

  public static void main(String[] args) {

        LinkedList<Integer>[] adj;
        adj = (LinkedList<Integer>[]) new LinkedList[5];
        Object o = adj;
        Object[] oa = (Object[]) o;
        List<String> li = new LinkedList<>();  
        li.add("s");  

        oa[0] = li;
        System.out.println(adj[0]);
    }

この状況を理解する必要がありますが、この記事では主にアルゴリズムを紹介するため、この部分についてはあまり説明しません。ここでエラーの可能性を列挙したいと思います。

接続性問題

package Graph;

import java.util.ArrayDeque;
import java.util.Queue;

public class Connected {

    private Graph g;
    private boolean[] marked;
    private int count;

    public Connected(Graph g) {
        this.g = g;
        marked = new boolean[g.V()];
    }

    /**
     * DFS算法计算连通结点
     * 
     * @param s
     *            起点
     */
    public void DFS(int s) {
        marked[s] = true;
        count++;
        for (int w : g.adj(s))
            if (!marked[w])
                DFS(w);
    }

    /**
     * BFS算法计算连通结点
     * 
     * @param s
     *            起点
     */
    public void BFS(int s) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(s);
        marked[s] = true;
        count++;
        while (!q.isEmpty()) {
            for (int w : g.adj(q.poll()))
                if (!marked[w]) {
                    marked[w] = true;
                    count++;
                    q.add(w);
                }
        }
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 返回该起点总连通结点数
     * 
     * @return 连通结点数
     */
    public int count() {
        return count;
    }

    /**
     * 判断一个结点是否被连通
     * 
     * @param v
     *            判断结点
     * @return 连通状态
     */
    public boolean isMarked(int v) {
        return marked[v];
    }

}

単一点経路問題

package Graph;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Paths {

    private Graph g;
    private boolean[] marked;
    private int[] edgeTo;

    public Paths(Graph g) {
        this.g = g;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
    }

    /**
     * DFS算法计算单点路径问题
     * 
     * @param s
     *            起点
     */
    public void DFS(int s) {
        marked[s] = true;
        for (int w : g.adj(s))
            if (!marked[w]) {
                edgeTo[w] = s;
                DFS(w);
            }
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 判断一个结点是否被连通
     * 
     * @param v
     *            判断结点
     * @return 连通状态
     */
    public boolean isMarked(int v) {
        return marked[v];
    }

    /**
     * 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
     * 
     * @param s
     *            起点
     * @param v
     *            终点
     * @return 存在状态
     */
    public boolean hasPathTo(int s, int v) {
        DFS(s);
        if (isMarked(v))
            return true;
        return false;
    }
}

単一点最短経路

package Graph;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class Paths {

    private Graph g;
    private boolean[] marked;
    private int[] edgeTo;

    public Paths(Graph g) {
        this.g = g;
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
    }

    /**
     * DFS算法计算单点路径问题
     * 
     * @param s
     *            起点
     */
    public void DFS(int s) {
        marked[s] = true;
        for (int w : g.adj(s))
            if (!marked[w]) {
                edgeTo[w] = s;
                DFS(w);
            }
    }

    /**
     * BFS算法计算单点最短路径问题
     * 
     * @param s
     *            起点
     */
    public void BFS(int s) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(s);
        marked[s] = true;
        while (!q.isEmpty()) {
            for (int w : g.adj(q.poll()))
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = s;
                    q.add(w);
                }
        }
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 判断一个结点是否被连通
     * 
     * @param v
     *            判断结点
     * @return 连通状态
     */
    public boolean isMarked(int v) {
        return marked[v];
    }

    /**
     * 是否存在从s到v的路径，默认调用深度优先，可以选择广度优先
     * 
     * @param s
     *            起点
     * @param v
     *            终点
     * @return 存在状态
     */
    public boolean hasPathTo(int s, int v) {
        DFS(s);
        // BFS(v);
        if (isMarked(v))
            return true;
        return false;
    }

    /**
     * 输出最短路径
     * 
     * @param s
     *            起点
     * @param v
     *            终点
     */
    public void pathTo(int s, int v) {
        if (!hasPathTo(s, v))
            return;
        BFS(s);
        // DFS(s); 但深度优先可能不是最短路径
        Stack<Integer> sta = new Stack<>();
        sta.push(v);
        for (int i = v; i != s; i = edgeTo[i])
            sta.push(edgeTo[i]);
        while (!sta.isEmpty())
            System.out.println(sta.pop() + " ");
    }
}

連結成分計算

package Graph;

public class ConnectedComp {

    private Graph g;
    private boolean[] marked;
    private int count;
    private int[] id;

    public ConnectedComp(Graph g) {
        this.g = g;
        id = new int[g.V()];
        marked = new boolean[g.V()];
    }

    /**
     * 调用方法，便利全部结点判断分量数
     */
    public void DFS() {
        for (int s = 0; s < g.V(); s++) {
            if (!marked[s]) {
                DFS(s);
                count++;
            }
        }
    }

    /**
     * DFS算法计算连通结点
     * 
     * @param s
     *            起点
     */
    private void DFS(int s) {
        marked[s] = true;
        id[s] = count;
        for (int w : g.adj(s))
            if (!marked[w])
                DFS(w);
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 返回该图总分量数目
     * 
     * @return 分量数
     */
    public int count() {
        return count;
    }

    /**
     * 返回该节点属于第几个分量
     * 
     * @param s
     *            判断结点
     * @return 分量组数
     */
    public int id(int s) {
        return id[s];

    }

}

非巡回グラフ問題

package Graph;

public class Cycle {

    private Graph g;
    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph g) {
        this.g = g;
        marked = new boolean[g.V()];
        for(int s=0;s<g.V();s++)
            if(!marked[s])
                DFS(s,s);
    }

    /**
     * DFS算法计算无环图问题
     * 
     * @param s
     *            起点
     */
    public void DFS(int s, int v) {
        marked[s] = true;
        for (int w : g.adj(s))
            if (!marked[w])
                DFS(w, s);
            else if (w != v)
                hasCycle = true;
    }

    /**
     * 初始化marked标记数组状态
     */
    public void cleanMarked() {
        for (boolean b : marked)
            b = false;
    }

    /**
     * 判断是否有环
     * 
     * @return 判断结果
     */
    public boolean hasCycle() {
        return hasCycle;
    }

}

二部グラフの二色問題

りー

以上がJava優先度検索(DFS/BFS)の実用化の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。