数据结构：深度优先与广度优先

深度优先

package graph;

import java.util.Stack;

/*
 * 使用深度优先搜索查找图中的路径
 */
public class DepthFirstPaths {
    private boolean[] marked; //是否以被标记
    private int[] edgeTo; //从起点到一个顶点的已知路径上的最后一个顶点
    private final int s; //起点

    //找出所有起点为s的路径
    public DepthFirstPaths(Graph g,int s) {
        marked=new boolean[g.V()];
        edgeTo=new int[g.V()];
        this.s=s;
        dfs(g, s);
    }

    //深度优先搜索
    private void dfs(Graph graph,int v){
        marked[v]=true;
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                edgeTo[w]=v;
                dfs(graph, w);
            }
        }
    }

    //是否存在从起点s到v的路径
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //起点s到v的路径，如果不存在则返回null
    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path=new Stack<>();
        for (int i = v; i != s; i=edgeTo[i]) {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

广度优先

package graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/*
 * 广度优先搜索，按照与起点的距离的顺序来遍历所有顶点
 */
public class BreadFirstPaths {
    private boolean[] marked; //是否以被标记
    private int[] edgeTo; //从起点到一个顶点的已知路径上的最后一个顶点
    private final int s; //起点

    public BreadFirstPaths(Graph g,int s) {
        marked=new boolean[g.V()];
        edgeTo=new int[g.V()];
        this.s=s;
        bfs(g, s);
    }

    //广度优先搜索
    private void bfs(Graph g,int s){
        Queue<Integer> queue=new LinkedList<>();
        marked[s]=true; //标记起点
        queue.offer(s); //将起点加入队列
        while (!queue.isEmpty()) {
            int v=queue.poll(); //从队列中删除下一个顶点
            for (int w : g.adj(v)) {
                if (!marked[w]) { //对于每个未被标记的相邻顶点
                    edgeTo[w]=v;  //保存最短路径的最后一条边
                    marked[w]=true; //标记它，因为最短路径已知
                    queue.offer(w); //并将它添加到队列中
                }
            }
        }
    }

    //是否存在从起点s到v的路径
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //起点s到v的路径，如果不存在则返回null
    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path=new Stack<>();
        for (int i = v; i != s; i=edgeTo[i]) {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}