java数据结构与算法（再版）（三）

i like like like java do you like a java      // 共40个字符(包括空格)
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97  //对应Ascii码
01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制

public class HuffmanCode {
    public static void main(String[] args) {
        String s = "i like like like java do you like a java";
        byte[] codeBytes = s.getBytes();
        creatHuffmanTree(getNodes(codeBytes)).preOrder();
    }
    //构建赫夫曼树
    public static Node creatHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1){
        //先对nodes进行排序,使用collections工具类
        Collections.sort(nodes);
        //拿到前两个权值最小的节点
        Node leftNode = nodes.get(0);
        Node rightNode = nodes.get(1);
        //通过两个节点构成一个新的节点，注意注意只有最开始的节点有data，其他新构建的节点没有data
        Node parentNode = new Node(null, leftNode.weight + rightNode.weight);
        //清除前面两个节点
        nodes.remove(leftNode);
        nodes.remove(rightNode);
        //设置新节点的左右节点
        parentNode.leftNode = leftNode;
        parentNode.rightNode = rightNode;
        //添加新的节点
        nodes.add(parentNode);
        }
        return nodes.get(0);
    }
    //创建一个Arraylist,来存放每一个节点的数据
    public static List<Node> getNodes(byte[] bytes) {
        //创建一个Map来记录每一个字符出现的数量
        Map<Byte, Integer> hashMap = new HashMap<>();
        List<Node> nodes = new ArrayList<>();
        //记录每一个字符对应的byte所出现的次数
        for (byte aByte : bytes) {
            hashMap.put(aByte, hashMap.getOrDefault(aByte, 0) + 1);
        }
        for (Map.Entry<Byte, Integer> byteIntegerEntry : hashMap.entrySet()) {
            nodes.add(new Node(byteIntegerEntry.getKey(), byteIntegerEntry.getValue()));
        }
        return nodes;
    }
}
//重新创建一个Node
class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node leftNode;
    Node rightNode;
    //写一个前序遍历
    public void preOrder(){
        System.out.println(this);
        if (this.leftNode != null){
            this.leftNode.preOrder();
        }
        if (this.rightNode != null){
            this.rightNode.preOrder();
        }
    }
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

