【递归与非递归实现：】
    使用递归实现时，系统隐式的维护了一个栈 用于操作节点。虽然递归代码易理解，但是对于系统的性能会造成一定的影响。
    使用非递归代码实现，可以主动去维护一个栈 用于操作节点。非递归代码相对于递归代码，其性能可能会稍好（数据大的情况下）。
注：
    栈是先进后出（后进先出）结构，即先存放的节点后输出（后存放的节点先输出）。
    所以使用栈时，需要明确每一步需要压入的树节点。
    递归实现二叉树 前序、中序、后序遍历。可参考：https://www.cnblogs.com/l-y-h/p/13751459.html#_label5_2

【非递归实现前序遍历：】
    前序遍历顺序：当前节点（父节点）、左子节点、右子节点。
实现思路：
    首先明确一点，每次出栈的树节点即为当前需要输出的节点（第一个输出的节点为 根节点）。
    
    每次首先输出的为 当前节点（父节点），所以父节点先入栈、再出栈。
    出栈之后，需要重新选择出下一次需要输出的父节点。从当前节点的 左、右子节点中选择。
    而左子节点需要在 右子节点前输出，所以右子节点需要先进栈，然后左子节点再进栈。
    左子节点入栈后，再次出栈即为当前节点，然后重复上面操作，依次取出栈顶元素即可。
    
步骤：
    Step1：根节点入栈。
    Step2：根节点出栈，此时为当前节点，输出或者保存。
        Step2.1：若当前节点存在右子节点，则压入栈。
        Step2.2：若当前节点存在左子节点，则压入栈。
    Step3：重复 Step2，依次取出栈顶元素并输出，栈为空时，则树遍历完成。    
    
