深度优先，检索图中的路线

深度优先是按照一个节点，一直递归向下寻找，找到或者找不到时终止。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.linkedList;
import java.util.List;


public class UndiGraph {
    
    private int point;

    
    private linkedList adjacencyList[];

    
    public UndiGraph(int point) {
        this.point = point;
        // 初始化连接表数组
        adjacencyList = new linkedList[point];
        for (int i = 0; i < point; i++) {
            // 初始化邻接表的每一个槽位的连表
            adjacencyList[i] = new linkedList<>();
        }
    }

    
    public void addPoint(int s, int t) {
        // 数组的下标，代表当前顶点，连表的数据代表的临边数据
        adjacencyList[s].add(t);
        // 因为没有方向，两个节点是互联关系，因此目标节点连线出也有源节点
        adjacencyList[t].add(s);
    }

    
    public void dfs(int[] router,boolean[] visited,int begin,int f, int t) {
        if (visited[f]){
            return;
        }
        router[f] = begin;
        if (f == t){
            return ;
        }
        visited[f] = true;
        linkedList toList = this.adjacencyList[f];
        for (int i = 0; i < toList.size(); i++) {
            dfs(router,visited,f,toList.get(i),t);
        }
    }

    
    public void dfsAllRouter(int f, int t) {
        // 定义数组，保存所有路线的数据
        List routerList = new ArrayList<>();
        int[] router = new int[this.point];// 定义路线存储对象
        initRouter(router);// 初始化路线
        boolean[] hasExist = new boolean[this.point];// 定义数组，保存当前节点是否被访问
        searchRouter(routerList, router, hasExist, f, t);
        for (int[] ints : routerList) {
            printRouterST(ints, f, t);
            System.out.println();
        }
    }

    
    public void initRouter(int[] router) {
        for (int i = 0; i < router.length; i++) {
            router[i] = -1;
        }
    }

    
    public void searchRouter(List routerList, int[] router, boolean[] hasExist, int f, int t) {
        if (f == t) {
            // 说明顶点已经重合
            routerList.add(router);
            return;
        }
        hasExist[f] = true; // 在当前路线上标记当前节点已经访问
        // 遍历当前节点所连接的每一个节点
        linkedList linkedPointList = this.adjacencyList[f];
        for (int i = 0; i < linkedPointList.size(); i++) {
            Integer currentPoint = linkedPointList.get(i);
            if (hasExist[currentPoint]) {
                // 说明当前路径已经走过这个顶点
                continue;
            }
            // 每一个顶点都记录来自哪个顶点
            // 创建新的路径数组，为新节点分支新的路径
            int[] routerTemp = Arrays.copyOf(router, this.point);
            // 创建新的路径数组，为新节点分支新的路过标识符
            boolean[] hasExistTemp = Arrays.copyOf(hasExist, this.point);
            routerTemp[currentPoint] = f;
            // 递归当前路径，继续寻找
            searchRouter(routerList, routerTemp, hasExistTemp, linkedPointList.get(i), t);
        }
    }


    
    public void printRouterST(int[] prev, int s, int t) {
        if (prev[t] != -1 && s != t) {
            // prev记录的是当前路线，因此向前追溯，一直到开始节点依次打印
            printRouterST(prev, s, prev[t]);
        }
        System.out.print(t + ">>");
    }

    public static void main(String[] args) {
        UndiGraph undiGraph = new UndiGraph(8);
        undiGraph.addPoint(0, 1);
        undiGraph.addPoint(0, 3);
        undiGraph.addPoint(1, 2);
        undiGraph.addPoint(1, 4);
        undiGraph.addPoint(2, 5);
        undiGraph.addPoint(3, 4);
        undiGraph.addPoint(4, 5);
        undiGraph.addPoint(4, 6);
        undiGraph.addPoint(5, 7);
        undiGraph.addPoint(6, 7);
        //undiGraph.bfs(0,7);
        int[] router = new int[8];
        boolean[] visited = new boolean[8];
        undiGraph.initRouter(router);
        undiGraph.dfs(router,visited,-1,0, 7);
        undiGraph.printRouterST(router,0,7);
    }
}