public class HuffmanCode {
    public static void main(String[] args) {
        String s = "i like like like java do you like a java";
        System.out.println(Arrays.toString(zip(s)));
    }
    public static byte[] zip(String s){
        //将这些封装成方法
        byte[] codeBytes = s.getBytes();
        Node node = creatHuffmanTree(getNodes(codeBytes));
        Map<Byte, String> hash = getCode(node);
        return zip(codeBytes,hash);
    }
    //通过hashHuffman来生成编码字符串,返回一个字节数组
    /**
     * @param contentsBytes 需要一个之前的传进来的原始字符串的bytes数组
     * @param hashHuffman   遍历之前的对应字符存入的编码
     * @return 返回一个压缩之后的Bytes数组
     */
    public static byte[] zip(byte[] contentsBytes, Map<Byte, String> hashHuffman) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte contentsByte : contentsBytes) {
            stringBuilder.append(hashHuffman.get(contentsByte));
        }
        //拿到字符编码后，压缩为byte数组，返回一个byte数组
        //这里我们每八位作为一个字符
        int len = 0;
        if (stringBuilder.length() % 8 == 0){
            len = stringBuilder.length()/8;
        }else {
            len = stringBuilder.length()/8 + 1;
        }
        ////创建 存储压缩后的 byte数组
        byte[] bytes = new byte[len];
        int index = 0;
        //这里后移八位
        for (int i = 0; i < stringBuilder.length() ; i+=8) {
            //当后移八位的时候，如果长度不够继续就要进行一个判断，这样就能防止越界。
            String strByte;
            if (i+8 > stringBuilder.length()){
                strByte = stringBuilder.substring(i);
            }else {
                strByte = stringBuilder.substring(i,i+8);
            }
            bytes[index++] = (byte) Integer.parseInt(strByte,2);
        }
        return bytes;
    }
    //构建赫夫曼树
    public static Node creatHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //先对nodes进行排序,使用collections工具类
            Collections.sort(nodes);
            //拿到前两个权值最小的节点
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //通过两个节点构成一个新的节点，注意注意只有最开始的节点有data，其他新构建的节点没有data
            Node parentNode = new Node(null, leftNode.weight + rightNode.weight);
            //清除前面两个节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //设置新节点的左右节点
            parentNode.leftNode = leftNode;
            parentNode.rightNode = rightNode;
            //添加新的节点
            nodes.add(parentNode);
        }
        return nodes.get(0);
    }
    //创建一个Arraylist,来存放每一个节点的数据
    public static List<Node> getNodes(byte[] bytes) {
        //创建一个Map来记录每一个字符出现的数量
        Map<Byte, Integer> hashMap = new HashMap<>();
        List<Node> nodes = new ArrayList<>();
        //记录每一个字符对应的byte所出现的次数
        for (byte aByte : bytes) {
            hashMap.put(aByte, hashMap.getOrDefault(aByte, 0) + 1);
        }
        for (Map.Entry<Byte, Integer> byteIntegerEntry : hashMap.entrySet()) {
            nodes.add(new Node(byteIntegerEntry.getKey(), byteIntegerEntry.getValue()));
        }
        return nodes;
    }
    //生成一组赫夫曼编码
    //1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
    //   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    static Map<Byte, String> hashHuffman = new HashMap<>();
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便我们写一个方法的重载
    public static Map<Byte, String> getCode(Node node) {
        if (node == null) {
            return null;
        } else {
            //如果不为空那么就处理左子树
            getCode(node.leftNode, "0", stringBuilder);
            //处理右子树
            getCode(node.rightNode, "1", stringBuilder);
        }
        return hashHuffman;
    }
    /**
     * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
     *
     * @param node          传入结点
     * @param code          路径： 左子结点是 0, 右子结点 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCode(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node.data == null) {
            //先向左递归找
            getCode(node.leftNode, "0", stringBuilder1);
            //然后在右递归
            getCode(node.rightNode, "1", stringBuilder1);
        } else {
            //说明是一个子叶节点，就直接将对应的编码放入到节点当中
            hashHuffman.put(node.data, stringBuilder1.toString());
        }
    }
}
//重新创建一个Node
class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node leftNode;
    Node rightNode;
    //写一个前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

public class HuffmanCode {
    static int zeroCount= 0;
    public static void main(String[] args) {
        String s = "你好";
        byte[] zip = zip(s);
        System.out.println(new String (decode(hashHuffman, zip)));
    }
    public static byte[] zip(String s){
        //将这些封装成方法
        byte[] codeBytes = s.getBytes();
        Node node = creatHuffmanTree(getNodes(codeBytes));
        Map<Byte, String> hash = getCode(node);
        return zip(codeBytes,hash);
    }
    //通过hashHuffman来生成编码字符串,返回一个字节数组
    /**
     * @param contentsBytes 需要一个之前的传进来的原始字符串的bytes数组
     * @param hashHuffman   遍历之前的对应字符存入的编码
     * @return 返回一个压缩之后的Bytes数组
     */
    public static byte[] zip(byte[] contentsBytes, Map<Byte, String> hashHuffman) {
        StringBuilder stringBuilder = new StringBuilder();
        for (byte contentsByte : contentsBytes) {
            stringBuilder.append(hashHuffman.get(contentsByte));
        }
        System.out.println(stringBuilder);
        //拿到字符编码后，压缩为byte数组，返回一个byte数组
        //这里我们每八位作为一个字符
        int len = 0;
        if (stringBuilder.length() % 8 == 0){
            len = stringBuilder.length()/8;
        }else {
            len = stringBuilder.length()/8 + 1;
        }
        ////创建 存储压缩后的 byte数组
        byte[] bytes = new byte[len];
        int index = 0;
        //这里后移八位
        for (int i = 0; i < stringBuilder.length() ; i+=8) {
            //当后移八位的时候，如果长度不够继续就要进行一个判断，这样就能防止越界。
            String strByte;
            if (i+8 > stringBuilder.length()){
                strByte = stringBuilder.substring(i);
                for (int j = 0; j < strByte.length(); j++) {
                    if (strByte.length() == 1){
                        break;
                    }
                    if (strByte.charAt(j) == '0'){
                        zeroCount++;//记录当不够八位的时候是否要补零，补多少个零
                    }else {
                        break;
                    }
                }
            }else {
                strByte = stringBuilder.substring(i,i+8);
            }
            bytes[index++] = (byte) Integer.parseInt(strByte,2);
        }
        return bytes;
    }
    //构建赫夫曼树
    public static Node creatHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //先对nodes进行排序,使用collections工具类
            Collections.sort(nodes);
            //拿到前两个权值最小的节点
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //通过两个节点构成一个新的节点，注意注意只有最开始的节点有data，其他新构建的节点没有data
            Node parentNode = new Node(null, leftNode.weight + rightNode.weight);
            //清除前面两个节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //设置新节点的左右节点
            parentNode.leftNode = leftNode;
            parentNode.rightNode = rightNode;
            //添加新的节点
            nodes.add(parentNode);
        }
        return nodes.get(0);
    }
    //创建一个Arraylist,来存放每一个节点的数据
    public static List<Node> getNodes(byte[] bytes) {
        //创建一个Map来记录每一个字符出现的数量
        Map<Byte, Integer> hashMap = new HashMap<>();
        List<Node> nodes = new ArrayList<>();
        //记录每一个字符对应的byte所出现的次数
        for (byte aByte : bytes) {
            hashMap.put(aByte, hashMap.getOrDefault(aByte, 0) + 1);
        }
        for (Map.Entry<Byte, Integer> byteIntegerEntry : hashMap.entrySet()) {
            nodes.add(new Node(byteIntegerEntry.getKey(), byteIntegerEntry.getValue()));
        }
        return nodes;
    }
    //生成一组赫夫曼编码
    //1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
    //   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    static Map<Byte, String> hashHuffman = new HashMap<>();
    static StringBuilder stringBuilder = new StringBuilder();
    //为了调用方便我们写一个方法的重载
    public static Map<Byte, String> getCode(Node node) {
        if (node == null) {
            return null;
        } else {
            //如果不为空那么就处理左子树
            getCode(node.leftNode, "0", stringBuilder);
            //处理右子树
            getCode(node.rightNode, "1", stringBuilder);
        }
        return hashHuffman;
    }
    /**
     * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
     *
     * @param node          传入结点
     * @param code          路径： 左子结点是 0, 右子结点 1
     * @param stringBuilder 用于拼接路径
     */
    public static void getCode(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node.data == null) {
            //先向左递归找
            getCode(node.leftNode, "0", stringBuilder1);
            //然后在右递归
            getCode(node.rightNode, "1", stringBuilder1);
        } else {
            //说明是一个子叶节点，就直接将对应的编码放入到节点当中
            hashHuffman.put(node.data, stringBuilder1.toString());
        }
    }
    //编写一个方法，完成对压缩数据的解码
    /**
     *
     * @param huffmanCodes 赫夫曼编码表 map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    public static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes){
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag,b));
        }
        System.out.println(stringBuilder);
        Map<String,Byte> map = new HashMap<>();
        //把字符串按照指定的赫夫曼编码进行解码
        //把赫夫曼编码进行调换，因为反向查询a - > 100 就是转回原来的ASCII码
        for (Map.Entry<Byte, String> stringByteEntry : huffmanCodes.entrySet()) {
            map.put(stringByteEntry.getValue(),stringByteEntry.getKey());
        }
        //创建一个集合来存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i< stringBuilder.length();){
            int count = 1;//写到外面去的话这个count就不能置1了
            Byte b = null;
            boolean flag = true;
            while (flag){
                String s = stringBuilder.substring(i,i+count);
                b = map.get(s);
                if (b == null){
                    count++;
                }else {
                   flag = false;
                }
            }
            list.add(b);
            i += count;//这里就直接移动i到count的位置
        }
        byte[] bytes = new byte[list.size()];
        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = list.get(i);
        }
        return bytes;
    }
    /**
     * 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
     * @param b 传入的 byte
     * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
     * @return 是该b 对应的二进制的字符串，（注意是按补码返回）
     */
    public static String byteToBitString(boolean flag,byte b){
        int tmp = b;//将byte转为int
        if (tmp > 0){
            if (flag){//最后一位不用补位，前面只要不是负数就要补高位
            tmp |= 256;
        }}
        String s = Integer.toBinaryString(tmp);
        if (s.length() > 8){
            return s.substring(s.length() - 8);//取后八位
        }else {
            for (int i = 0; i < zeroCount; i++) {
                s = "0" + s;
            }
        }
        return s;
    }
}
//重新创建一个Node
class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node leftNode;
    Node rightNode;
    //写一个前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.leftNode != null) {
            this.leftNode.preOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.preOrder();
        }
    }
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

