Depth FirstSearchDFS is Depth First Search. Briefly speaking, the process is to drill down into every possible branch path until it cannot go any deeper, and each node can only be visited once. Breadth First Search BFS is Breadth First Search. All child nodes obtained by expanding the node will be added to a first-in, first-out queue.

DFS/BFS search algorithm analysis

Theorem 1: Depth-first search marks the time required for all vertices connected to the starting point and the time of the vertices The sum of degrees is directly proportional.

Suppose we have two points v and w. In a graph, when v visits w first, the edge v-w changes from unchecked status to checked , this edge has been visited once. When w visits v, the edge w-v is checked again, but it is found that it has already been checked. At this time, this edge has been visited twice. Apart from this, there is no other possibility that causes the edge v-w (w-v) to be visited. Therefore, it can be seen that each edge in the graph will be visited twice, edge × 2 = vertex Σ degree (the sum of the degrees of each vertex). So directly proportional.

Theorem 2: Generally, problems that can be solved using depth-first search can be converted into breadth-first search.

The advantages of depth-first search are: RecursionEasy to understand and simple. However, depth-first search does not have a clear purpose, while breadth-first search searches from near to far, and can find the optimal solution in many cases, and loop is more efficient than recursion, and There is no risk of stack overflow. The efficiency of breadth-first search in sparse graphs is much faster than depth-first search, and is almost the same in dense graphs. When breadth-first search is not necessarily needed, we can try to use depth-first search.

Theorem 3: When using adjacency lists as the graph recording method, the time complexity of both depth-first search and breadth-first search is O(V+E).

The time required to access elements mainly depends on the recording method of graph data. Whether it is depth-first search or breadth-first search, the entire graph needs to be checked before the calculation can be completed. The main time-consuming factor is Partly depends on the recording method. When using the adjacency matrix as the method of recording data, the complexity is O(n²), and the adjacency list only has (vertex + number of edges × 2) data. We only Half of the number of edges needs to be performed, and the other half can be exempted by inspection. Therefore, when using adjacency lists as the graph recording method, the time complexity of both DFS and BFS is O(V+E).

Basic data structure - graph class

Depth-first algorithm and breadth-first algorithm are algorithms based on graph theory. Before implementing the application, first implement the basic Undirected Graph class data structure.
The Graph class uses V to define fixed points, E to define edges, and LinkedList<Integer>[ ] to define adjacency lists.

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

}

Copy after login

Generics in the Graph classArray

It should be noted that although only generic arrays are declared here, ordinary array types are used Transformation is achieved, but there are also security hidden dangers.
Similar to the following program, the compilation passes but the content is wrong because generics are erased during runtime. ObjectAssignment between array classes does not report an error.

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

Copy after login

This situation needs to be understood, but this article mainly introduces the algorithm, and this part will not be discussed too much. I would like to list here the possibilities for error.

Connectivity problem

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

}

Copy after login

There is a problem with the single-point path

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

Copy after login

Single-point shortest path

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() + " ");
    }
}

Copy after login

Connected component calculation

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

    }

}

Copy after login

Acyclic graph problem

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

}

Copy after login

Bipart graph two-color problem

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

Copy after login

The above is the detailed content of Practical application of java priority search (DFS/BFS). For more information, please follow other related articles on the PHP Chinese website!