图的 m 着色问题 一、描述 给定无向连通图 G 和 m 种不同的颜色. 用这些颜色为图 G 的各顶点着色, 每个顶点着一种颜色. 是否有一种着色法使 G 中每条边的 2 个顶点着不同颜色. 这个问题是图的 m 可着色判定问题. 若一个图最少需要 m 种颜色才能使图中每条边连接的 2 个顶点着不同颜色, 则称这个数 m 为该图的色数. 二、解决思路 可以把这个问题的解空间转换为高度

图的广度优先遍历 一、描述 从随机一个节点出发, 访问该节点所有的邻接节点. 访问后的节点(包括第一个节点)对其进行标记, 若节点未被访问则添加到队列中. 若队列中存在元素就将其出队, 并用上述的方法重复过程. 二、举例 目前存在一个图如下所示 假设从 2 这个节点开始遍历, 2 先标记为访问后入队. 此时队列中有 2 就出队访问 0 和 3, 同时这两个数标记后入队. 0

整数矩阵及其运算 一、描述 在最开始的时候已经做过相关的工作, 只不过那会是面向过程的编码. 今天这里的步骤就是把面向过程改为面向对象. 矩阵对象的创建. getRows 等: getter, setter 在 java 里面很常用. 主要是为了访问控制. 整数矩阵的加法、乘法. Exception 的抛出与捕获机制. 用 this 调用其它的构造方法以减少冗余代码. ge

Huffman 编码 (建树) 一、描述 在之前的基础上增加了两个函数. 一个是构建字母表 constructAlphabet() , 另一个就是通过字母表来建立起 Huffman 树 constructTree(). 二、构建字母表 1. 三部分 完整的字母映射其实是需要存储出现字符和每个字符出现次数的两个辅助结构才能达到查询的目的. 在代码中这三部分使用三个数组来表示. 分别是

Hanoi 塔问题 一、描述 有三根杆子A, B, C. A 杆上有 N 个 ( N > 1 ) 穿孔圆盘, 盘的尺寸由下到上依次变小. 要求按下列规则将所有圆盘移至 C 杆: 每次只能移动一个圆盘; 大盘不能叠在小盘上面. 提示: 可将圆盘临时置于 B 杆, 也可将从 A 杆移出的圆盘重新移回 A 杆, 但都必须遵循上述两条规则. 问: 如何移? 最少要移动多少次 ? 二、

二叉树深度遍历的栈实现 (中序) 中序遍历在之前是用递归的方式来实现的, 递归的本质就是栈. 只不过递归使用的是系统提供的栈, 当然我们也可以编写手工栈来实现之前系统栈的功能. 这就是这一节需要完成的任务. 那么第一个任务就是编写一个栈. 一、具有通用性的对象栈 简而言之就是把之前的字符栈转变为适合于所有数据结构的对象栈, 其中方法也和之前的大同小异. 这里新增了判断栈是否为空的代码

使用具有通用性的队列 一、描述 之前使用的队列有两种: 存储二叉树节点的队列; 存储整数的队列. 这样的话, 难道我们要为每种类型单独写一个队列? 这样显然没有充分利用代码的复用性. 实际上, 我们只需要一个存储对象的队列就够啦! 这个问题在之前总结的时候就已经提到了. Java 里面, 所有的类均为 Object 类的 (直接或间接) 子类. 如果不写就默认为直接子类. 例如