public static void zipFile(String sfcFile,String detFile){
        //创建输出流
        FileOutputStream os = null;
        //创建输入流
        FileInputStream in = null;
        //创建一个对象输出流
        ObjectOutputStream opj = null;
        try {
            in = new FileInputStream(sfcFile);
            //用一个byte数组去接受这个一个文件输入流
            byte[] fileBytes = new byte[in.available()];
            //将数据写入到byte数组中
            in.read(fileBytes);
            //压缩成赫夫曼编码
            byte[] bytes = HuffmanZip(fileBytes);
            //写入文件
            os = new FileOutputStream(detFile);
            opj = new ObjectOutputStream(os);
            //将byte写出
            opj.writeObject(bytes);
            //写入对应的huffman编码表,不然后续文件会恢复不了
            opj.writeObject(hashHuffman);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
public static void  Decompression(String sfcFile,String DFile){
        //创建对象输入流
        ObjectInputStream opi = null;
        //创建一个输出流
        FileOutputStream fo = null;
        //创建一个输入流
        InputStream ip = null;
        try {
            ip = new FileInputStream(sfcFile);
            opi = new ObjectInputStream(ip);
            //通过对象输出流拿到对应的bytes数组，对应的huffman编码
            byte[] bytes = (byte[]) opi.readObject();
            Map<Byte,String> huffmanCodes = (Map<Byte,String>) opi.readObject();
            //解码
            byte[] decode = decode(huffmanCodes, bytes);
            //写入到文件中
            fo = new FileOutputStream(DFile);
            fo.write(decode);
        } catch (Exception e) {
            e.printStackTrace();
        }finally {
            try {
                assert fo != null;
                fo.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

public class Graph {
    //创建一个二维数组来表示矩阵
    private int[][] edges;
    //创建一个Arraylist来保存顶点vertx的集合
    private ArrayList<String> vertxList;
    //来记录边的数量
    private int numOfEdges;
    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] Vertex = {"A","B","C","D","E"};
        for (String vertex : Vertex) {
            graph.insertVertex(vertex);
        }
        graph.insertEdges(0,1,1); //A-B
        graph.insertEdges(0,2,1);
        graph.insertEdges(1,0,1);
        graph.insertEdges(1,2,1);
        graph.insertEdges(1,3,1);
        graph.insertEdges(1,4,1);
        graph.insertEdges(2,0,1);
        graph.insertEdges(2,1,1);
        graph.insertEdges(3,1,1);
        graph.insertEdges(4,1,1);
        graph.showEdges();
    }
    //图常用的方法
    //返回结点的个数
    public int VertexNum(){
        return this.vertxList.size();
    }
    //返回边的条数
    public int EdgeNums(){
        return numOfEdges;
    }
    //返回对应的结点
    public String vertex(int i){
        return vertxList.get(i);
    }
    //返回对应节点的权值
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    //显示图对应的矩阵
    public void showEdges(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }
    public Graph(int n) {
        this.edges = new int[n][n];
        this.vertxList = new ArrayList<>(n);
        this.numOfEdges = 0;
    }
    //添加顶点的方法
    public void insertVertex(String vertex){
        vertxList.add(vertex);
    }
    //添加边
    /**
     *
     * @param v1 表示点的下标即是第几个顶点
     * @param v2 表示第二个顶点对应的下标
     * @param weight 表示每一个边的权值为1就表示两个点之间有连接，0就表示没有连接
     *
     *     A   B   C   D   E
     * A   0   1   1   0   0
     * B   1   0   1   1   1
     * C   1   1   0   0   0
     * D   0   1   0   0   0
     * E   0   1   0   0   0
     */
    public void insertEdges(int v1,int v2,int weight){
        this.edges[v1][v2] = weight;//这里就是表示两个顶点之间是否有边连接
        this.edges[v2][v1] = weight;
        numOfEdges++;
    }
}

//图的深度遍历
    //这里先访问他的第一个节点如果第一个节点没有访问到那么就返回-1，这里传入第一个节点
    public int getFirstNeighbor(int i){
        for (int j = 0; j < vertxList.size(); j++) {
            if (edges[i][j] > 0){
                return j;
            }
        }
        return -1;
    }
    //拿到当前节点的下一个节点
    public int getNextNeighbor(int v1,int v2){
        for (int i = v2 + 1; i < vertxList.size(); i++) {
            if (edges[v1][i] > 0 ){
                return i;
            }
        }
        return -1;
    }
/**
     *
     * @param v1 表示点的下标即是第几个顶点
     * @param v2 表示第二个顶点对应的下标
     * @param weight 表示每一个边的权值为1就表示两个点之间有连接，0就表示没有连接
     *
     *     A   B   C   D   E
     * A   0   1   1   0   0
     * B   1   0   1   1   1
     * C   1   1   0   0   0
     * D   0   1   0   0   0
     * E   0   1   0   0   0
     */
    //开始深度遍历
    public void dfs(boolean[] isVisited,int i){
        System.out.print(vertex(i));
        //先遍历第一个节点，再用isVisited保存证明遍历过
        isVisited[i] = true;
        //查找第第一个邻接节点
        int w = getFirstNeighbor(i);
        //然后在判断
        while(w != -1){//如果找到了他的一个邻接节点就找下一个邻接节点，就比如拿上图举例，当找到A的时候他的第一个邻接点为B，应为找到的w不为-1，这时进入while循环，在判断B点是否已经访问过，如果没有访问过就把B作为当前结点继续向下找到B的第一个邻接点，找到C但是C后面已经没有连结的节点了，就之间结束c的方法回溯到B，B就找他的相邻下一个节点(w = getNextNeighbor(i,w) 即这个方法)，找到了D，D也没有下一个节点，回溯到B，继续找到了E，然后相继输出.
            //继续判断C是否访问过，没有访问就继续
            if (!isVisited[w]){
                dfs(isVisited,w);
            }
            w = getNextNeighbor(i,w);
        }
    }
    public void dfs(){
        for (int i = 0; i < VertexNum(); i++) {
            //这里重载的原因是应为A的点的邻接节点B，连接了剩下的节点，如果B没有连接剩下的节点，dfs这个方法在A点没有找到剩下的节点的时候就会在A点直接结束，剩下的结点就不会再去遍历。
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

/**
     * 1. 访问初始结点v并标记结点v为已访问。
     * 2. 结点v入队列
     * 3. 当队列非空时，继续执行，否则算法结束。
     * 4. 出队列，取得队头结点u。
     * 5. 查找结点u的第一个邻接结点w。
     * 6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
     * 6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
     * 6.2 结点w入队列 。
     * 6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
     *
     * @param i 对应的第一个节点
     */
    public void bfs(boolean[] isVisited, int i) {
        int v;//表示第一个节点
        int w;//表示第一个节点的邻接点
        //先创建一个队列
        LinkedList<Integer> queue = new LinkedList<>();
        //输出第一个结点
        System.out.print(vertex(i) + "->");
        //标记第一个结点
        isVisited[i] = true;
        //结点入队列
        queue.addLast(i);
        while (!queue.isEmpty()) {
            v = queue.removeFirst();
            w = getFirstNeighbor(v);
            while (w != -1) {
                if (!isVisited[w]) {
                    //如果该节点没有被访问过就继续输出该节点,然后将该节点入列，然后继续寻找A后面的结点，直到A没有可以连接的结点为止
                   System.out.print(vertex(w)+"->");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(v, w);
            }
        }
    }
    //遍历所有的结点，都进行广度优先搜索
    public void bfs() {
        boolean[] isVisited = new boolean[n];
        for (int i = 0; i < VertexNum(); i++) {
            if (!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        int[] arr = {1,3,8,10, 11, 67, 100};
        System.out.println(binarySearch(arr, 3));
    }
    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length - 1;
        while (left <= right){
            int mid = (left + right)/2;
            if (arr[mid] == target){
                return mid;
            }else if (arr[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

public class HanoiTower {
    public static void main(String[] args) {
        new HanoiTower().Han(2,'A','B','C');
    }
    public void Han(int n,char a, char b , char c){
        if (n == 1){
            System.out.println("第一个盘"+a +"->"+ c );
        }else {
            //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
            //1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c,这里的c就是传入的'B'，因为第一个判断第一个盘移动
            Han(n-1,a,c,b);
            System.out.println("第" + n + "个盘从 " + a + "->" + c);
            //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔
            Han(n - 1, b, a, c);
        }
    }
}

package Algorithm;
public class KnapsackProblem {
    public static void main(String[] args) {
        //先定义物品重量
        int[] w ={1,4,3};
        //定义物品的价格
        int[] value = {1500,3000,2000};
        //定义物品的名称
        String[] name = {"鞋子","音响","电脑"};
        //定义背包的容量
        int packageCapacity = 4;
        //定义一个二维价格表
        int[][] v = new int[name.length+1][packageCapacity+1];
        // 构建可能装入背包的二维数组
        // 值为0时说明不会装进背包, 值为1说明可能装入背包
        int[][] content = new int[name.length+1][packageCapacity+1];
        for (int i = 1; i < v.length ; i++) {
            for (int j = 1; j < v[i].length; j++) {
                if (w[i-1] > j){//因为这里i是从1开始的所以v[i] -> v[i-1]
                    v[i][j] = v[i-1][j];//应为初始化的二位数组全是0最开始就不用进行初始化
                }else if (w[i-1] <= j){
                    int price = value[i-1];
                    int NewPrice = v[i-1][j-w[i-1]]+value[i-1];//这里的i-1在放入最后一个商品的时候，
                    // 如果还有剩余的空间就看前面表的重量放入当前商品后背包容量减去放入物品的容量剩下的容量在前面i-1物品的最大价值，在加上
                    // 能放入的最大商品重量对应的价格，就为背包的总价值。
                    //这个时候这个位置就是当前背包对应重量能拿到的最大值
                    v[i][j] = Math.max(price,NewPrice);
                    if (v[i][j] == NewPrice){
                        content[i][j] = 1;
                    }
                }
            }
        }
        //这里拿到最大的行,即最后一行
        int i = v.length-1;
        //这里拿到最大的列,也表示的是背包的容量
        int j = v[0].length -1;
        //总价钱
        int totalPrice = 0;
        while (i > 0 && j>0){
            if (content[i][j] == 1){
                j -= w[i -1];
                totalPrice += value[i-1];
                System.out.println(name[i-1]+"放入了背包");
            }
            i--;
        }
        System.out.println(totalPrice);
    }

public static int[] getNext(String s){
        //初始化j
        int j =0;
        //初始化next
        int[] next = new int[s.length()];
        next[0] = 0;
        //为了进行比较i从1开始
        for (int i = 1; i < s.length() ; i++) {
            //当j和i对应的字符不相等的时候，那么j就要向后回退,如果一直没有找到j就会退到最开始的位置
            while (j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j-1];//退回是核心代码。
            }
            //先考虑j和i相同的情况,例如"AA",j指向第一个A，i指向第二个i，这个时候j就要j++，这时候他们的最大相等前缀长度就是1
            if (s.charAt(j) == s.charAt(i)){
                j++;
            }
            next[i] = j;
        }
    return next;
    }

public class KMP {
    public static void main(String[] args) {
        String s1 = "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        int[] next = getNext("ABCDABD");
        System.out.println(Arrays.toString(next));
        System.out.println(KMPSearch(s1,s2,next));
    }
    //开始写Kmp
    public static int KMPSearch(String s1,String s2,int[] next){
        for (int i = 0, j = 0; i < s1.length(); i++) {
            //当两个字符串不相等的时候
            while (j > 0 && s1.charAt(i) != s2.charAt(j)){
                j = next[j-1];//当没有匹配到的时候就让j退回上一个最大前缀相等表的上一个值，再去判断j和i对应的字符是否相等。
            }
            //当两个字符串相等的时候
            if (s1.charAt(i) == s2.charAt(j)){
                j++;
            }
            if (j == s2.length()){
                return i-j+1;
            }
        }
        return -1;
    }
    //最大相等前缀表
    public static int[] getNext(String s){
        //初始化j
        int j =0;
        //初始化next
        int[] next = new int[s.length()];
        next[0] = 0;
        //为了进行比较i从1开始
        for (int i = 1; i < s.length() ; i++) {
            //当j和i对应的字符不相等的时候，那么j就要向后回退,如果一直没有找到j就会退到最开始的位置
            while (j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j-1];
            }
            //先考虑j和i相同的情况,例如"AA",j指向第一个A，i指向第二个i，这个时候j就要j++，这时候他们的最大相等前缀长度就是1
            if (s.charAt(j) == s.charAt(i)){
                j++;
            }
            next[i] = j;
        }
    return next;
    }
}

public class greedyAlgorithm {
    public static void main(String[] args) {
        //先创建一个hashset来存放所有的地区
        HashSet<String> allAreas = new HashSet<>();
        //创建每一个广播的地区
        HashSet<String> hashSet = new HashSet<>();
        HashSet<String> hashSet2 = new HashSet<>();
        HashSet<String> hashSet3 = new HashSet<>();
        HashSet<String> hashSet4 = new HashSet<>();
        HashSet<String> hashSet5 = new HashSet<>();
        hashSet.add("北京");
        hashSet.add("上海");
        hashSet.add("天津");
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        hashSet4.add("上海");
        hashSet4.add("天津");
        hashSet5.add("杭州");
        hashSet5.add("大连");
        //创建一个每一个广播对应的的地区
        HashMap<String,HashSet<String>> broadcasts = new HashMap<>();
        //将对应的广播地点传入map
        broadcasts.put("k1",hashSet);
        broadcasts.put("k2",hashSet2);
        broadcasts.put("k3",hashSet3);
        broadcasts.put("k4",hashSet4);
        broadcasts.put("k5",hashSet5);
        for (HashSet<String> value : broadcasts.values()) {
            allAreas.addAll(value);
        }
        //创建一个ArrayList来存放每一个广播站
        ArrayList<String> selects = new ArrayList<>();
        //定义一个临时的集合，在遍历的过程中存放当前电台没有覆盖的地区
        HashSet<String> tmpSet = new HashSet<>();
        while (allAreas.size() >0){//如果allAreas的长度不为0，说明还没有覆盖到全部地区就继续遍历直到覆盖所有的地区
            int maxTemp = 0;
            //定义一个maxKey来存放当前与要覆盖的地区交集最多的电台，如果有多个交集数量一致那么就取第一个
            String maxKey = null;
            for (String key : broadcasts.keySet()) {
                tmpSet.clear();//每一次使用完tmpSet都要清空！！！！
                HashSet<String> hashSet1 = broadcasts.get(key);
                //将当前key能够覆盖的地区都添加到临时的set中
                tmpSet.addAll(hashSet1);
                //求出tempSet 和 allAreas 集合的交集，交集会赋给tempSet
                tmpSet.retainAll(allAreas);
                //如果当tmp.size大于0那么就表明对应的key中还要没有覆盖到的地方
                //这里定义一个变量来记录最大的广播站交集。如果遍历到后面还有最大的交集数的话即tmpSet.size() > maxTemp,那么就继续交换
                if (tmpSet.size() > 0 && (maxKey == null || tmpSet.size() > maxTemp)){
                    maxKey = key;
                    maxTemp =tmpSet.size();
                }
            }
            //将找到的maxKey加入到选择当中去
            selects.add(maxKey);
            //然后再将广播能够覆盖到的地区移除
            allAreas.removeAll(broadcasts.get(maxKey));
            //将对应的maxKey删除
            broadcasts.remove(maxKey);
        }
        System.out.println(selects);
    }
}

public class primAlgorithm {
    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};
        int vertex = data.length;
        MGraph mGraph = new MGraph(vertex);
        minTree minTree = new minTree();
        minTree.GreatGraph(mGraph,vertex,weight,data);
        minTree.ShowGraph(mGraph);
        minTree.primTree(mGraph,0);
    }
}
class minTree{
    //传入一个MGraph
    private MGraph mGraph;
    //创建图的邻接矩阵
    /**
     *
     * @param mGraph 图对象
     * @param vertex 图对应的顶点个数
     * @param data 图的各个顶点的值
     * @param weight 图的邻接矩阵
     */
    public void GreatGraph(MGraph mGraph , int vertex ,int[][] weight,char[] data){
        int i,j;
        for (i = 0; i < vertex; i++) {
                mGraph.data[i] = data[i];
            for (j = 0; j < vertex; j++) {
                mGraph.weight[i][j] = weight[i][j];
            }
        }
    }
    //输出一个邻接矩阵
    public void ShowGraph(MGraph mGraph){
        for (int[] weight: mGraph.weight) {
            System.out.println(Arrays.toString(weight));
        }
    }
    /**
     *
     * @param mGraph 传入一个图
     * @param v  表明是从第几个节点开始
     */
    //编写prim算法，得到最小生成树
    public void primTree(MGraph mGraph,int v){
        //创建一个数组，来判断该节点是否访问过
        int[] isVisited = new int[mGraph.Vertex];
        //用0来表示未访问，应为java中创建的数组，默认值就为0所有就不需要初始化
        isVisited[v] = 1;
        //这两个变量，来标记是两个节点相连
        int h1 = -1;
        int h2 = -1;
        //然后人工定义一个最小的权值
        int minWeight = 10000;
        for (int k = 1; k < mGraph.Vertex;k++){//这里就是当prim算法结束后，就已经生成mGraph.Vertex 的顶点数减一条边
            for (int i = 0; i < mGraph.Vertex; i++) {// i结点表示被访问过的结点
                //这里就是从第一个顶点开始找和它相邻的两条边
                for (int j = 0; j < mGraph.Vertex; j++) {//j结点表示还没有访问过的结点
                    if (isVisited[i] == 1 && isVisited[j] == 0 && mGraph.weight[i][j] < minWeight ){
                        //替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
                        minWeight =mGraph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            //找到一条边是最小
            System.out.println("边<" + mGraph.data[h1] + mGraph.data[h2] + ">权值"+minWeight);
            //找到第一条边之后要将minWeight置为最大值
            minWeight = 10000;
            //就要将节点置为访问过
            isVisited[h2] = 1;
        }
    }
}
class MGraph{
    //确定顶点的个数
     int Vertex;
    //创建一个data来存放每一个顶点值
    char[] data;
    //创建每一个节点之间连接的权值
    int[][] weight;
    public MGraph(int vertex) {
        Vertex = vertex;
        this.data = new char[vertex];
        this.weight = new int[vertex][vertex];
    }
}

public class KruskalAlgorithm {
    //创建一个变量来表示最大的值，来表示不连通
    static final int INF = 1000;
    //创建一个vertex来存储顶点
    char[] vertex;
    //创建邻接矩阵
    int[][] weight;
    //记录每一条边的数量
    int edges;
    public static void main(String[] args) {
        char[] vertex = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weight = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {0, 12, INF, INF, INF, 16, 14},
                /*B*/ {12, 0, 10, INF, INF, 7, INF},
                /*C*/ {INF, 10, 0, 3, 5, 6, INF},
                /*D*/ {INF, INF, 3, 0, 4, INF, INF},
                /*E*/ {INF, INF, 5, 4, 0, 2, 8},
                /*F*/ {16, 7, 6, INF, 2, 0, 9},};
        new KruskalAlgorithm(vertex,weight).kruskal();
    }
    public KruskalAlgorithm(char[] vertex, int[][] weight) {
        this.vertex = vertex;
        this.weight = weight;
        //统计边的条数
        for (int i = 0;i<weight.length;i++) {
            for (int j = i+1 ; j < weight[i].length; j++) {
                if (weight[i][j]!= INF) {
                    edges++;
                }
            }
        }
    }
    public void kruskal() {
        int index = 0;//表示最后结果数组的索引
        int[] end = new int[edges];//用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
        //创建结果数组, 保存最后的最小生成树
        EData[] ret = new EData[edges];
        //获取所以的边的集合
        EData[] edge = getEdges();
        System.out.println(Arrays.toString(edge));
        //遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入
        for (int i = 0; i <edges ; i++) {
            //拿到对应顶点的下标
            int p1 = getPosition(edge[i].start);
            int p2 = getPosition(edge[i].end);
            //获取p1这个顶点在已有最小生成树中的终点
            int m = getEnd(end,p1);
            //获取p2这个顶点在已有最小生成树中的终点
            int n = getEnd(end,p2);
            if (m !=n){
                end[m] = n;// 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
                ret[index++] = edge[i];
            }
        }
        System.out.println(Arrays.toString(ret));
    }
    /**
     * 功能：对边进行排序处理, 冒泡排序
     * @param edges 边的集合
     */
    private void sortEdges(EData[] edges) {
        for (int i = 1;i < edges.length;i++){
            EData indexValue = edges[i];
            int index = i-1;
            while (index >= 0 && indexValue.weight < edges[index].weight){
                edges[index+1] = edges[index];
                index-=1;
            }
            edges[index+1] = indexValue;
        }
    }
    /**
     *
     * @param ch 顶点的值，比如'A','B'
     * @return 返回ch顶点对应的下标，如果找不到，返回-1
     */
    private int getPosition(char ch){
        for (int i = 0; i < vertex.length; i++) {
            if (ch == vertex[i]){
                return i;
            }
        }
        return -1;
    }
    /**
     * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
     * 是通过weight 邻接矩阵来获取
     * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
     * @return
     */
    private EData[] getEdges(){
        EData[] eData = new EData[edges];
        int index = 0;
        for (int i = 0; i < weight.length; i++) {
            for (int j = i+1; j < weight[i].length; j++) {
                if (weight[i][j] != INF){
                    eData[index++] = new EData(vertex[i],vertex[j],weight[i][j]);
                }
            }
        }
        sortEdges(eData);
        return eData;
    }
    /**
     * 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
     * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
     * @param i : 表示传入的顶点对应的下标
     * @return 返回的就是 下标为i的这个顶点对应的终点的下标
     */
    private int getEnd(int[] ends ,int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }
    public void print(){
        for (int[] ints : weight) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println();
    }
}
//这是来记录每一条边的权值
class EData{
    //起始点
    char start;
    //终点
    char end;
    //权值
    int weight;
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "EData{" +"<"+
                 start +","+ end + ">" +
                ", weight=" + weight + '}';
    }
}

public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
        new Graph(vertex, matrix).dsj(6);
    }
}
class Graph {
    char[] vertex;
    int[][] matrix;
    VisitedVertex vv;
    public Graph(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }
    public void print() {
        for (int[] m : matrix) {
            System.out.println(Arrays.toString(m));
        }
    }
    /**
     * @param index 表示起始点的下标
     */
    public void dsj(int index) {
        vv = new VisitedVertex(vertex.length, 6);
        //这里就是先初始化最开始的起点坐标
        updateDis(index);
        for (int i = 1; i < vertex.length ; i++) {
            int j = vv.updateArr();
            updateDis(j);
        }
        vv.show();
    }
    /**
    updateDis(int index)方法解释
    首先我们先定义一个len设置为0来表示初始的值
    然后我们遍历整个邻边矩阵
    将起始点周围可以联通的点的距离全部更新到dis中，
    然后在设置联通节点的前驱节点为当前的顶点。
    len = matrix[index][i] + vv.getLen(index);
    其中vv.getLen(index)中拿到的值就是之前起始点到最初各个顶点的距离，再加上各个顶点到其他点的距离，就是起始点到那个点的距离
    **/
    private void updateDis(int index) {
        int len = 0;
        for (int i = 0; i < matrix[index].length; i++) {
            // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
            len = matrix[index][i] + vv.getLen(index);
            if (!vv.in(i) && len < vv.getLen(i)){//这里就是要判断当前节点是否被访问过，并且两个节点之间的长度是要最短,不能改成||切记切记
                //如果改了，就是同一个节点距离不断重复的相加
                vv.updateDis(len, i);
                vv.updatePre(i, index);
            }
        }
    }
}
// 已访问顶点集合
class VisitedVertex {
    // 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新
    public int[] already_arr;
    // 每个下标对应的值为前一个顶点下标, 会动态更新
    public int[] pre_visited;
    // 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
    public int[] dis;
    /**
     * @param length 顶点的个数
     * @param index  起始点的下标
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];
        this.pre_visited = new int[length];
        this.dis = new int[length];
        Arrays.fill(dis, 65535);
        dis[index] = 0;
        already_arr[index] = 1;
    }
    /**
     * @param index 对应节点的下标
     * @return 判断该节点是否已经被访问过
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }
    /**
     * @param pre   要更新的节点
     * @param index 这个是pre对应的前驱节点的下标值
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }
    /**
     * @param len   跟对应的节点的长度
     * @param index 对应节点的下标
     */
    public void updateDis(int len, int index) {
        dis[index] = len;
    }
    /**
     * @param index 起始点和终点的对应下标值
     * @return 返回起始点和对应节点之间的距离
     */
    public int getLen(int index) {
        return dis[index];
    }
    /**
     *这里就是更新访问的节点，并且找到
     * @return 继续选择并且返回新的访问节点，比如G完后就是A点作为新的访问节点(注意不是新的起始点)
     */
    public int updateArr(){
        int min = 65535;
        int index = 0;
        for (int i = 0; i < already_arr.length;i++){
            if (already_arr[i] == 0 && dis[i] < min ){
                //判断当前节点是否被访问过，如果没有被访问过并且他的最小距离还最短就返回当前坐标的起始点
                min = dis[i];
                index = i;
            }
        }
        already_arr[index] = 1;
        return index;
    }
    public void show(){
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int index = 0;
        for (int di : dis) {
            if (di != 65535){
                System.out.println(vertex[index]+"===============" + di);
            }
            index++;
        }
    }
}

public class Floyd {
    public static void main(String[] args) {
        char[] vertex = {'A','B','C','D','E','F','G'};
        int[][] matrix = new int[vertex.length][];
        final int N = 65535;
        matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
        matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
        matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
        matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
        matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
        matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
        matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
        Graph graph = new Graph(vertex.length, vertex, matrix);
        graph.floyd();
        graph.show();
    }
}
class Graph{
    //先创建顶点的字符数组
    char[] vertex;
    //创建邻接矩阵
    int[][] matrix;
    //创建前驱节点，为了显示方便我这里直接用了char数组来进行展示
    char[][] pre;
    //初始化
    public Graph(int len ,char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
        this.pre = new char[len][len];
        for (int i = 0; i < vertex.length; i++) {
            Arrays.fill(pre[i],vertex[i]);
        }
    }
    public void show(){
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                System.out.print(pre[i][j]);
            }
            System.out.println();
            for (int j = 1+i; j < vertex.length; j++) {
                System.out.println(""+vertex[i]+"到"+vertex[j]+"最短的距离为"+matrix[i][j]);
            }
        }
    }
    public void floyd(){
        //先创建一个len表示长度
        int len =0;
        for (int k = 0; k < vertex.length; k++) {//对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G]
            for (int i = 0; i < vertex.length; i++) {//从i顶点开始出发 [A, B, C, D, E, F, G],表示的是起始点
                for (int j = 0; j < vertex.length; j++) {
                    //到达j顶点 // [A, B, C, D, E, F, G]终点
                    len = matrix[i][k] + matrix[k][j]; //=> 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离
                    if (len < matrix[i][j]){
                        matrix[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}

public class HorseChess {
    static int X;//来表示列
    static int Y;//来表示行
    static boolean[] visited;//用一个boolean数组来存放当前的格子是否被访问过
    static boolean flag = false;//来表示下一步能否继续走决定回溯
    public static void main(String[] args) {
        X = 6;
        Y = 6;
        int[][] chess = new int[Y][X];
        int row = 1;//马儿的行位置从1开始编号
        int col = 6;//马儿的列位置从1开始编号
        visited = new boolean[X*Y];//默认为false
        long time1 = System.currentTimeMillis();
        horseChess(chess,row-1,col-1,0);
        System.out.println(System.currentTimeMillis() - time1+"ms");
        for (int[] ints : chess) {
            for (int anInt : ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
    }
    /**
     *
     * @param chess 棋盘
     * @param row 马儿当前的位置行开始为0
     * @param col 马儿开始的位置的列开始为0
     * @param step 马儿开始的步数从1开始
     */
    public static void horseChess(int[][] chess,int row,int col,int step){
        //把马儿开始走的那一步在棋盘上标记出来
        chess[row][col] = step;
        //把马儿走的哪个位置标记起来
        visited[row * X + col] = true;
        //将这个起始点传进去拿到一个ps的集合
        ArrayList<Point> ps = next(new Point(col, row));
        //做一个排序减少回溯的次数
        ps.sort((x,y) -> next(x).size() - next(y).size());
        while (!ps.isEmpty()){
            Point p1 = ps.remove(0);//取出下一个访问的位置,应为ps中只有一个元素所以这里就是index填的是0
            if (!visited[p1.y * X+p1.x]){
                horseChess(chess,p1.y,p1.x,++step);//这里如果换成了++step，完全可以大大的提高算法运行的效率
                ++操作是速率最快的。
            }
        }
        //应该有可能执行到最后step的步数不一定可以满足要求所以这里就要进行应该判断
        if (step < X*Y && !flag){
            chess[row][col] = 0;//就将棋盘上对应的点给置为0
            visited[row * X + col] = false;//将这个访问的点从新设置为未访问
        }else {
            flag = true;
        }
    }
    public static ArrayList<Point> next(Point curPoint){
        //创建一个ArrayList来储存马能走的每一个点
        ArrayList<Point> ps = new ArrayList<>();
        //创建一个点
        Point p1 = new Point();
        //表示马儿可以走5这个位置
        if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走6这个位置
        if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走7这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走0这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走1这个位置
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走2这个位置
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走3这个位置
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //判断马儿可以走4这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
}