1、深度优先

深度优先遍历也叫深度优先搜索（Depth First Search)他的遍历规则：不断地沿着顶点的深方向遍历， 顶点的深度方向是指他的零界点方向，
如图

image.png

给定一图G=<V,E>用vsitted表示顶点i的访问情况， 则初始情况下所有的visited[i]都为false ， 假设从顶点V0开始遍历， 则下一个遍历点则是顶点V0的第一个邻接点V1，接着遍历V1第一个邻接点V3~~~~~~~~~~一直到所有的顶点都访问过
假如我要以V0作为初始的顶点,
第一步，找最近的一个邻接点，然后一直遍历，
则遍历的顺序为V0-V1-V3，
第二步， 回溯法

当遍历到V3时发觉没有遍历的节点了，因为V3指向的节点只能说V0, V0已经遍历过， 所以没路可走， 这时候回退到V1， 看看V1是否有遍历的节点，V1没有时回退到V0， 看看V0是否有下一个节点遍历，V0还有个V2没有遍历， 则 遍历V2 ，遍历的顺序为V0-V1-V3-V2--V4
代码如下

    public class ExampleUnitTest {
       @Test
        public void test(){
           Graph graph = new Graph(5);
           //添加图的结构数据
            int[] v0 = new int[]{0, 1, 1, MAX_WEIGHT, MAX_WEIGHT};
            int[] v1 = new int[]{MAX_WEIGHT, 0, MAX_WEIGHT, 1, MAX_WEIGHT};
            int[] v2 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT, MAX_WEIGHT};
            int[] v3 = new int[]{1, MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT};
            int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 0};
            graph.matrix[0] = v0;
            graph.matrix[1] = v1;
            graph.matrix[2] = v2;
            graph.matrix[3] = v3;
            graph.matrix[4] = v4;
            //深度优先
            graph.dfs();
            //广度优先
            graph.bfs();
        }
    }

    /**
     * Created by Jett on 2018/12/21.
     */

    public class Graph {
        public int[] vertices;//顶点集
        public int[][] matrix;//图的边的信息
        public int verticesSize;

        public static final int MAX_WEIGHT = Integer.MAX_VALUE;

        public boolean[] isVisited;

        public Graph(int verticesSize) {
            this.verticesSize = verticesSize;
            vertices = new int[verticesSize];
            matrix = new int[verticesSize][verticesSize];
            isVisited = new boolean[verticesSize];
            for (int i = 0; i < verticesSize; i++) {
                vertices[i] = i;
            }
        }

         /**
         * 获取第一个邻接点
         */
        public int getFirstNeightBor(int v) {
            for (int i = 0; i < verticesSize; i++) {
                if (matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT) {
                    return i;
                }
            }
            return -1;
        }

        /**
         * 获取到顶点v的邻接点index的下一个邻接点
         */
        public int getNextNeightBor(int v, int index) {
            for (int i = index + 1; i < verticesSize; i++) {
                if (matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT) {
                    return i;
                }
            }
            return -1;
        }
        /**
         * 深度优先(很象二叉树的前序)
         */
        public void dfs() {
            for (int i = 0; i < verticesSize; i++) {
                if (!isVisited[i]) {
                    System.out.println("viested vertice " + i);
                    dfs(i);
                }
            }
        }

        public void dfs(int i) {
            isVisited[i] = true;
            int v = getFirstNeightBor(i);
            while (v != -1) {
                if (!isVisited[v]) {
                    System.out.println("visted vertice " + v);
                    dfs(v);
                }
                v = getNextNeightBor(i, v);
            }
        }

2、广度优先

广度优先遍历也交广度优先搜索（Breadth First Search）,他的遍历规则为：
1、先访问完当前的顶点的所有邻接点，
2、先访问顶点的邻接点先于后访问顶点的邻接点被访问
具体说， 给的那个上图G=<V,E>，用visited[i]表示顶点i被访问的情况，初始情况下Visited【i]都为false,假如从顶点V0开始遍历， 则是遍历的顺序为V0-V1-V2， 遍历完V0所有的节点之后， 则从邻接点V1开始， 遍历V1下所有的节点，接着就遍历V2所有的节点，如果后面还有很多的话，以此类推。
代码如下

/**
     * 广度优先
     */
    public void bfs(){
        for (int i = 0; i < verticesSize; i++) {
            isVisited[i]=false;
        }
        for (int i = 0; i < verticesSize; i++) {
            if(!isVisited[i]){
                isVisited[i]=true;
                System.out.println("visited vertice:"+ i);
                bfs(i);
            }
        }
    }

    public void bfs(int i) {
        LinkedList<Integer> queue = new LinkedList<>();
        //找第一个邻接点
        int fn = getFirstNeightBor(i);
        if (fn == -1) {
            return;
        }
        if (!isVisited[fn]) {
            isVisited[fn] = true;
            System.out.println("visted vertice:" + fn);
            queue.offer(fn);
        }
        //开始把后面的邻接点都入队
        int next = getNextNeightBor(i, fn);
        while (next != -1) {
            if (!isVisited[next]) {
                isVisited[next] = true;
                System.out.println("visted vertice:" + next);
                queue.offer(next);
            }
            next = getNextNeightBor(i, next);
        }
        //从队列中取出来一个，重复之前的操作
        while(!queue.isEmpty()){
            int point=queue.poll();//v1  v2
            bfs(point);
        }

    }