数据结构和算法
1. 数据结构
在计算机科学中，数据结构是计算机存储、组织数据的方式。
常见的数据结构有数组、链表、堆、栈、队列、散列表、树和图。
1.1. 数组
数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是 O(1)，中间插入、删除数组元素的时间复杂度是 O(n)。
数组随机读取和更新元素方便，插入和删除操作要移动元素或扩容，若是移动大量元素会影响效率。数组适合读操作多，写操作少的场景。
1.2. 链表
链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是 O（n），中间插入、删除节点的时间复杂度是 O(1)。
链表插入和删除操作灵活，读取只能顺序遍历无法快速定位元素。
1.3. 队列
队列是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队列包含入队和出队操作，遵循先入先出的原则（FIFO）。
1.4. 堆
堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。
1.5. 栈
栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含入栈和出栈操作，遵循先入后出的原则（FILO）。
1.6. 树
树是 n 个节点的有限集，有且仅有一个特定的称为根的节点。当 n>1 时，其余节点可分为 m 个互不相交的有限集，每一个集合本身又是一个树，称为根的子树。
1.6.1. 二叉树
二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式。
根据节点之间的位置关系遍历二叉树，可以分为前序遍历、中序遍历、后序遍历、层序遍历这4种方式；从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历两大类。
结构
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int val) {
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
前序遍历，根节点->左节点->右节点
private static void preOrderTraverse(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.val);
preOrderTraverse(node.left);
preOrderTraverse(node.right);
}
中序遍历，左节点->根节点->右节点
private static void middleOrderTraverse(TreeNode node) {
if (node == null) {
return;
}
middleOrderTraverse(node.left);
System.out.println(node.val);
middleOrderTraverse(node.right);
}
前序遍历，左节点->右节点->根节点
private static void afterOrderTraverse(TreeNode node) {
if (node == null) {
return;
}
afterOrderTraverse(node.left);
afterOrderTraverse(node.right);
System.out.println(node.val);
}
广度优先遍历，利用队列辅助实现
public static void levelOrderTraverse(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
深度优先遍历，可利用栈的回溯特性实现。
private static void preOderTraverseByStack(TreeNode node) {
Stack<TreeNode> stack = new Stack<>();
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.val);
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()) {
node = stack.pop();
node = node.right;
}
}
}
1.6.2. 二叉堆
二叉堆本质上是一种完全二叉树，它分为最小堆和最大堆两种类型，见以上堆介绍。
堆的插入操作是单一节点的“上浮”，堆的删除操作是单一节点的“下沉”，这两个操作的平均交换次数都是堆高度的一半，所以时间复杂度是 O（logn）。堆的构建是吧一个完全无序的二叉树调整为二叉堆，本质是让所有非叶子节点依次“下沉”，时间复杂度是 O（n）。
插入上浮
/**
* 插入操作，上浮调整
*/
public static void upAdjust(int[] array) {
int childIndex = array.length - 1;//插入节点下标，数组最后一个元素
/**
* 计算父节点下标
* 若当前是左节点，父节点下标为（节点下标-1）/2
* 若当前是右节点，减1为奇数，（节点下标-1）/2 向下取整结果也等于左节点的情况
*/
int parentIndex = (childIndex - 1)/2;
int temp = array[childIndex];//调整的数
while (childIndex>0 && temp < array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (parentIndex - 1)/2;
}
array[childIndex] = temp;
}
删除或构建下沉
/**
* 下沉调整
* 删除操作，最后一个元素替换一个元素再做下沉操作
* @param array 源数组
* @param parentIndex 要调整节点的父节点下标
* @param length 数组长度
*/
public static void downAdjust(int[] array, int parentIndex, int length) {
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;//左节点
//判断是否属于数组
while (childIndex < length) {
//判断右节点是否小于左节点，成立定位到右节点
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex ++;
}
//父节点小于任意子节点，不必操作
if (temp <= array[childIndex]) {
break;
}
//父大于子，下沉
array[parentIndex] = array[childIndex];
//继续下一层遍历判断
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
array[parentIndex] = temp;
}
/**
* 构建堆，所有非叶子节点依次做下沉操作
* @param array
*/
public static void buildHeap(int[] array) {
for (int i = (array.length-2)/2; i >= 0; i--) {
downAdjust(array, i, array.length);
}
}
1.6.3. 优先队列
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的。
每一次入队操作就是堆的插入操作，，每一次出队操作就是删除堆顶节点。
import java.util.Arrays;
public class PriorityQueue {
private int[] array;
private int size;
public PriorityQueue() {
array = new int[32];
}
//入队
public void enQueue(int key) {
if (size > array.length) {
//扩容
resize();
}
array[size++] = key;
//上浮操作
upAdjust();
}
//出队
public int deQueue() throws Exception{
if (size <= 0) throw new Exception("empty queue...");
//堆顶元素
int head = array[0];
//最后一个元素替代
array[0] = array[--size];
//下沉操作
downAdjust();
return head;
}
/**
* 入队插入上浮
*/
private void upAdjust() {
int childIndex = size - 1;
int parentIndex = (childIndex - 1) / 2;
int temp = array[childIndex];
while (childIndex > 0 && temp > array[parentIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = parentIndex / 2;
}
array[childIndex] = temp;
}
/**
* 出队删除下沉
*/
private void downAdjust() {
int parentIndex = 0;
int temp = array[parentIndex];
int childIndex = 1;
while (childIndex < size) {
if (childIndex + 1 < size && array[childIndex+1] > array[childIndex]) {
childIndex++;
}
if (temp > array[childIndex]) break;
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
array[parentIndex] = temp;
}
private void resize() {
int newSize = size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}
public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(10);
priorityQueue.enQueue(5);
priorityQueue.enQueue(2);
priorityQueue.enQueue(8);
System.out.println(Arrays.toString(priorityQueue.array));
System.out.println("出队" + priorityQueue.deQueue());
System.out.println("出队" + priorityQueue.deQueue());
System.out.println(Arrays.toString(priorityQueue.array));
priorityQueue.enQueue(1);
priorityQueue.enQueue(12);
System.out.println(Arrays.toString(priorityQueue.array));
}
}
1.7. 散列表
哈希表也叫散列表，是存储 Key-Value 映射的集合。对于某一个 Key，哈希表可以在接近 O(1)的时间内进行读写操作。哈希表通过哈希函数实现 Key 和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。
散列表本身是一个数组，需要通过哈希函数把Key进行处理以确定元素存放位置的数组下标。在 Java 中，每个对象都有自己的 hashcode，所以简单的计算方式可以按数组长度进行取模运算
JDK 哈希函数不是直接使用取模运算，而是利用了位运算的方式来优化性能
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1.8. 图
在计算机科学中，图（英语：graph）是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。
图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。
2. 算法
计算机中一系列程序指令，用于处理特定的运算和逻辑问题。
2.1. 算法复杂度
2.1.1. 时间复杂度
常数时间操作：
- 算数运算：+ - * /
-
位运算：>>（带符号右移动）、 >>>（不带符号右移动） 、 <<、 | 、& 、^
带符号就是最高位补符号位，不带符号就是最高位补0 -
赋值操作：比较，自增，自减操作
-
数组寻址等
总之，执行时间固定的操作都是常数时间的操作。反之执行时间不固定的操作，都不是常数时间的操作
通过基本动作的常数时间，推导时间复杂度
对于双层循环来说，n（常数）+ (n-1)(常数)+ ... + 2(常数) + 1（常数） => 推导出
y = an^2 + bn + c
忽略掉低阶项，忽略掉常数项，忽略掉高阶项的系数，得到时间复杂度为 n^2。
2.1.2. 空间复杂度
申请有限几个变量，和样本量n没关系，就是空间复杂度 O(1)，如果要开辟一个空间数组和样本量 n 是一样大，用来支持我们的算法流程那么 O(N)。反之用户就是要实现数组拷贝，我们开辟一个新的 n 大小数组用来支撑用户的需求，那么仍然是 O(1)。
2.2. 排序算法
排序是最常见的一类算法，按照复杂度和稳定性不同
| 算法 | 稳定性 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | √ | O(N2) | O(N2) | O(1) | |
| 选择排序 | × | O(N2) | O(N2) | O(1) | |
| 插入排序 | √ | O(N2) | O(N2) | O(1) | 时间复杂度和初始顺序有关，最好是O(n) |
| 希尔排序 | × | O(nlogn)~O(N2) | O(N2) | O(1) | 改进版插入排序 |
| 快速排序 | × | O(NlogN) | O(N2) | O(logN) | |
| 归并排序 | √ | O(NlogN) | O(NlogN) | O(N) | |
| 堆排序 | × | O(NlogN) | O(NlogN) | O(1) | 无法利用局部性原理 |
2.2.1. 冒泡排序
从小大排序，循环遍历数组，相邻元素互相比较，若右边元素大于左边元素则交换位置，这样每次会按照最大从右端递减排列。
/**
* time: O(n^2) 两个循环n*n
* space: O(1) 变量大小都不变为1
* @param arr
* @return
*/
public static int[] bubbleSort(int[] arr) {
for (int i=0; i<arr.length; i++) {
for (int j=0; j<arr.length-i-1; j++) {
if (arr[j+1] < arr[j]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
/**
* 优化
* 1、不到 i-1 轮数组已经排完序不需要继续
* 2、后区间有序不需要每次再比较
*/
public static int[] bubbleSortPlus(int[] arr) {
//最后一次交换的位置
int lastExchangeIndex = 0;
//无序数列的边界，每次比较只需要到这里位置
int sortBorder = arr.length - 1;
for (int i=0; i<arr.length; i++) {
//有序标记，每一轮的初始值都是 true
boolean isSorted = true;
for (int j=0; j<sortBorder; j++) {
if (arr[j+1] < arr[j]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
//有交换，不是有序
isSorted = false;
//变更为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) break;
}
return arr;
}
2.2.2. 选择排序
遍历数组，每次选择最小的元素交换
/**
* time: O(n^2) 两个循环n*n
* space: O(1) 变量大小都不变为1
* @param arr
* @return
*/
public static int[] selectionSort(int[] arr) {
for (int i=0; i<arr.length-1; i++) {
int index = i;
for (int j=i+1; j<arr.length; j++) {
if (arr[j] < arr[index]) {
index = j;
}
}
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
return arr;
}
2.2.3. 插入排序
/**
* time: O(n^2) 两个循环n*n
* space: O(1) 变量大小都不变为1
* @param arr
* @return
*/
public static int[] insertionSort(int[] arr) {
for (int i=1; i<arr.length; i++) {
int value = arr[i];
int index = i;
for (int j=i-1; j>=0; j--) {
if (arr[j] > value) {
arr[j+1] = arr[j];
//arr[j] = value;
index = j;
} else break;
}
arr[index] = value;
}
return arr;
}
/**
* while 写法
*/
public static int[] insertionSortWhile(int[] arr) {
for (int i=1; i<arr.length; i++) {
int value = arr[i];
int index = i;
while (index > 0 && arr[index-1] > value) {
arr[index] = arr[index-1];
index--;
}
arr[index] = value;
}
return arr;
}
2.2.4. 快速排序
又称分区交换排序，使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
- 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
- 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
- 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
public static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partition = partition(arr, left, right);//基准值
quickSort(arr, left, partition-1);
quickSort(arr, partition+1, right);
}
return arr;
}
// 分区操作，单边操作
public static int partition(int[] arr, int left, int right) {
int pivot = left;// 设定基准值（pivot）
int index = pivot + 1;
//从第二个开始查找
for (int i = index; i <= right; i++) {
//当前值小于基准值
if (arr[i] < arr[pivot]) {
//交换当前值和开始值
swap(arr, i, index);
index++;
}
}
//最后将基准值和
swap(arr, pivot, index - 1);
return index-1;//基准值目前位置
}
//交换
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
2.2.5. 归并排序
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
递归方式实现
private static void mergeSortRecursive(int[] arr, int[] result, int start, int end) {
if (start >= end) return;
//左边数组结尾
int mid = ((end - start)>>1) + start;
int start1 = start, end1 = mid;
int start2 = mid+1, end2 = end;
mergeSortRecursive(arr, result, start1, end1);
mergeSortRecursive(arr, result, start2, end2);
int k = start;
/**
* 合并两个数组，遍历比较两个数组，谁小谁放入排序数组并移一位，然后继续比较，直到其中一个数组遍历完毕为止
* 明显遍历完毕的数组会有 start > end
*/
while (start1 <= end1 && start2 <= end2) {
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
//左边数组未遍历完的情况，剩余元素直接合并入排序数组
while (start1 <= end1) {
result[k++] = arr[start1++];
}
//右边数组未遍历完的情况，剩余元素直接合并入排序数组
while (start2 <= end2) {
result[k++] = arr[start2++];
}
//回写出栈返回给上一层递归
for (int i = start; i <= end; i++) {
arr[i] = result[i];
}
}
public static void mergeSort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
mergeSortRecursive(arr, result, 0, len-1);
}
2.2.6. 堆排序
根据二叉堆的特性，通过调整二叉堆所得到的集合就会成为一个有序集合。堆排序的最坏时间复杂度是 O(N2)，空间复杂度是 O(1)。
public static void sort(int[] arr) {
//构建最大堆
for (int i = (arr.length-2)/2; i >= 0; i--) {
downAdjust(arr, i, arr.length);
}
for (int i=arr.length-1; i>=0; i--) {
int tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
downAdjust(arr, 0, i);
}
}
public static void downAdjust(int[] array, int parentIndex, int length) {
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;//左节点
//判断是否属于数组
while (childIndex < length) {
//判断右节点是否小于左节点，成立定位到右节点
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex ++;
}
//父节点小于任意子节点，不必操作
if (temp <= array[childIndex]) {
break;
}
//父大于子，下沉
array[parentIndex] = array[childIndex];
//继续下一层遍历判断
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
array[parentIndex] = temp;
}
2.2.7. 计数排序
计数排序使用一个额外的数组，利用数组下标确定元素位置，根据统计数组输出排序数组。计数排序的时间复杂度是 O(n+m)，空间复杂度是 O(m)。
计数排序有一些局限性，当数列最大和最小值差距过大时，或者数列元素不是整数时，都不适合计数排序。
public static int[] sort(int[] arr) {
//先遍历找到最大值
int maxVal = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxVal)
maxVal = arr[i];
}
//根据最大值确定统计数组长度
int[] countArr = new int[maxVal + 1];
//遍历填充
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
//根据统计数组生成排序数组
int[] sortedArr = new int[arr.length];
int index = 0;
for (int i = 0; i < countArr.length; i++) {
for (int j = 0; j < countArr[i]; j++) {
sortedArr[index++] = i;
}
}
return sortedArr;
}
优化版本，以最大值-最小值+1作为统计数组的长度，数列的最小值作为一个偏移量，并将统计数组的第2个元素开始，每一个元素都加上前面所有元素之和，最终统计数组存储的元素值就是相应整数的最终排序位置的序号，这样就能直接定位排序数组元素的下标并设置值。
public static int[] sort1(int[] arr) {
//先遍历找到最大值和最小值
int maxVal = arr[0], minVal = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxVal)
maxVal = arr[i];
if (arr[i] < minVal)
minVal = arr[i];
}
//遍历填充
int[] countArr = new int[maxVal - minVal + 1];
for (int i = 0; i < arr.length; i++) {
//要减去偏移量
countArr[arr[i] - minVal]++;
}
//改变统计数组，后面元素等于前面元素之和
for (int i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i-1];
}
//倒叙遍历原始数组，找到元素在统计数组的位置并设值
int[] sortedArr = new int[arr.length];
for (int i = arr.length-1; i >= 0; i--) {
sortedArr[countArr[arr[i] - minVal] - 1] = arr[i];
countArr[arr[i] - minVal]--;
}
return sortedArr;
}
2.2.8. 桶排序
桶排序是一种线性时间的排序算法，类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。桶排序的总体时间复杂度是 O(n)，空间复杂度也是 O(n)。
public static double[] sort(double[] arr) {
double max = arr[0];
double min = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max)
max = arr[i];
if (arr[i] < min)
min = arr[i];
}
double d = max -min;
int bucketNum = arr.length;
//初始化桶
ArrayList<LinkedList<Double>> bucketLists = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketLists.add(new LinkedList<>());
}
//遍历原始数组，将元素放入桶中
for (int i = 0; i < arr.length; i++) {
//计算所在桶下标
int index = (int) ((arr[i] - min) * (bucketNum - 1) / d);
bucketLists.get(index).add(arr[i]);
}
//桶内部排序
for (int i = 0; i < bucketLists.size(); i++) {
Collections.sort(bucketLists.get(i));
}
double[] sortedArr = new double[arr.length];
int index = 0;
for (LinkedList<Double> bucketList : bucketLists) {
for (Double aDouble : bucketList) {
sortedArr[index++] = aDouble;
}
}
return sortedArr;
}
2.3. 贪心算法
贪心算法（英语：greedy algorithm），又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
2.4. 递归算法
递归算法（recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。
2.5. 跳表
即跳跃表（skiplist），是一种随机化的数据，以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。
Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合健的底层实现。
2.6. 动态规划
动态规划（英語：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划在查找有很多重叠子问题的情况的最优解时有效，一般形式是求最值，核心问题是穷举。
动态规划问题一定会具备最优子结构，通过子问题的最值得到原问题的最值。列出正确的状态转移方程是解动态规划问题的关键，同样也是难点。
2.7. 广度优先搜索和深度优先搜索
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
参考 - [1] 堆 - 维基百科，自由的百科全书 - [2] 漫画算法：小灰的算法之旅 - [3] 归并排序 - 维基百科，自由的百科全书 - [4] 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）