算法理论基础01
前言与基础概念
- 前言
本文谨代表个人在算法学习中的一点粗浅理解，如有疏漏与错误，还请各位大佬不吝赐教。时间有限，本文中部分示例代码为伪代码，还请谅解。
图片来源于互联网，如有侵权，请联系我删除。
- 算法是什么？
算法，是对于解决问题方法的规则总结。以有限的步骤（有穷性），根据输入（含有输入）成功解决逻辑或数学上的问题（可行性），给出确定的（确定性）输出（含有输出）。
广义而言，我们所编写的每个程序都是一个算法，从复杂的STL到简单的输出一句helloworld,其中包含的每个函数也都是一个算法，毕竟它们都是用来解决或大或小的逻辑问题或数学问题。我们常常讨论的排序、查找、组合的方法，由于其对不同问题广泛的适应性，组成了狭义理解上的计算机算法。
特定的算法往往搭配特定的数据结构，算法与数据结构相辅相成。
- 算法的自检验
在解决实际问题的时候，我们无法像考试一样去使用标准答案检验算法，但是我们知道正确的算法应该怎么工作运行。所以，我们可以自己创建数据。计算机中，所有的信息被表示为0和1，我们也可以将所有的业务数据抽象为数字。一维数组表示一维数据，二维数组表示拓扑与图，三维数组表示空间信息，我们可以按规则生成足够信息量的数据作为校验算法的输入。
同时，我们只需要一个可能不那么优秀，但是绝对正确的算法，就可以使用对比结果的方式检验当前算法的正确性。
具体的实施方式在获得实际的算法返回值后，通过一项项的数据比对，分析当前算法是否满足了要求。当然，在实际的使用中，我们可以对多次的结果取加权期望，或是引入合理的误差范围以及非法输入，从而加强我们对当前运行算法的检验。
以上就是数据发生器和对数器概念的实际应用。
我们以一个最简单的例子，来演示自检验的工作流程。
首先，写一个一维随机数发生器。
注意，我们不鼓励使用rand函数，不管它多么经典，但是使用rand始终无法改变伪随机带来的一系列问题，我们更鼓励使用现代C++的方式发生随机数。
bool getRandomArraySafe(std::vector<int>& ioArray, int minValue, int maxValue,
int minLength, int maxLength)
{
bool res = false;
if (minValue > maxValue || minLength > maxLength || minLength < 0)//不符合随机值发生要求
{ return res; }
ioArray.clear();
std::random_device rd;//产生种子
std::mt19937 gen(rd());//梅森引擎
std::uniform_int_distribution<int> arraysizes(minLength, maxLength);//均匀分布
std::uniform_int_distribution<int> arrayvalues(minValue, maxValue);
int arraysize = arraysizes(gen);
int arrayvalue;
while (arraysize > ioArray.size())
{
arrayvalue = arrayvalues(gen);
ioArray.emplace_back(arrayvalue);
}
res = true;
return res;
}
通过随机发生的数据进行算法校验，例如我们可以使用冒泡排序校验快速排序。
这里我们可以使用简单的比较来检验函数的正确性。
template<typename T>
inline bool IsSame(std::vector<T>& ioArray1, std::vector<T>& ioArray2)
{
bool res = true;
if (ioArray1.size() != ioArray2.size()) return false;
for (size_t i = 0; i < ioArray1.size(); i++)
{
if (ioArray1[i] != ioArray2[i])
{
res = false;
break;
}
}
return res;
}
由于我们需要大量的运算资源去完成算法的自检验，所以它更多的使用在较为底层的框架函数中。
- 算法的复杂度与稳定度
对于算法的评价是多维度的，常见的评价方式为复杂度与稳定度。
在明确时间复杂度的概念之前，我们必须明确一个规则。那就是复杂度存在的前提。我们假设计算机执行单一运算的时间相同，并不考虑硬件结构上的不同导致的运行差异。即我们认为，世界上所有类型的计算机都是标准计算机，其执行的单一运算（如加法、减法、乘法）均为标准运算，所花费的时间也是相同的。
所以，我们将时间复杂度定义为对某一标准输入数据执行某一算法后，所需要的时间长短。
可以被等价为，对某一标准数据输入执行某一算法后，所需要的步骤次数。
同样的，空间复杂度也被视为申请单位空间的次数，所以大部分时候仍然可以近似的替代为申请存储空间的次数。
当然，如果是对算法复杂度较为苛求的场合，不再适用以上估算准则。
对于上述估算结果，我们以如下三个标记描述他：
：给出了算法运行时间的上界，也就是最坏情况下的时间复杂度；
：给出了算法运行时间的上界和下界，这里Θ(f(n))是渐近的确界。
：给出了算法运行时间的下界，也就是最好情况下的时间复杂度；
总之，我们在算法研究中，主要讨论，在工程应用中，还会考虑。
除了算法的复杂度之外，算法稳定度也是衡量算法的一个指标。
算法的稳定性并不是针对复杂度的稳定性，而是针对使用完该算法之后，数据之间的结构是否还有稳定性。（如原始数据中就有4个2，排完之后这4个2之间的次序是否还是一致的），在大部分情况下，一个算法是否稳定往往被我们视为是一种算法的特征，他可以简单的被回答是或者否。
下图是排序算法的复杂度和稳定性表
- 算法的“模板化”
我们这里提到的，不是具体的方法或者算法的模板化，而是算法思想的模板化。
例如分治法，它作为一种常使用的算法思想，被应用在各种各样不同的算法中我们可以在排序中见到它（快速排序），在搜索中见到它（二分搜索）在动态规划中见到它，在多线程优化的算法中见到它，这里的分治思想，其实就是算法思想模板化的体现。
这里的分治算法思想，不仅仅是一种抽象的概念，也是可以被文字或者数学所定义的过程。
例如我们可以使用master公式尝试描述分治法的原理。
其公式的推导如下图：
可以看到，分治法的中心思想在于将一个整体的问题分解为b个子问题进行求解。当然，这里的公式仅仅是描述了最为简单的一种情况，即一个问题的解可以被拆分为b个相同子问题的解。
但是，通过不断的实践与归纳，我们可以大胆地总结为只要整体问题的解可以被分为同一种或者有限种不同子问题的解，就可以尝试分治思想的使用。类似的思想还有深度优先、广度优先、递归调用、科学归纳、迭代收敛等等。
当然，也有的书籍并不支持这样的划分，但是这样的思想对于我们学习算法和解决问题却是相当高效且可靠的。
常见的数据结构
2.1数组与队列
数组和队列是最为常见的数据结构，他们常常用来表示有序的一维数据。由于是有序的结构，在数组与队列中查找与定位效率很高，但对于元素的插入等操作效率相对较低。
我们用vector为例，下图为vector的结构图解：
!
在日常的使用中，C++已经提供了足够好用的vector、deque等容器，一般不需要重新实现。
2.2 树形结构
树形结构的特征为每个节点含有父节点和子节点，最为常见的便是二叉树结构，一棵二叉树上所有的节点都可以合法的拥有一个父节点和不多于两个的子节点。
经典的二叉树结构如下：
二叉树结构在代码中通常可以表示为一个带有两个子节点指针的结构体。
struct Node
{
public:
int value;
Node* left;
Node* right;
};
2.3 拓扑与图
拓扑与图结构往往是由多个节点以及节点间相互作用的关系组合而成。我们常常将它描述为顶点以及边。
我们简单的引入几个描述图的概念：
顶点（vertex）：图中的节点本身。
边（edge）：由节点相连而成，可以含有方向与权值。
有向图：节点与节点之间的连线有明显的指向关系
无向图：节点之间形成通路，没有单方指向关系，也可以理解为双向连接
入度、出度：指向该顶点的边的条数|该节点向外指向的边的条数
权重：节点连接边的加权比重（类似于cast）
我们可以使用不同的方式去描述同一张图，常见方式有邻接矩阵法、邻接表法等。
在实际的代码中，我们分别使用数据结构描述点和边，最后将点与边组合起来生成图，示例代码结构如下：
class Node {
public:
int value=0;
int in = 0;//入度
int out = 0;//出度
vector<Node> nexts;//向外连接的节点
vector<Edge> edges;//一共有哪些边
Node(){
this->in = 0;
this->out = 0;
}
Node(int value) {
this->value = value;
this->in = 0;
this->out = 0;
}
bool operator==(const Node& other) const{
if (other.value==value) return true;
else return false;
}
struct HashFunctionNode{
size_t operator()(const Node& node) const{
size_t xHash = std::hash<int>()(//………);
return xHash;
}
};
};
class Edge {
public:
int weight;
Node from;
Node to;
Edge(int weight, Node from, Node to) {
this->weight = weight;//权重
this->from = from;//起点
this->to = to;//终点
}
struct HashFunction{
size_t operator()(const Edge& edge) const{
size_t xHash = std::hash<int>()(//………);
return xHash;
}
};
};
class Graph {
public:
unordered_map<int, Node> nodes;
unordered_set<Edge, Edge::HashFunction> edges;
Graph() {
//……
}
};
2.4 结构的组合
当现有的简单数据结构无法满足业务需求时，我们可以将各种数据结构进行组合，例如数组和链表的组合（我们就得到了一个类似哈希表的结构……）
这样类似的结构可以综合各种数据结构的优缺点，也是广泛使用的优化数据结构方法。
排序算法
如果说算法是一道完整的料理，那么排序就是备菜的过程。许多的算法都需要运行在有序的数据之上，随意排序虽然不难，却是无法绕开的基础。
3.1冒泡排序
排序思想：冒泡排序是以值为核心的排序，它的原理是一次选择一个列表中的值（注意是值）将这个值沉底或者冒出，一次确定一个最大值（沉底）或者最小值（冒出）。
以下为代码实现：
bool sort_Bubble(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() < 2) return res;
for (size_t i = 0; i < ioArray.size(); i++) {
for (size_t j=0; j < (ioArray.size()-i-1); j++){
if (ioArray[j]> ioArray[j+1])//下沉冒泡 {
Swap(ioArray[j], ioArray[j + 1]);
}
}
}
res = true;
return res;
}
3.2 选择排序
排序思想：选择排序是以下标为核心的排序，一次选择一个列表中的下标对应元素（可以从左到右选择），将它假设为最小（或者最大）并和剩下的元素比较，从而确定这一个下标对应的元素值。
以下为代码实现
bool sort_Selection(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() < 2) return res;
for (size_t i = 0; i < ioArray.size(); i++){
for (size_t j = i+1; j < ioArray.size(); j++){
if (ioArray[i]> ioArray[j]){
Swap(ioArray[i], ioArray[j]);
}
}
}
res = true;
return res;
}
3.3 插入排序
排序思想：插入排序的思想为有序的扩大化，从一个最小的有序数列开始（只有一个元素一定有序）逐步扩大这个数列，将后纳入的元素作为插入元素按序比较（小数列有序），给插入元素一个位置
实现代码如下：
bool sort_Insert(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() < 2) return res;
for (size_t i = 1; i < ioArray.size(); i++)//长度为1的序列不要排序 {
for (size_t j = i; j >0; j--){
if (ioArray[j]<ioArray[j-1]){
Swap(ioArray[j], ioArray[j-1]);
}
}
}
res = true;
return res;
}
3.4 归并排序
排序思想：归并排序使用了分区规划的思想【按下标进行分区】它的默认划分的节点选为中点，一直划分到数组自然有序，即数组只有一个数的时候，再使用merge方法，将有序的子数列合并为有序的大数列。
实现代码如下：
bool sort_Merge(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() <2) return res;
processMerge(ioArray, 0, (ioArray.size() - 1));
res = true;
return res;
}
int processMerge(std::vector<int>& ioArray, int left, int right)
{
if (left==right) return ioArray[left];//直到不可拆分为止
int mid = left +((right - left) >> 1);//防止溢出
int leftMax = processMerge(ioArray, left, mid);
int rightMax = processMerge(ioArray,mid+1,right);
merge(ioArray,left,mid,right);
return __max(leftMax,rightMax);
}
void merge(std::vector<int>& ioArray, int left, int mid, int right){
std::vector<int> tempvec(right- left+1);
int i = 0;
int p1 = left;
int p2 = mid + 1;
while (p1<=mid && p2<=right){
tempvec[i++]=(ioArray[p1]<=ioArray[p2]?ioArray[p1++]:ioArray[p2++]);
}
while (p1<=mid)//右边已经跑完了{
tempvec[i++] = ioArray[p1++];
}
while (p2<=right)//左边已经跑完了{
tempvec[i++] = ioArray[p2++];
}
for (size_t i = 0; i < tempvec.size(); i++){
ioArray[left+i] = tempvec[i];
}
}
3.5 快速排序
排序思想：使用分区规划的思想【按值进行分区】先选定一个元素作为分隔符，小于它的划进小于区，大于它的划进大于区。为了避免算法的最坏情况，我们需要在选择划分值的时候加入随机值 (当原来的数列已经有序，拿后面的数划分，就没有最大区域)即随机选择划分值。快排的空间复杂度取决于它的递归层数，而且其所有复杂度都是期望的结果
排序的实现如下：
bool sort_Quick3(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() <2) return res;
processQuick3(ioArray, 0, ioArray.size()-1);
res = true;
return res;
}
void processQuick3(std::vector<int>& ioArray, int left, int right){
if (left<right){
Swap(ioArray[getRandomNum(left, right)],ioArray[right]);//随机数放在右侧
std::vector<int> tempvec;
tempvec=partition(ioArray,left,right);
processQuick3(ioArray, left, tempvec[0] - 1);//小于区域
processQuick3(ioArray, tempvec[1] +1, right);//大于区域
}
}
std::vector<int> partition(std::vector<int>& ioArray, int left, int right){
int less = left - 1;//小于区域右边界
int more = right;//大于区域左边界
while (left<more) {
if (ioArray[left]< ioArray[right])//ioArray[right] is base number{
Swap(ioArray[++less],ioArray[left++]);
}
else if (ioArray[left] > ioArray[right]){
Swap(ioArray[--more], ioArray[left]);
}
else {
left++;
}
}
Swap(ioArray[more],ioArray[right]);
return (std::vector<int>{ less+1,more });
}
3.6 堆排序
排序思想：还是使用了分治的思想，同时利用了堆的二叉树结构。我们人为构建一个大根堆或者小根堆，每一次调整完结构根就是最大（最小）。我们只需要不断的去维护这个结构就可以，维护这个结构不用动所有节点。
算法实现代码如下;
bool sort_Heap(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() < 2) return res;
for (size_t i = 0; i < ioArray.size(); i++){
heapinsert(ioArray,i);//整体大根堆
}
int heapsize = ioArray.size();
Swap(ioArray[0], ioArray[--heapsize]);//把根和最后一个数交换【此时已经是大根堆】
while (heapsize>0){
heapify(ioArray,0,heapsize);//每一个数向下沉【主要就是为了下一步做准备】
Swap(ioArray[0], ioArray[--heapsize]);//之后再把最后一个数和根交换
}
res = true;
return res;
}
void heapinsert(std::vector<int>& ioArray, int index){
while (ioArray[index]>ioArray[(index-1)/2]) {
Swap(ioArray[index], ioArray[(index - 1) / 2]);
index = (index - 1) / 2;
}
}
void heapify(std::vector<int>& ioArray, int index, int heapsize){
int left = index * 2 + 1;//左子树下标，乘2表示向下一层
while (left<heapsize)//自己还有孩子 {
//比较左右孩子的值
int largest = ((left + 1 < heapsize) && (ioArray[left + 1] > ioArray[left])) ? left + 1 : left; //比较孩子和父，谁配得上largest、
largest = ioArray[largest] > ioArray[index] ? largest : index;
if (largest==index){
break;
}
Swap(ioArray[largest], ioArray[index]);
index = largest;
left= index * 2 + 1;
}
}
3.7 基数排序|计数排序
排序思想：利用划分区域的分类方式代替比较分类，这是一类使用桶排序思想的排序。基数排序：以不同元素的区域，划定桶处理的元素范围，在排序中使用了词频表完成入桶与出桶；而计数排序则是对每一个元素可能出现的值进行频率划分。
我们这里给出基数排序的实现代码：
bool sort_Bucket(std::vector<int>& ioArray){
bool res = false;
if (ioArray.size() < 2) return res;
radixSort(ioArray, 0, ioArray.size()-1, maxbits(ioArray));
res = true;
return res;
}
void radixSort(std::vector<int>& ioArray, int left, int right, int digit){
static int radix = 10;
int i = 0, j = 0;
//准备足够的辅助空间
std::vector<int> tempvec(right-left+1);
for (size_t d = 1; d <= digit; d++) {
//10个空间//count[0]当前位是零的数//count[n]当前位是0到n的数
std::vector<int> count(radix);
for (size_t i = left; i <= right; i++){
j = getDigit(ioArray[i],d);
count[j]++;
}
for (size_t i = 1; i < radix; i++){
count[i] = count[i] + count[i - 1];
}
for (int i = right; i >= left; i--) {
j = getDigit(ioArray[i], d);
tempvec[count[j] - 1] = ioArray[i];
count[j]--;
}
for (i = left, j = 0; i <= right; i++, j++) {
ioArray[i] = tempvec[j];
}
}
}
二叉树经典算法
4.1 三种遍历方式
提到二叉树，那必然不能不提它的前中后三种遍历方法，以及如何使用递归与非递归方式完成遍历。这里指的前中后序并不是一个固定的顺序，而是先处理哪一个节点。
如果你的处理函数在对一个struct Node（含两个叶子节点）的处理过程中先处理了自己，我们叫它前序。先处理了左子节点或者右子节点，在中间处理自己，我们叫它中序。先处理了左右子节点，最后处理自己，我们叫它后序。
我们这里简单的表述一下三种遍历的递归与非递归的实现方式。
首先是递归方式，我们以前序为例：
void preOrderRecurErgodic(Node*& head) {
if (!head) {
return;
}
ProcessErgodic(head);
preOrderRecurErgodic(head->left);
preOrderRecurErgodic(head->right);
}
如果使用非递归方式，我们就需要使用栈的结构，去仿照递归的执行过程。
void preOrderStackErgodic(Node*& head){
if (!head) {
return;
}
stack<Node*> node_stack;
node_stack.push(head);
while (!node_stack.empty()) {
head= node_stack.top();
node_stack.pop();
ProcessErgodic(head);
if (head->right) {//先右后左，与期望输出相反
node_stack.push(head->right);
}
if (head->left) {
node_stack.push(head->left);
}
}
}
而由于栈的特殊性，如果我们在应当执行处理函数的时机将它放入栈中，全部入栈之后再从头执行，就得到了后序遍历代码：
void posOrderStackErgodic(Node*& head){
if (!head) {
return;
}
stack<Node*> node_stack_in;
stack<Node*> node_stack_process;
node_stack_in.push(head);
while (!node_stack_in.empty()) {
head = node_stack_in.top();
node_stack_in.pop();
node_stack_process.push(head);
if (head->left) {
node_stack_in.push(head->left);
}
if (head->right) {
node_stack_in.push(head->right);
}
}
while (!node_stack_process.empty()) {
Node* node_process= node_stack_process.top();
ProcessErgodic(node_process);
}
}
而中序优先遍历时，我们可以将一棵二叉树进行完全的左分解，优先压入左边，然后依次出栈，并处理右子树。就可以得到简洁的中序遍历代码：
void midOrderStackErgodic(Node*& head){
if (!head) {
return;
}
stack<Node*> node_stack;
while (!node_stack.empty() || head) {
if (head != nullptr) {//优先压入左边
node_stack.push(head);
head = head->left;
}
else {
head = node_stack.top();
node_stack.pop();
ProcessErgodic(head);
head = head->right;
}
}
}
4.2 深度与宽度优先
深度优先和宽度优先遍历由于其结构的特殊性，并不需要复杂的处理算法。深度遍历的原理为优先处理子树的内容，其代码和前序遍历一致，不再重复。而二叉树的宽度优先遍历为优先处理同层次的内容，所以代码实现中先处理完父节点，然后将左右节点分别放入即可。
void widthOrderErgodic(Node*& head)
{
if (!head) {
return;
}
queue<Node*> node_queue;
node_queue.push(head);
while (!node_queue.empty()) {
Node* cur = node_queue.back();
node_queue.pop();
ProcessErgodic(head);
if (cur->left) {
node_queue.push(cur->left);
}
if (cur->right ) {
node_queue.push(cur->right);
}
}
}
4.3 树形DP
树形DP：顾名思义，就是在树状的结构上，进行动态规划的过程。树状结构通常指的是二叉树的结构，DP（Dynamic programming）指一种动态的分治思想。这里算法的本质仍然是将一个整体的问题拆分为若干子问题求解，不同的是，每一个子问题的求解结果可能会影响到之后的决策，所以我们需要不断地返回并处理子问题的求解信息。这里就是其相对于普通分治法动态的部分。
我们以一个简单的题目来阐述树形DP的思路与解法。
题目如下：
输入格式：
输入的第一行是一个整数 n。
第 2 到第 (n + 1)行，每行一个整数，第 (i+1)行的整数表示 i 号职员的快乐指数 ri；第 (n + 2) 到第 2n 行，每行输入一对整数 l, k代表 k 是 l的直接上司。
输出格式：
输出一行一个整数代表最大的快乐指数。
我们仔细观察题目，它从什么角度符合动态规划的特征，又该怎么解决呢？
首先，这是一棵结构清晰的树，每一个节点的父节点是上司；子节点是下属。其次，它满足动态的定义，即我们这一次的选择会影响到下一步的选择，回顾一下最简单的分治递归，它虽然使用了递归调用的结构，但是每次使用的单元处理函数（每次递归调用的函数）都是不变的，上一次的选择不会影响到下一次的处理。而在动态过程中，比如这个题目：当前节点能不能来，取决于下属节点的选择；当前节点能不能来，也取决于当前节点的选择；当前节点来不来，会影响上司节点的选择权利。这样的影响，导致每一步的选择都会动态影响最后的结果。
由于动态规划的特点和树形的结构，我们可以知道，题解需要子的配合。在现实生活中，在假设人员不会说谎的情况下，我们可以直接打电话询问下属，也就是获取子树的信息。
不断调用函数从子树中获取信息，就是树形DP的解法。简而言之，直接向子树索取信息。
示例题解如下：
void TempSln_DP(){
vector<int> g[6010];//二维的数组（开链表示），每一个成员表示一个上司，上司有一个下属列表
int ss[6010];//每一个成员代表一个下属，一个成员只可能有一个上司，所以没有用开链
int r[6010];//存储每一个节点的权值
int n;//一共多少人
int x, y;//临时变量，用于输入上司与下属的关系
int f[6010][2];//这里记录一个节点来或者不来的状态，数值代表当前状态的快乐值||
//这一个值表达的就是动态的概念，如果我们不使用这种全局的变量，就需要向子树索取返回数据
void dfs(int x) {
for (int j = 0; j < g[x].size(); j++) {//遍历所有有下属的成员
int i = g[x][j];//取出一个下属
dfs(i);//递归
//传说中的转移函数，其实就是把子树的快乐值存到了全局
f[x][0] += max(f[i][1], f[i][0]);
f[x][1] += f[i][0];
}
f[x][1] += r[x];//来的话，加上权值
}
int main1() {
scanf("%d", &n);//一共多少人
for (int i = 1; i <= n; i++)
scanf("%d", &r[i]);//每个人的权重
while (scanf("%d%d", &x, &y) == 2, x != 0 || y != 0) {//输入上司与下属的关系
g[y].push_back(x);
ss[x] = y;
}
for (int i = 1; i <= n; i++)
if (ss[i] == 0) {//当前节点没有上司（找到了boss）
dfs(i);
printf("%d\n", max(f[i][1], f[i][0]));//最后输出结果
break;
}
return 0;
}
}
4.4 序列化与反序列化
序列化的过程是将二叉树等数据结构所存储的信息转化为有序排列的一维信息。它将复杂的结构转换成可以取用的格式，通常在断电数据保护、文件传输的时候使用。
经过序列化的信息后续在相同或另一台计算机环境中，能恢复到原先状态。依照序列化格式重新获取字节的结果时，可以利用它来产生与原始对象相同语义的副本。对于许多对象，特别是使用大量引用的复杂对象，这种序列化重建的过程并不容易。面向对象中的对象序列化，并不概括之前原始对象所关系的函数。这种过程也称为对象编组（marshalling）。从一系列字节提取数据结构的反向操作，是反序列化（也称为解编组、deserialization、unmarshalling）。
我们这里以简单的二叉树序列化与反序列化的过程演示上述概念。
根据之前的描述，我们了解了什么是二叉树的遍历，在二叉树的遍历过程中，我们会依次处理遍历的元素。只需要将处理函数替换为序列化写入函数，即可完成二叉树的序列化。
char* Serialize(Node* root) {
string str;
preOrderRecurErgodic(root, str);//这里使用了先序遍历
char* ret = new char[str.length()];
strcpy(ret, str.c_str());
return ret;
}
反序列化的过程本质是依据定义好的规则对序列化的逆运算。
Node* Deserialize(char** pstr) {
char* str = *pstr;
if (*str == '#') {
(*pstr)++;
return NULL;
}
int num = 0;
while (*str != ',') {
num = 10 * num + *str - '0';
str++;
}
str++;
*pstr = str;
Node* root = new Node(num);
root->left = Deserialize(pstr);
root->right = Deserialize(pstr);
return root;
}
图与拓扑的经典算法
5.1 宽度优先与深度优先
相比于之前提及的二叉树的深度优先、宽度优先遍历，图的遍历更加的符合深度、宽度的定义。
深度优先要求的是优先到达未有邻接关系的点，如果我们以互联网为例的话，它更类似于网络中的单播，以最快的速度路由到最远的节点。
而宽度优先则要求优先到达所有相邻节点，更类似于网络中的广播行为，以最快的速度向邻居转达信息。
两种优先遍历的图示如下：
根据上述信息，我们可以轻易的写下下面的代码：
void bfs(Node node) {
queue<Node> queue;
unordered_set<Node,Node::HashFunctionNode> set;
queue.emplace(node);
set.insert(node);//存储已经标记过的node
while (!queue.empty()) {
Node cur = queue.front();
queue.pop();
cout << (cur.value) << endl;//处理函数，这里简单使用cout代替
for (Node next : cur.nexts) {//所有的相邻接点放进去
if (set.find(next)== set.end()) {//已经处理过的节点不要
set.insert(node);
queue.emplace(node);
}
}
}
}
void dfs(Node node) {
stack<Node> stack;
unordered_set<Node, Node::HashFunctionNode> set;
stack.emplace(node);
set.insert(node);
cout << (node.value) << endl;
while (!stack.empty()) {
Node cur = stack.top();//深度优先可以仿堆栈
stack.pop();
for (Node next : cur.nexts) {
if (set.find(next) == set.end()) {
stack.push(cur);
stack.push(next);
set.insert(node);
cout << (next.value) << endl;
break;//深度优先
}
}
}
}
5.2 Kruskal|Prim
Kruskal与Prim算法都是计算最小生成树的算法（用来求加权连通图的最小生成树的算法）。最小生成树可以在保证图节点连通的情况下，连通代价最小。
Kruskal与Prim算法的不同之处在于，它们一个是以节点为中心计算，一个则是以边为中心计算。
Kruskal的计算步骤可以总结为：
S01: 从图的边集数组中找到权值最小的边，将边的两个顶点连接起来
S02: 考察当前已经选择的边是否形成环
S03：如果形成环了，舍弃当前选择。如果没有形成环的话，将当前选择加入集合，继续找下一个权值较小的边。
整个算法十分简单，值得注意的点在于如何考察已经选择的边中是否含有环路。我们这里提供一种思路：
将每一个边当做只含有一个元素的集合，找到权值最小的边之后，将集合合并，扩充已选择集合。由于边可以找到两端的元素，我们可以存储下起点与终点，在合并入新边时，只需要判断首尾是否相接即可。若该图为无向图，则只需判断集合中是否已有相同的元素。
示例代码如下：
//最小生成树，克鲁斯卡尔算法
void Kruskal(MGraph* G) {
int parent[MAXVERTEX];//存放最小生成树的顶点
for (int i = 0; i < G->numvertex; i++) {
parent[i] = 0;
}
int m, n;
for (int i = 0; i < G->numedges; i++) {
n = Find(parent, G->edges[i].begin);
m = Find(parent, G->edges[i].end);
if (n != m) { //m=n说明有环
parent[n] = m;
printf("(%d,%d) %d\t", G->edges[i].begin, G->edges[i].end, G->edges[i].wight);//打印边和权值
}
}
}
Prim算法则是以顶点为中心的算法，它的计算步骤可以被总结为：
S01: 以节点的角度出发，先找一个节点（可以随机，反正都会连起来）
S02: 找这个节点的出度边，在边里面选一个最小权值的，把这条边的连接节点拿进来
S03：同样的，我们把拿进来的节点存放到一个集合里面，边也放到一个容器里
S04：如果被选择的节点已经在集合里面，查看它拥有的边在不在，如果都在，我们就舍弃它，寻找下一个。
下面给出示例代码：
/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/
void Prim(adjmatrix GA, EdgeNode T) {
int i, j, k, min, u, m, w;
Edge temp;
/*给T赋初值。相应为v1依次到其余各顶点的边*/
k = 1;
for (i = 1; i <= n; i++) {
if (i != 1) {
T[k].fromvex = 1;
T[k].tovex = i;
T[k].weight = GA[1][i];
k++;
}
}
/*进行n-1次循环，每次求出最小生成树中的第k条边*/
for (k = 1; k < n; k++) {
min = MaxNum;
m = k;
for (j = k; j < n; j++) {
if (T[j].weight < min) {
min = T[j].weight;
m = j;
}
}
/*把最短边对调到k-1下标位置*/ 可用swap替换
temp = T[k];
T[k] = T[m];
T[m] = temp;
/*把新增加最小生成树T中的顶点序号赋给j*/
j = T[k].tovex;
/*改动有关边，使T中到T外的每个顶点保持一条到眼下为止最短的边*/
for (i = k + 1; i < n; i++) {
u = T[i].tovex;
w = GA[j][u];
if (w < T[i].weight) {
T[i].weight = w;
T[i].fromvex = j;
}
}
}
}
5.3 Dijkstra
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径，典型的应用就是游戏中的路径规划。
Dijkstra的计算过程并不复杂，其核心思路可以总结为一句话：找出每个出发点到所有的点的距离，（可以填入一张表中）每次向这个表中填入一个最短距离，然后更新计算这张表。
我们以下图为例：
S01我们选择A节点为起始点，拟定一张由A到达其他节点的表格，最初全部初始化为MAX。
S02然后，我们由A点出发，发现了从A通向B的路径，该路径权值18。
S03:依据这一路径，我们更新A点的表格，发现A达到B的值不再是MAX，可以被更小的18替代，同时，该条路径的发现不会影响A点前往其他路径的值。所以其余值依然保持MAX。
S04:我们紧接着发现了A的其他边，依次更新表格，当某一个节点的所有边都被发现，我们就不再更新该节点的对应距离。
落到代码之中，我们同样给出示例：
//迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径p[v]及带权长度D[v]
//p[][]=-1表示没有路径，p[v][i]存的是从v0到v当前求得的最短路径经过的第i+1个顶点(这是打印最短路径的关键)，则v0到v的最短路径即为p[v][0]到p[v][j]直到p[v][j]=-1,路径打印完毕。
//final[v]为true当且仅当v∈S,即已经求得从v0到v的最短路径。
void ShortestPath_DIJ(Graph G, int v0, int p[][MAX_VERTEX_NUM], int D[]) {
int v, w, i, j, min;
bool final[10];
for (v = 0; v < G.vexnum; v++) {
final[v] = false;//设初值
D[v] = G.arcs[v0][v];//D[]存放v0到v得最短距离，初值为v0到v的直接距离
for (w = 0; w < G.vexnum; w++)
p[v][w] = -1;//设p[][]初值为-1，即没有路径
if (D[v] < INFINITY) { //v0到v有直接路径
p[v][0] = v0;//v0到v最短路径经过的第一个顶点
p[v][1] = v;//v0到v最短路径经过的第二个顶点
}
}
D[v0] = 0;//v0到v0距离为0
final[v0] = true;//v0顶点并入S集
for (i = 1; i < G.vexnum; i++) { //其余G.vexnum-1个顶点
//开始主循环，每次求得v0到某个顶点v的最短路径，并将v并入S集，然后更新p和D
min = INFINITY;
for (w = 0; w < G.vexnum; w++)//对所有顶点检查
if (!final[w] && D[w] < min) { //在S集之外(即final[]=false)的顶点中找离v0最近的顶点，将其赋给v,距离赋给min
v = w;
min = D[w];
}
final[v] = true;//v并入S集
for (w = 0; w < G.vexnum; w++) { //根据新并入的顶点，更新不在S集的顶点到v0的距离和路径数组
if (!final[w] && min < INFINITY && G.arcs[v][w] < INFINITY && (min + G.arcs[v][w] < D[w])) {
//w不属于S集且v0->v->w的距离<目前v0->w的距离
D[w] = min + G.arcs[v][w];//更新D[w]
for (j = 0; j < G.vexnum; j++) { //修改p[w]，v0到w经过的顶点包括v0到v经过的所有顶点再加上顶点w
p[w][j] = p[v][j];
if (p[w][j] == -1) { //在p[w][]第一个等于-1的地方加上顶点w
p[w][j] = w;
break;
}
}
}
}
}
}
5.4 并查集
并查集作为一种经典的算法结构，它从设计之初就只为了一件事：如何简单高效的合并集合、查找集合元素。
我们先看看传统的数据结构怎么处理这个问题：
由于需要合并集合，我们可以考虑链表结构，链表的合并只需要改动少许元素即可完成。但是合并完之后的查询却需要遍历；
那什么结构查询快呢，当然是map，但是要合并两张map，需要进行元素的迁移，在大数量的时候也无法接受。所以我们提出这种并查集的结构。其实在之前的K算法和P算法中，我们已经初步使用了类似于并查集结构的内容，它可以快速的检查连通性以及图是否有环。
我们接下来讨论并查集的实现：
现在，我们假设有一群学生，他们每个人自成一个班级。要想找到他们，需要遍历所有元素，想要知道他们是否属于某一个班级也是一样需要遍历：
由于没有这么多老师，我们要精简编制，合并这些单人班。我们搞一次群众选举，被选中的人出任新班级的班长，并且以班长的名字命名新班级。
此时6个班级变为两个，继续合并。
于是乎……我们就得到了一个树状的结构，一号身为班长，班级命名为1班，4号则由原来的班长退化为组长，仍然管辖两位同学。
回顾这一步的合并，过程相比较于map的合并，只需要班长承认自己属于另一个班级，不再需要所有同学的承认，无疑大大缩短了合并时间。
而此时如果我们需要查找6号同学和16号同学是不是在一个班级中，也不需要在各自的班级中遍历查找有没有对方，而是可以通过比对班长是否是同一个人即可。这也大大缩短了查询时间。
但这个时候我们也发现了一个问题，就是当合并的班级越来越多，这个树越来越长，那我们后加入的同学想要找到班长直接交流也就越来越难，查询时间就会变长。
所以我们需要扁平化的管理氛围。在数据结构中，进行路径压缩。示例如下图：
同样，我们给出简易的并查集合并示例代码：
void initSet(int* set, int n) {
for (int i = 0; i < n; i++) {
set[i] = -1;
}
}
int find(int* set, int x) {
return set[x] < 0 ? x : set[x] = find(set, set[x]);
}
void merge(int* set, int x, int y) {
x = find(set, x);
y = find(set, y);
if (x == y) return;
if (set[x] > set[y]) {
set[y] += set[x];
set[x] = y;
}
else {
set[x] += set[y];
set[y] = x;
}
}
Q.E.D.