【非递归前序遍历代码实现：】
package com.lyh.tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeSort<K> {
    /**
     * 前序遍历（非递归实现、使用栈模拟递归）
     */
    public List<K> prefixList(TreeNode9<K> root) {
        // 使用集合保存最终结果
        List<K> result = new ArrayList<>();
        // 根节点不存在时，返回空集合
        if (root == null) {
            return result;
        }
        // 使用栈模拟递归
        Stack<TreeNode9<K>> stack = new Stack<>();
        // 根节点入栈
        stack.push(root);
        // 栈非空时，依次取出栈顶元素，此时栈顶元素为当前节点，输出，并将当前节点 左、右子节点入栈
        // 左子节点 先于 右子节点出栈，所以左子节点在 右子节点入栈之后再入栈
        while(!stack.isEmpty()) {
            // 取出栈顶元素（当前节点）
            TreeNode9<K> tempNode = stack.pop();
            // 保存（或者输出）当前节点
            result.add(tempNode.data);
            // 存在右子节点，则压入栈
            if (tempNode.right != null) {
                stack.push(tempNode.right);
            }
            // 存在左子节点，则压入栈
            if (tempNode.left != null) {
                stack.push(tempNode.left);
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // 构建二叉树
        TreeNode9<String> root = new TreeNode9<>("0");
        TreeNode9<String> treeNode = new TreeNode9<>("1");
        TreeNode9<String> treeNode2 = new TreeNode9<>("2");
        TreeNode9<String> treeNode3 = new TreeNode9<>("3");
        TreeNode9<String> treeNode4 = new TreeNode9<>("4");
        root.left = treeNode;
        root.right = treeNode2;
        treeNode.left = treeNode3;
        treeNode.right = treeNode4;
        // 前序遍历
        System.out.print("前序遍历： ");
        System.out.println(new BinaryTreeSort<String>().prefixList(root));
        System.out.println("\n=====================");
    }
}
class TreeNode9<K> {
    K data; // 保存节点数据
    TreeNode9<K> left; // 保存节点的 左子节点
    TreeNode9<K> right; // 保存节点的 右子节点
 
    public TreeNode9(K data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "TreeNode9{ data= " + data + "}";
    }
}
【输出结果：】
前序遍历： [0, 1, 3, 4, 2]

【非递归实现中序遍历：】
    中序遍历顺序：左子节点、当前节点、右子节点。
实现思路：
    首先明确一点，每次出栈的树节点即为当前需要输出的节点（第一次输出的节点为 最左侧节点）。
    由于每次都要先输出当前节点的最左侧节点，所以需要遍历找到这个节点。
    而在遍历的过程中，每次经过的树节点均为 父节点，可以使用栈保存起来。
    此时，找到并输出最左侧节点后，就可以出栈获得父节点，然后根据父节点可以找到其右子节点。
    将右子节点入栈，同理找到其最左子节点，并重复上面操作，依次取出栈顶元素即可。
注：
    为了防止重复执行父节点遍历左子节点的操作，可以使用辅助变量记录当前操作的节点。
    
步骤：
    Step1：记当前节点为根节点，从根节点开始，遍历找到最左子节点，并依次将经过的树节点入栈。
    Step2：取出栈顶元素，此时为最左子节点（当前节点），输出或者保存。
        Step2.1：若存在右子节点，则当前节点为 父节点，将右子节点入栈，并修改新的当前节点为 右子节点。遍历当前节点，同理找到最左子节点，并依次将经过的节点入栈。
        Step2.2：若不存在右子节点，则当前节点为 左子节点，下一次取得的栈顶元素即为 父节点。
    Step3：重复上面过程，输出顺序即为 左、根、右。
    
【非递归中序遍历代码实现：】
package com.lyh.tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeSort<K> {
    /**
     * 中序遍历（非递归实现，使用栈模拟递归）
     */
    public List<K> infixList(TreeNode9<K> root) {
        // 使用集合保存遍历结果
        List<K> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 保存当前节点
        TreeNode9<K> currentNode = root;
        // 使用栈模拟递归实现
        Stack<TreeNode9<K>> stack = new Stack<>();
        while(!stack.isEmpty() || currentNode != null) {
            // 找到当前节点的左子节点，并依次将经过的节点入栈
            while(currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            // 取出栈顶元素
            TreeNode9<K> tempNode = stack.pop();
            // 保存栈顶元素
            result.add(tempNode.data);
            // 存在右子节点，则右子节点入栈，
            if (tempNode.right != null) {
                currentNode = tempNode.right;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // 构建二叉树
        TreeNode9<String> root = new TreeNode9<>("0");
        TreeNode9<String> treeNode = new TreeNode9<>("1");
        TreeNode9<String> treeNode2 = new TreeNode9<>("2");
        TreeNode9<String> treeNode3 = new TreeNode9<>("3");
        TreeNode9<String> treeNode4 = new TreeNode9<>("4");
        root.left = treeNode;
        root.right = treeNode2;
        treeNode.left = treeNode3;
        treeNode.right = treeNode4;
        // 前序遍历
        System.out.print("中序遍历： ");
        System.out.println(new BinaryTreeSort<String>().infixList(root));
        System.out.println("\n=====================");
    }
}
class TreeNode9<K> {
    K data; // 保存节点数据
    TreeNode9<K> left; // 保存节点的 左子节点
    TreeNode9<K> right; // 保存节点的 右子节点
 
    public TreeNode9(K data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "TreeNode9{ data= " + data + "}";
    }
}
【输出结果：】
中序遍历： [3, 1, 4, 0, 2]

【非递归实现后序遍历：】
    后序遍历顺序：左子节点、右子节点、当前节点。
实现思路：
    首先明确一点，每次出栈的树节点即为当前需要输出的节点（第一次输出的节点为最左侧节点）。
    
    这里与 中序遍历还是有点类似的，同样是先输出最左侧节点。区别在于，后序遍历先输出 右子节点，再输出父节点。
    同样使用一个变量，用来辅助遍历，防止父节点重复遍历子节点。
    此处的变量，可以理解成上一次节点所在位置。而栈顶取出的当前节点为上一次节点的父节点。
步骤：
    Step1：根节点入栈。
    Step2：取出栈顶元素（当前节点），判断其是否存在子节点。
        Step2.1：存在左子节点，且未被访问过，左子节点入栈（此处为遍历找到最左子节点）。
        Step2.2：存在右子节点，且未被访问过，右子节点入栈。
        Step2.3：不存在 或者 已经访问过 左、右子节点，输出当前节点。
    Step3：重复以上操作，直至栈空。        
    
【非递归后序遍历代码实现：】
package com.lyh.tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeSort<K> {
    /**
     * 后序遍历（非递归实现，使用栈模拟递归）
     */
    public List<K> suffixList(TreeNode9<K> root) {
        // 使用集合保存遍历结果
        List<K> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 保存当前节点
        TreeNode9<K> currentNode = root;
        // 使用栈模拟递归实现
        Stack<TreeNode9<K>> stack = new Stack<>();
        // 根节点入栈
        stack.push(root);
        // 依次取出栈顶元素
        while(!stack.isEmpty()) {
            // 取出栈顶元素
            TreeNode9<K> tempNode = stack.peek();
            // 若当前节点 左子节点 存在，且未被访问，则入栈
            if (tempNode.left != null && currentNode != tempNode.left && currentNode != tempNode.right) {
                stack.push(tempNode.left);
            } else if (tempNode.right != null && currentNode != tempNode.right){
                // 若当前节点 右子节点存在，且未被访问，则入栈
                stack.push(tempNode.right);
            } else {
                // 当前节点不存在 左、右子节点 或者 左、右子节点已被访问，则取出栈顶元素，
                // 并标注当前节点位置，表示当前节点已被访问
                result.add(stack.pop().data);
                currentNode = tempNode;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        // 构建二叉树
        TreeNode9<String> root = new TreeNode9<>("0");
        TreeNode9<String> treeNode = new TreeNode9<>("1");
        TreeNode9<String> treeNode2 = new TreeNode9<>("2");
        TreeNode9<String> treeNode3 = new TreeNode9<>("3");
        TreeNode9<String> treeNode4 = new TreeNode9<>("4");
        root.left = treeNode;
        root.right = treeNode2;
        treeNode.left = treeNode3;
        treeNode.right = treeNode4;
        // 前序遍历
        System.out.print("后序遍历： ");
        System.out.println(new BinaryTreeSort<String>().suffixList(root));
        System.out.println("\n=====================");
    }
}
class TreeNode9<K> {
    K data; // 保存节点数据
    TreeNode9<K> left; // 保存节点的 左子节点
    TreeNode9<K> right; // 保存节点的 右子节点
 
    public TreeNode9(K data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "TreeNode9{ data= " + data + "}";
    }
}
【输出结果：】
后序遍历： [3, 4, 1, 2, 0]

【一颗 M 阶的 B 树特点：（M 阶指的是最大节点的子节点个数）】
    每个节点最多有 M 个子节点（子树）。
    根节点存在  0 个或者 2 个以上子节点。
    非叶子节点 若存在 j 个子节点，那么该非叶子节点保存 j - 1 个数据项，且按照递增顺序存储。
    所有的叶子节点均在同一层。
注：
    B 树是一个平衡多路查找树，具有与 平衡二叉树 类似的特点，
    区别在于 B 树分支更多，从而构建出的树高度低。
    当然 B 树也不能无限制的增大 树的阶，阶约大，则非叶子节点保存的数据项越多（变成了一个有序数组，增加查找时间）。

【2-3 树特点：】
对于 2 节点：
    只能包含一个数据项 和 两个子节点（或者没有子节点）。
    左子节点值 小于 当前节点值，右子节点值 大于 当前节点值。
    不存在只有一个子节点的情况。
对于 3 节点：
    包含一大一小两个数据项（从小到大排序） 和 三个子节点（或者没有子节点）。
    左子节点值 小于 当前节点数据项最小值，右子节点值 大于 当前节点数据项最大值，中子节点值 在 当前节点数据项值之间。
    不存在有 1 子节点、2 个子节点的情况。

【B+ 树特点：】
   所有 数据项（关键字） 均存放于 叶子节点。
   每个叶子节点 存放的 数据项（关键字）是有序的。
   所有叶子节点使用链表相连（即进行范围查询时，只需要查找到 首尾节点、然后遍历链表 即可）。
注：
    所有数据项（关键字） 均存放与 叶子节点组成的链表中，且数据有序，可以视为稠密索引。
    非叶子节点 相当于 叶子节点的索引，可以视为 稀疏索引。

【B* 树与 B+ 树 节点分裂的区别：】
对于 B+ 树：
    B+ 树 节点的最低使用率是 1/2，其非叶子节点关键字（数据项）个数至少为 (1/2)*M。M 为 B+ 树的阶。
    当一个节点存放满时，会增加一个节点，并将原节点 1/2 的数据移动到新的节点，然后在 父节点 添加新的节点。
    B+ 树 只影响 原节点 以及 父节点，不会影响兄弟节点，兄弟之间不需要指针。
    
对于 B* 树：
    B* 树 节点的最低使用率为 2/3，其非叶子节点关键字（数据项）个数至少为 (2/3)*M。
    当一个节点存放满时，若其下一个兄弟节点未满，则将一部分数据移到兄弟节点中，在原节点 添加新节点，然后修改 父节点 中的节点（兄弟节点发生改变）。
    若其下一个兄弟已满，则在 两个兄弟之间 增加一个新节点，并分别从两个兄弟节点中 移动 1/3 的数据到新节点，然后在 父节点 添加新的节点。
    B* 树 影响了 兄弟节点，所以需要指针将兄弟节点连接起来。
    
总的来说，B* 树分配新节点的概率比 B+ 树低，B* 树的节点利用率更高。
    
注：
    相关内容参考：https://blog.csdn.net/wyqwilliam/article/details/82935922

【B 树 或者 B- 树：】
    平衡的多路查找树，非叶子节点至少存储 (1/2)*M 个关键字（数据项），
    关键字升序存储，且仅出现一次，
    进行查找匹配操作时，可以在 非叶子节点 成功匹配。
    
【B+ 树：】
    B 树的变种，仅在 叶子节点 保存数据项，且叶子节点之间 通过链表存储。
    整体 数据项 有序存储。
    非叶子节点 作为 叶子节点 的索引存在，匹配时通过 非叶子节点 快速定位到 叶子节点，然后在 叶子节点 处进行匹配操作，相当于进行 二分查找。
    
【B* 树：】
    B+ 树的变种，给 非叶子节点 也加上指针，非叶子节点 至少存储 (2/3)*M 个关键字。
    将节点利用率 从 1/2 提高到 2/3 。

【常用快速查找的数据结构有两种：】
哈希表：
    比如 HashMap，其查找、添加、删除、修改的平均时间复杂度均为 O(1)
树：
    比如 平衡二叉树，其查询、添加、删除、修改的平均时间复杂度均为O(logn)
    
【什么是哈希表？】
    哈希表（Hash table 、散列表），是根据键（Key）直接访问数据（Value）的一种数据结构。
规则：
   使用某种方式（映射函数）将键值（Key）映射到数组中的某个位置，并在此位置存放记录，用于加快查询速度。
   映射函数 也称为 散列函数，存放记录的数组 称为 散列表。
   
理解：
    使用 散列函数，将 键值（Key）转换为一个 整型数字，
    然后再对数字进行转换（取模、与运算等），将其转为 数组对应的下标，并将 value 存储在该下标对应的存储空间中。
    而进行查询操作时，再次对 Key 进行运算，转换为对应的数组下标，即可定位并获取 value 值（时间复杂度为 O(1)）。
        
【为什么不使用 哈希表？】
    对于 单次写操作或者读操作 来说，哈希的速率比树快，但是为什么不用哈希表呢？
    可以想一下如果是排序或者范围查询的情况下，执行哈希是什么情况，很显然，哈希无法很快的进行范围查找（其数据都是无序的），查找范围 0~n 的情况下，会执行 n 次查找，也即时间复杂度为 O(n)。
    
    而树（AVL树、B树、B+树等）是有序的（1、2 次查找即可），其时间复杂度仍可以保证在 O(logn)。
    
    相比较之下，哈希肯定没有树的效率高，因此不会使用哈希这种数据结构作为索引。
    
【平衡二叉树时间复杂度 O(logn) 怎么来的？】
    在树中查找一个数字时，第一次在树的第一层（根节点）判断，第二次在树的第二层判断，依次类推，树有多少层，就会进行多少次判断，即对于 k 层的树，最坏时间复杂度为O(k)。
    所以只需要知道 n 个节点的树有多少层即可。
    若为满二叉树（除叶子节点外，每个节点均有两个节点），则对于第一层，有一个节点（2^0），对于第二层有两个节点（2^1），依次类推对于第 k 层有 2^k-1（2 的 k-1 次方）。
    所以 n = 2^0 + 2^1 + ... + 2^k-1，从而 k = log(n + 1)。
    所以时间复杂度为 O(k) = O(logn)     k 为树 层数，n 为树 节点数。

【查看 InnoDB 默认页大小：】
    SHOW GLOBAL STATUS like 'Innodb_page_size';

【首先明确一点：】
    B+ 树 非叶子节点存储的是 主键（关键字）+ 指针（指向叶子节点）。
    B+ 树 叶子节点存储的是 数据（真实的数据记录）。
    假设每次读取一个节点均会执行一次磁盘 I/O，即每个节点大小为页的大小。
【以节点大小为 16KB 为例：】
假设一行数据大小为 1KB，那么一个叶子节点能保存 16 条记录。
假设非叶子节点主键为 bigint 类型，那么长度为 8B，而指针在 InnoDB 中大小为 6B，即一个非叶子节点能保存 16KB / 14B = 1170 个数据（主键 + 指针）。
那么对于 高度为 2 的 B+树，能存储记录数为： 1170 * 16 = 18720 条。
对于 高度为 3 的 B+树，能存储记录数为：1170 * 1170 * 16 = 21902400 条。
也就是说，若页大小为 16KB，那么高度为 3 的 B+ 树就能支持 2千万的数据存储。
当然若页大小更大，树的高度也会低，但是一般没有必要去修改。
读取一个节点需要经过一次磁盘 I/O，那么根据主键 只需要 1-3 次磁盘 I/O 即可查询到数据，能满足绝大部分需求。

【构建思路：】
    使用 一维数组 记录 图的顶点数据。
    使用 二维数组 记录 图的各顶点的联系（边，其中 1 表示存在边，0 表示不存在边）。
【代码实现：】
package com.lyh.chart;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 使用 邻接矩阵 形式构建无向图
 */
public class UndirectedGraph {
    private List<String> vertexs; // 用于保存 无向图 的顶点数据（可以使用一维数组）
    private int[][] edges; // 用于保存 无向图 中各顶点之间的关系，1 表示两顶点之间存在边，0 表示不存在边
    private int numberOfEdges; // 用于记录 无向图中边的个数
 
    /**
     * 根据 顶点个数 进行初始化
     * @param number 顶点个数
     */
    public UndirectedGraph(int number) {
        vertexs = new ArrayList<>(number); // 用于记录顶点
        edges = new int[number][number]; // 用于记录顶点之间的关系
        numberOfEdges = 0; // 用于记录边的个数
    }
    /**
     * 添加顶点
     * @param vertex 顶点
     */
    public void insertVertex(String vertex) {
        vertexs.add(vertex);
    }
    /**
     * 添加边
     * @param row 行
     * @param column 列
     * @param value 值（1 表示存在边，0表示不存在边）
     */
    public void insertEdge(int row, int column, int value) {
        edges[row][column] = value; // 设置边
        edges[column][row] = value; // 设置边，对称
        numberOfEdges++; // 边总数加 1
    }
    /**
     * 返回边的总数
     * @return 边的总数
     */
    public int getNumberOfEdges() {
        return numberOfEdges;
    }
    /**
     * 返回顶点的总数
     * @return 顶点总数
     */
    public int getNumberOfVertex() {
        return vertexs.size();
    }
    /**
     * 返回 下标对应的顶点数据
     * @param index 顶点下标
     * @return 顶点数据
     */
    public String getValueByIndex(int index) {
        return vertexs.get(index);
    }
    /**
     * 输出邻接矩阵
     */
    public void showGraph() {
        for (int[] row : edges) {
            System.out.println(Arrays.toString(row));
        }
    }
    public static void main(String[] args) {
        // 初始化无向图
        UndirectedGraph undirectedGraph = new UndirectedGraph(5);
        // 插入顶点数据
        String[] vertexs = new String[]{"A", "B", "C", "D", "E"};
        for (String vertex : vertexs) {
            undirectedGraph.insertVertex(vertex);
        }
        // 插入边
        undirectedGraph.insertEdge(0, 1, 1); // A-B
        undirectedGraph.insertEdge(0, 2, 1); // A-C
        undirectedGraph.insertEdge(1, 2, 1); // B-C
        undirectedGraph.insertEdge(1, 3, 1); // B-D
        undirectedGraph.insertEdge(1, 4, 1); // B-E
        // 输出
        System.out.println("无向图顶点总数为： " + undirectedGraph.getNumberOfVertex());
        System.out.println("无向图边总数为： " + undirectedGraph.getNumberOfEdges());
        System.out.println("无向图第 3 个顶点为： " + undirectedGraph.getValueByIndex(2));
        System.out.println("无向图 邻接矩阵为： ");
        undirectedGraph.showGraph();
    }
}
【输出结果为：】
无向图顶点总数为： 5
无向图边总数为： 5
无向图第 3 个顶点为： C
无向图 邻接矩阵为： 
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]

【步骤：】
Step1：访问初始节点 start，标记该节点 start 已访问。
Step2：查找节点 start 的第一个邻接节点 neighbor。
  Step2.1：若 neighbor 不存在，则返回 Step1，且从 start 下一个节点继续执行。
  Step2.2：若 neighbor 存在，且未被访问，则返回 Step1，且将 neighbor 视为新的 start 执行。
  Step2.3：若 neighbor 存在，且已被访问，则返回 Step2，且从 neighbor 下一个节点继续执行。
【举例：】
图的 邻接矩阵表示如下：,图各顶点 按照顺序为 A B C D E。
      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]
注：
    1 表示两个顶点间存在边，0 表示不存在边。
则遍历过程如下：（整个过程是纵向的）
Step1：从 A 开始遍历，将 A 标记为 已访问。找到 A 的 第一个邻接节点 B。
Step2：B 未被访问，将 B 视为新的节点开始遍历，将 B 标记为已访问，找到 B 的第一个邻接节点 A。
Step3：A 被访问过，继续查找 B 下一个邻接节点为 C。
Step4：C 未被访问过，将 C 视为新节点开始遍历，将 C 标记为已访问，找到 C 的第一个邻接节点 A。
Step5：A 被访问，继续查找 C 下一个邻接节点为 B，B 也被访问，继续查找，C 没有邻接节点，回退到上一层 B。
Step6：继续查找 B 下一个邻接节点为 D，将 D 标记已访问，同理可知 D 没有 未被访问的邻接顶点，回退到上一层 B。
Step7：查找 B 下一个邻接节点为 E，将 E 标记已访问，至此遍历完成。
即顺序为：A -> B -> C -> D -> E
【代码实现：】
package com.lyh.chart;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 使用 邻接矩阵 形式构建无向图
 */
public class UndirectedGraph {
    private List<String> vertexs; // 用于保存 无向图 的顶点数据（可以使用一维数组）
    private int[][] edges; // 用于保存 无向图 中各顶点之间的关系，1 表示两顶点之间存在边，0 表示不存在边
    private int numberOfEdges; // 用于记录 无向图中边的个数
    private boolean[] isVisit; // 用于记录 顶点是否被访问，true 表示已访问
 
    /**
     * 根据 顶点个数 进行初始化
     * @param number 顶点个数
     */
    public UndirectedGraph(int number) {
        vertexs = new ArrayList<>(number); // 用于记录顶点
        edges = new int[number][number]; // 用于记录顶点之间的关系
        numberOfEdges = 0; // 用于记录边的个数
        isVisit = new boolean[number]; // 用于记录顶点是否被访问
    }
    /**
     * 添加顶点
     * @param vertex 顶点
     */
    public void insertVertex(String vertex) {
        vertexs.add(vertex);
    }
    /**
     * 添加边
     * @param row 行
     * @param column 列
     * @param value 值（1 表示存在边，0表示不存在边）
     */
    public void insertEdge(int row, int column, int value) {
        edges[row][column] = value; // 设置边
        edges[column][row] = value; // 设置边，对称
        numberOfEdges++; // 边总数加 1
    }
    /**
     * 返回边的总数
     * @return 边的总数
     */
    public int getNumberOfEdges() {
        return numberOfEdges;
    }
    /**
     * 返回顶点的总数
     * @return 顶点总数
     */
    public int getNumberOfVertex() {
        return vertexs.size();
    }
    /**
     * 返回 下标对应的顶点数据
     * @param index 顶点下标
     * @return 顶点数据
     */
    public String getValueByIndex(int index) {
        return vertexs.get(index);
    }
    /**
     * 输出邻接矩阵
     */
    public void showGraph() {
        for (int[] row : edges) {
            System.out.println(Arrays.toString(row));
        }
    }
    /**
     * 获取下一个顶点的下标
     * @param row 行
     * @param column 列
     * @return 下一个邻接顶点的下标（-1 表示不存在下一个邻接顶点）
     */
    public int getNeighborVertexIndex(int row, int column) {
        for (int index = column + 1; index < vertexs.size(); index++) {
            if (edges[row][index] != 0) {
                return index;
            }
        }
        return -1;
    }
    /**
     * 返回当前顶点 的第一个邻接顶点的下标
     * @param index 当前顶点下标
     * @return 第一个邻接顶点的下标（-1 表示不存在邻接顶点）
     */
    public int getFirstVertextIndex(int index) {
        return getNeighborVertexIndex(index, -1);
    }
    /**
     * 深度优先遍历
     */
    public void dfs() {
        // 未被访问的顶点，进行深度优先遍历
        for (int index = 0; index < vertexs.size(); index++) {
            if (!isVisit[index]) {
                dfs(index);
            }
        }
    }
    /**
     * 深度优先遍历
     * @param index 顶点下标
     */
    private void dfs(int index) {
        // 输出当前顶点数据
        System.out.print(getValueByIndex(index) + " ==> ");
        // 标记当前顶点为 已访问
        isVisit[index] = true;
        // 获取当前顶点第一个邻接顶点下标
        int neighborIndex = getFirstVertextIndex(index);
        // 当下一个邻接顶点存在时
        while(neighborIndex != -1) {
            // 若邻接顶点未被访问，则递归遍历
            if (!isVisit[neighborIndex]) {
                dfs(neighborIndex);
            } else {
                // 若邻接顶点已被访问，则访问当前邻接顶点的下一个邻接顶点
                neighborIndex = getNeighborVertexIndex(index, neighborIndex);
            }
        }
    }
    public static void main(String[] args) {
        // 初始化无向图
        UndirectedGraph undirectedGraph = new UndirectedGraph(5);
        // 插入顶点数据
        String[] vertexs = new String[]{"A", "B", "C", "D", "E"};
        for (String vertex : vertexs) {
            undirectedGraph.insertVertex(vertex);
        }
        // 插入边
        undirectedGraph.insertEdge(0, 1, 1); // A-B
        undirectedGraph.insertEdge(0, 2, 1); // A-C
        undirectedGraph.insertEdge(1, 2, 1); // B-C
        undirectedGraph.insertEdge(1, 3, 1); // B-D
        undirectedGraph.insertEdge(1, 4, 1); // B-E
        // 输出
        System.out.println("无向图顶点总数为： " + undirectedGraph.getNumberOfVertex());
        System.out.println("无向图边总数为： " + undirectedGraph.getNumberOfEdges());
        System.out.println("无向图第 3 个顶点为： " + undirectedGraph.getValueByIndex(2));
        System.out.println("无向图 邻接矩阵为： ");
        undirectedGraph.showGraph();
        System.out.println("深度优先遍历结果为： ");
        undirectedGraph.dfs();
    }
}
【输出结果：】    
无向图顶点总数为： 5
无向图边总数为： 5
无向图第 3 个顶点为： C
无向图 邻接矩阵为： 
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
深度优先遍历结果为： 
A ==> B ==> C ==> D ==> E ==>

【步骤：】
Step1：访问初始节点 start，并标记为 已访问，start 入队列。
Step2：循环取出队列，若队列为空，则结束循环，否则执行下面步骤。
Step3：取得队列头部节点，即为 first，并查找 first 的第一个邻接节点 neighbor。
  Step3.1：若 neighbor 不存在，则返回 Step2，再取出队列 新的头节点。
  Step3.2：若 neighbor 存在，且未被访问，则将其标记为 已访问并入队列。
  Step3.3：若 neighbor 存在，且已被访问，则返回 Step3，并查找 neighbor 的下一个节点。
注：
    Step3 将某一层 未访问的节点 入队列，当该层顶点全部被访问时，执行 Step2，
    从队列中取出 头部节点，即为 新的层，并开始查找未被访问的节点入队列。
【举例：】
图的 邻接矩阵表示如下：,图各顶点 按照顺序为 A B C D E。
      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]
注：
    1 表示两个顶点间存在边，0 表示不存在边。
则遍历过程如下：（整个过程是横向分层的）
Step1：从 A 开始，将其标记为 已访问，将 A 存入队列末尾。
Step2：取出队列头部元素为 A，查找其邻接节点为 B，B 未被访问将其入队列、并标记为 已访问。
Step3：继续查找 A 下一个邻接节点为 C，C 为被访问将其入队列、并标记为 已访问。
Step4：A 层遍历结束，取出队列头部为元素为 B，即开始访问 B 层。
Step5：B 层未被访问的节点 依次入队列并标记为已访问。即 D、E 入队列。
Step6：同理依次取出队列头部元素 C、D、E，直至遍历完成。
即顺序为：A -> B -> C -> D -> E
【代码实现：】
package com.lyh.chart;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
 * 使用 邻接矩阵 形式构建无向图
 */
public class UndirectedGraph {
    private List<String> vertexs; // 用于保存 无向图 的顶点数据（可以使用一维数组）
    private int[][] edges; // 用于保存 无向图 中各顶点之间的关系，1 表示两顶点之间存在边，0 表示不存在边
    private int numberOfEdges; // 用于记录 无向图中边的个数
    private boolean[] isVisit; // 用于记录 顶点是否被访问，true 表示已访问
 
    /**
     * 根据 顶点个数 进行初始化
     * @param number 顶点个数
     */
    public UndirectedGraph(int number) {
        vertexs = new ArrayList<>(number); // 用于记录顶点
        edges = new int[number][number]; // 用于记录顶点之间的关系
        numberOfEdges = 0; // 用于记录边的个数
        isVisit = new boolean[number]; // 用于记录顶点是否被访问
    }
    /**
     * 添加顶点
     * @param vertex 顶点
     */
    public void insertVertex(String vertex) {
        vertexs.add(vertex);
    }
    /**
     * 添加边
     * @param row 行
     * @param column 列
     * @param value 值（1 表示存在边，0表示不存在边）
     */
    public void insertEdge(int row, int column, int value) {
        edges[row][column] = value; // 设置边
        edges[column][row] = value; // 设置边，对称
        numberOfEdges++; // 边总数加 1
    }
    /**
     * 返回边的总数
     * @return 边的总数
     */
    public int getNumberOfEdges() {
        return numberOfEdges;
    }
    /**
     * 返回顶点的总数
     * @return 顶点总数
     */
    public int getNumberOfVertex() {
        return vertexs.size();
    }
    /**
     * 返回 下标对应的顶点数据
     * @param index 顶点下标
     * @return 顶点数据
     */
    public String getValueByIndex(int index) {
        return vertexs.get(index);
    }
    /**
     * 输出邻接矩阵
     */
    public void showGraph() {
        for (int[] row : edges) {
            System.out.println(Arrays.toString(row));
        }
    }
    /**
     * 获取下一个顶点的下标
     * @param row 行
     * @param column 列
     * @return 下一个邻接顶点的下标（-1 表示不存在下一个邻接顶点）
     */
    public int getNeighborVertexIndex(int row, int column) {
        for (int index = column + 1; index < vertexs.size(); index++) {
            if (edges[row][index] != 0) {
                return index;
            }
        }
        return -1;
    }
    /**
     * 返回当前顶点 的第一个邻接顶点的下标
     * @param index 当前顶点下标
     * @return 第一个邻接顶点的下标（-1 表示不存在邻接顶点）
     */
    public int getFirstVertextIndex(int index) {
        return getNeighborVertexIndex(index, -1);
    }
    /**
     * 广度优先遍历
     */
    public void bfs() {
        // 未被访问的顶点，进行广度优先遍历
        for (int index = 0; index < vertexs.size(); index++) {
            if (!isVisit[index]) {
                bfs(index);
            }
        }
    }
    /**
     * 广度优先遍历
     * @param index 顶点下标
     */
    private void bfs(int index) {
        // 输出当前顶点数据
        System.out.print(getValueByIndex(index) + " ==> ");
        // 用于记录访问的顶点
        LinkedList<Integer> queue = new LinkedList<>();
        int firstIndex; // 用于记录队列的头部节点
        int neighborIndex; // 用于记录邻接节点
        isVisit[index] = true; // 标记当前节点已被访问
        queue.addLast(index); // 当前节点入队列
        // 队列不空时
        while(!queue.isEmpty()) {
            // 取出队列头节点
            firstIndex = queue.removeFirst();
            // 找到邻接节点
            neighborIndex = getFirstVertextIndex(index);
            while(neighborIndex != -1) {
                if(!isVisit[neighborIndex]) {
                    // 输出当前顶点数据
                    System.out.print(getValueByIndex(neighborIndex) + " ==> ");
                    isVisit[neighborIndex] = true;
                    queue.addLast(neighborIndex);
                } else {
                    neighborIndex = getNeighborVertexIndex(firstIndex, neighborIndex);
                }
            }
        }
    }
    public static void main(String[] args) {
        // 初始化无向图
        UndirectedGraph undirectedGraph = new UndirectedGraph(5);
        // 插入顶点数据
        String[] vertexs = new String[]{"A", "B", "C", "D", "E"};
        for (String vertex : vertexs) {
            undirectedGraph.insertVertex(vertex);
        }
        // 插入边
        undirectedGraph.insertEdge(0, 1, 1); // A-B
        undirectedGraph.insertEdge(0, 2, 1); // A-C
        undirectedGraph.insertEdge(1, 2, 1); // B-C
        undirectedGraph.insertEdge(1, 3, 1); // B-D
        undirectedGraph.insertEdge(1, 4, 1); // B-E
        // 输出
        System.out.println("无向图顶点总数为： " + undirectedGraph.getNumberOfVertex());
        System.out.println("无向图边总数为： " + undirectedGraph.getNumberOfEdges());
        System.out.println("无向图第 3 个顶点为： " + undirectedGraph.getValueByIndex(2));
        System.out.println("无向图 邻接矩阵为： ");
        undirectedGraph.showGraph();
        System.out.println("广度优先遍历结果为： ");
        undirectedGraph.bfs();
    }
}
【输出结果：】
无向图顶点总数为： 5
无向图边总数为： 5
无向图第 3 个顶点为： C
无向图 邻接矩阵为： 
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
广度优先遍历结果为： 
A ==> B ==> C ==> D ==> E ==>