java優先搜尋（DFS/BFS）實際應用

深度優先搜尋DFS即Depth First Search。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。廣度優先搜尋BFS是Breadth First Search。所有因為展開節點而得到的子節點都會被加進一個先進先出的佇列。

DFS/BFS搜尋演算法分析

#定理一：深度優先搜尋標記與起點連通的所有頂點所需的時間和頂點的度數總和成正比。

假設我們有兩個點v和w，在一張圖中，當v先訪問到w時，v-w這條邊從未檢查的狀態變成已檢查，此時這條邊訪問了一次。當w訪問v時，w-v這邊又被檢查一次，但是發現已經被檢查，此時這條邊被訪問了兩次。除此之外，不可能再有其他情況導致v-w（w-v）這條邊被訪問。所以可得，圖中每條邊會被訪問兩次，邊×2 = 頂點 Σ 度數 （各頂點度數之和）。所以成正比。

定理二：一般的，使用深度優先搜尋能解決的問題都可轉換為廣度優先搜尋解決。

深度優先搜尋的優點在於：遞迴易於理解、簡單。但是深度優先搜索並沒有明確的目的性，而廣度優先搜索按照由近及遠的順序搜索，在很多情況下能找出最優解，而且循環的效率高於遞歸，並沒有棧溢位的風險。在稀疏圖中廣度優先搜尋的效率更是快過深度優先搜尋很多，稠密圖相差無幾。在不一定需要廣度優先搜尋的情況下，我們可以盡量使用深度優先搜尋。

定理三：使用鄰接表作為圖記錄方法時，深度優先搜尋與廣度優先搜尋時間複雜度均為O(V+E)。

存取元素所需的時間主要取決於圖資料的記錄方法，無論是深度優先搜索或是廣度優先搜索，都需要檢查整張圖後才能計算完畢，耗時的主要部分取決於記錄方式，在使用鄰接矩陣作為記錄數據的方法時，複雜度為O(n²)，而鄰接表中只有(頂點+邊數×2)的數據，我們只需要執行其中一半的邊數，另一半可由檢查免除運算。所以，使用鄰接表作為圖記錄方法時，DFS與BFS時間複雜度均為O(V+E)。

基本資料結構－圖類

深度優先演算法和廣度優先演算法是基於圖論的演算法。在實作應用之前，先實作基本的無向圖類別資料結構。
Graph類別用V定義定點，E定義邊，LinkedListcb2ea6ec594694ef40e2e39d0d6b88f7[ ]定義鄰接表。

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類別中的泛型陣列

#需要說明的是：這裡雖然只是宣告了泛型陣列、用普通陣列類型轉化來實現，但也存在安全隱患。
類似下面的程序，編譯通過但是內容出錯，因為泛型在運行期被擦除，Object數組類間進行賦值不報錯。

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

}

二分圖雙色問題

package Graph;

public class TwoColor {

    private Graph g;
    private boolean[] color;
    private boolean[] marked;
    private boolean isTwoColor;

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

    /**
     * DFS算法计算二分图问题
     * 
     * @param s
     *            起点
     */
    public void DFS(int s) {
        marked[s] = true;
        for (int w : g.adj(s))
            if (!marked[w]) {
                color[w] = !color[s];
                DFS(w);
            } else if (color[w] == color[s])
                isTwoColor = false;
    }

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

    /**
     * 判断是否为二分图
     * 
     * @return 判断结果
     */
    public boolean isTwoColor() {
        return isTwoColor;
    }
}

以上是java優先搜尋（DFS/BFS）實際應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！