一道智力题

发表于 2020-07-08 | 阅读次数:

Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
 
Input&Output
输入三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。如果能平分的话请输出最少要倒的次数，否则输出"NO"。
 
Sample Input
7 4 3
4 1 3
0 0 0
 
Sample Output
NO
3

用最大公约数的角度思考，本质就是寻找一个最优化方程组的可能整数解;记录此题是因为用BFS写起来过于冗长，这种解决方法给我耳目一新的感觉。

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int a,b,c;
    while(cin>>a>>b>>c&&(a&&b&&c))
    {
        a/=gcd(b,c);
        if(a&1)
            cout<<"NO"<<endl;
        else
            cout<<a-1<<endl;
    }
    return 0;
}

所谓高精度

发表于 2020-06-05 | 阅读次数:

#include <stdio.h>
#include <string.h>
//jie cheng
struct bigInteger
{
	int digit[1000];
	int size;
	void init()
	{
		for(int i=0;i<1000;i++)
			digit[i]=0;
		size=0;
	}
	
	void set(int x) //solve N! N is a small int
	{
		init();
		do
		{
			digit[size++]=x%10000;
			x/=10000;
		}while(x);
	}
	
	void output()
	{
		for(int i=size-1;i>=0;i--)
		{
			if(i!=size-1) printf("%04d",digit[i]);
			else printf("%d",digit[i]);
		}
		printf("\n");
	}
	
	bigInteger operator * (const int &x) const
	{
		bigInteger ret;
		ret.init();
		int carry=0;
		for(int i=0;i<size;i++)
		{
			int temp=x*digit[i]+carry;
			carry=temp/10000;
			temp%=10000;
			ret.digit[ret.size++]=temp;
		}
		if(carry!=0)
		{
			ret.digit[ret.size++]=carry;
		}	
		return ret;
	 }

    bigInteger operator + (const bigInteger &A) const
	{
		bigInteger ret;
		ret.init();
		int carry=0; 
		for(int i=0;i<A.size||i<size;i++)
		{
			int temp=A.digit[i]+digit[i]+carry;
			carry=temp/10000;
			temp%=10000;
			ret.digit[ret.size++]=temp;	
		}
		if(carry!=0)
			ret.digit[ret.size++]=carry; 
		
		return ret;
	}
}a;

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		a.init();
		a.set(1);
		for(int i=1;i<=n;i++)
		{
			a=a*i;
		}
		a.output();
	}
	return 0;	
}

降噪算法之深度网络

发表于 2020-05-10 | 阅读次数:

在之前提到的五种方法，虽然把标签都归结于深度学习，但其实这一篇才是用深度网络的方式来解决降噪这个逆问题，囿于篇幅，这里就贴一个文档的链接好了。
改进Deep Image Prior进行图像降噪工作

降噪算法之低秩恢复

发表于 2020-05-09 | 阅读次数:

近几年，低秩矩阵恢复（LRMR）广泛用于图像处理用途图像恢复，比如去噪、去模糊等。一幅清晰的自然图像其数据矩阵往往是低秩或者近似低秩的，但存在随机幅值任意大但是分布稀疏的误差破坏了原有数据的低秩性。低秩矩阵恢复是将退化图像看做一组低维数据加上噪声形成的，因此退化前的数据就可以通过低秩矩阵来逼近。
设B为模糊图像，根据低秩分解有B=I+N，其中I为清晰图像，是低秩的。N为噪声具有稀疏性。
example

秩的行列式定义：设在矩阵A中有一个不等于0的r阶子式D，且所有r+1阶子式（如果存在的话）全等于0，那么D称为矩阵A的最高阶非零子式，数r称为矩阵A的秩，记作R（A）。并规定零矩阵的秩等于0.求解方法：对矩阵作初等行变换为行阶梯矩阵，其中非零行的个数为矩阵的秩。其物理意义矩阵中的最大不相关的向量的个数。顾名思义，低秩是指矩阵的秩比较小，而矩阵的低秩性是指矩阵的秩相对矩阵的行数或列数而言很小。

低秩与稀疏: 低秩是指矩阵的秩较小，稀疏是指矩阵中非零元素的个数少。如果对矩阵进行奇异值分解，并把其所有奇异值排列为一个向量，那么这个向量的稀疏性便对应于该矩阵的低秩性

由矩阵秩的定义知道，若将图像看成一个矩阵，那么它的基的数量越少，基对应的线性无关向量数量就越少，矩阵的秩就越小。当它远远小于矩阵的大小的时候，图像就是低秩的。低秩矩阵的每行或者每列都可以用其他的行或者列线性表示，这说明这个矩阵包含了大量的冗余信息。利用这种冗余信息可以对确实图像信息进行恢复，可以将多出来的噪声信息进行去除，还可以对错误的图像信息进行恢复。图像处理中，rank可以理解为图像所包含的信息的丰富程度，在现实生活中，一张图片大部分是相似的。比如一张大草原的图片：可以理解为，草原是由很多草组成的，而草是相似的，所以如果全是草，那么这张图所包含的信息量是很少的的，因为可以理解为草是草的复制品。如果图片中比较突兀的成分，比如蒙古包，比如人像照片中的红眼亮点，会增加图像矩阵的秩。

我们可以利用图像的低秩性来恢复图像，首先构建融合了低秩矩阵先验的模型，再求解这个模型得到低秩的矩阵。这种基于低秩矩阵逼近（LOW-Rank Matrix Approximation,LRMA）的模型称为低秩矩阵恢复模型（LRMR）。目前，LRMR主要有鲁棒主成分分析robust PCA,RPCA）、矩阵补全（matrix completion,MC）和低秩表示（low-rank representation，LRP）等三类模式。LRMR其实就是假设给定数据矩阵D，D=A+E,其中A和E未知，但是A是低秩的。低秩矩阵表示是将数据集矩阵D表示成字典矩阵B（也称为基矩阵）下的线性组合，即D=BZ，并希望线性组合系数矩阵Z是低秩的,其实是希望能解决一个最优化问题。
RPCA
这篇文章把奇异值的意义介绍的很详细：https://www.zhihu.com/question/22237507/answer/53804902 。简而言之，奇异值分解是将矩阵分解成若干个秩一矩阵（矩阵秩为1）之和，奇异值往往对应着矩阵中隐含的重要信息，且重要性和奇异值大小正相关。

降噪算法之传统外部先验

发表于 2020-05-09 | 阅读次数:

外部先验（external prior）：如果从有噪音的图片本身无法找到规律，我们也可以借助其他类似但又没有噪音的图片，来总结图片具有的固有属性。这一类方法利用的外部图片来创造先验条件，然后用于约束需要预测的图片。最有代表性的工作，就是混合高斯模型（Gaussian Mixture Model）。严格来说，基于深度学习的算法也可以归于这个类。所以这里是指传统的外部先验方式。
顾名思义，就是用多个带有权重的高斯密度函数来描述数据的分布情况。理论上来说，高斯分量越多，极值点越多，混合高斯密度函数可以逼近任意概率密度函数，刻画模型越精确，需要的训练数据也就越多。
图中的点在我们看来明显分成两个聚类。这两个聚类中的点分别通过两个不同的正态分布随机生成而来。但是如果没有GMM，那么只能用一个的二维高斯分布来描述图中的数据。如果只考虑一个高斯分布，最后能作出一个椭圆区域，这显然不太合理，毕竟肉眼一看就觉得应该把它们分成两类。
gmm
其用数学方式表示出来很简单：
gmm2
例如图2的例子，很明显有两个聚类，可以定义K=2. 那么对应的GMM形式如下：
gmm2
将GMM的思想和一些方法进行结合，就可以达到一定的降噪效果，比如小波分解。

降噪算法之稀疏表示

发表于 2020-05-08 | 阅读次数:

从稀疏分解与稀疏表示的角度看，含噪的图像信号包括两部分，干净图像信号与噪声。由于干净的图像信号是又一定的结构的，其结构特性与原子特性相吻合，故干净图像信号是稀疏成分，通过设定稀疏表示阈值可以保留下来。而噪声是随机的，不相关，因此没有结构特性。如果能够从信号中提取出有意义的原子，则提取出的部分就作为信号。如果不能继续从信号残差中提取出有意义的原子，则认为信号残差中全部是噪声。通过这样的原理可以达到图像去噪的目的。感觉做稀疏表示降噪的比较少，看了很多资料，在知乎上看到一篇还不错的，再结合论文，今天就来讲讲K-SVD算法。

SVD

从大二上学到《矩阵论》，到今天才知道SVD可以用于图片压缩。奇异值分解是一个能适用于任意的矩阵的一种分解的方法，假设A是一个N M的矩阵，那么得到的U是一个N N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片。当我们从大到小开始截断，丢弃较小的奇异值并重建图像之后，我们就能得到「压缩之后」的图像了。在Python的cv2包中有相关实现。
SVD
下面这张图就是对一张高清图片选择前五十个较大特征值进行压缩得到的小猫咪。此时，重建的图像和原图已经相当接近了。
neco
同样的，SVD也可以进行降噪。其原理是，奇异值较小的部分，频率较低，大多不是信号而是噪声部分，将其去除后（即，只取前面频率较高的部分），就相当于进行了降噪处理。

K-means

首先申明，K-means和KNN是两个不同的算法。K-平均算法源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。
这个问题在计算上是NP困难的，不过存在高效的启发式算法。一般情况下，都使用效率比较高的启发式算法，它们能够快速收敛于一个局部最优解。这些算法通常类似于通过迭代优化方法处理高斯混合分布的最大期望算法（EM算法）。而且，它们都使用聚类中心来为数据建模；然而k-平均聚类倾向于在可比较的空间范围内寻找聚类，期望-最大化技术却允许聚类有不同的形状。

KNN分类算法

监督学习
数据集是带Label的数据
没有明显的训练过程，基于Memory-based learning
K值含义 - 对于一个样本X，要给它分类，首先从数据集中，在X附近找离它最近的K个数据点，将它划分为归属于类别最多的一类

K-means聚类算法

非监督学习
数据集是无Label，杂乱无章的数据
有明显的训练过程
K值含义- K是事先设定的数字，将数据集分为K个簇，需要依靠人的先验知识

K-means要解决的问题是NP问题，为了避免NP问题带来的计算麻烦，算法使用迭代的方式，能以较快的速度得到一个不错的局部最优结果。字典设计问题上也存在计算量过大的问题，将其K-means这种避其锋芒，退而求其次的方法推而广之便有了K-SVD算法。
原始的K-means算法思想分四步：

从N个点随机选取K个点作为质心
对剩余的每个点测量其到每个质心的距离，并把它归到最近的质心的类
重新计算已经得到的各个类的质心
迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束

稀疏表示与字典学习

写字相对于打字而言是很麻烦的，你需要一笔一划的写，每一个笔画你都必须认真写，否则就会很丑。但在打字的时候，具体来说，拼音打字，只需要输入几个字母就能打出你想要的字，而且这些字在屏幕上显示得异常美观。而几个字母就能表示笔画复杂的文字的过程，我们就可以称之为“稀疏表示”，简而言之，它就是用少量信息来映射复杂信息的过程。从广义上来说，人类的语言文字皆为稀疏表示，用少量的象形符号排列组合就能表示无限多的含义。那么“稀疏表示”又是怎么做到的呢？答案是利用“字典”。
正是因为电脑里保存了Unicode字符库、字体库等等一系列支持软件，我们才能用几个字母来写出一个标准的漂亮的字。也正是因为人类将世界中复杂的信息分解抽象化成为符号，构成“字典”，我才能够用这一屏幕密密麻麻的小黑方块，来向你介绍什么是“稀疏表示”，什么又是字典。
而字典是有好坏之分的，好的字典有两个特点，一是在表达的时候只需要用非常稀疏（即很少）的信息，二是这些稀疏的信息通过字典的映射（可以将字典看做一个函数），准确地表达原本的含义，即误差低。简而言之，好的字典较准确地提取出了复杂信息中的抽象结构。

K-SVD

ksvd

降噪算法之滤波

发表于 2020-05-07 | 阅读次数:

前言

这个部分应该总共会有五个part，来讲述最近的一些工作，分别小结五类图片降噪方法。降噪的本质，是要从观测值中分离噪音，保留图像。算法的关键，是要掌握并借助于图像本身独特的性质和结构。根据算法利用了什么图像性质，就可以分为许多流派了。基本上可以这么划分：滤波类，稀疏表达类，外部先验，聚类低秩和最近很热的深度网络方法。
今天主要来学习第一类滤波算法，最知名的是BM3D算法了。这是一种相对比较传统的算法，通过设计滤波器对图像进行处理。特点是速度比较快，很多卷积滤波可以借助FFT变换来加速。近期的一些算法也结合了一些block matching来利用图片的self-similarity，效果不错。
有两种噪声算法，一种是非局部去噪方法Non-local method(NLM)，是一种空间算法，另一种transform method是一种转换算法，都在图像去噪中得到很好的效果，所以自然而然地想：同时使用两种算法效果如何？这便引出了BM3D去噪算法。

Non-Local Means

顾名思义，这是一种非局部平均算法。何为局部平均滤波算法呢？那是在一个目标像素周围区域平滑取均值的方法，所以非局部均值滤波就意味着它考虑到了图像中的所有像素，这些像素根据某种相似度进行加权平均。非局部均值滤波由Baudes提出，其出发点应该是借鉴了越多幅图像加权的效果越好的现象，那么在同一幅图像中对具有相同性质的区域进行分类并加权平均得到去噪后的图片，应该降噪效果也会越好。同时，在一个邻域中，不同位置的像素权重也不一样，考虑到复杂度搜索区域大概取21x21，相似度比较的块的可以取7x7。

Transform method

这个方法偏信号角度，比较知名的方法是小波去噪。从信号学的角度看 ,小波去噪是一个信号滤波的问题。尽管在很大程度上小波去噪可以看成是低通滤波 ,但由于在去噪后 ,还能成功地保留信号特征 ,所以在这一点上又优于传统的低通滤波器。由此可见 ,小波去噪实际上是特征提取和低通滤波的综合

BM3D

BM3D算法总体分为两大步估计，每一大步又分为三小步：相似块分组、协同滤波和聚合。Basic estimate与Final estimate，两步除Collaborative filtering不同外，其余子步骤近似。从2007年提出，它在近十年内都被认为是最好的算法。甚至目前一些论文也经常引用到这个模型。说白了，该算法通过相似判定找到与参考块相近的二维图像块，并将相似块按照组合成三维群组，对三维群组进行协同滤波处理，再将处理结果聚合到原图像块的位置。

第一大步：基础估计

第一步，搜索相似块，然后把相似的块grouping成一个个3D stack。（图像本身是2D，变成stack就成了3D）

第二步，协同滤波：先对每个三维矩阵中的二维的块进行二维变换（DCT变换）后再在矩阵的第三个维度进行一维变换，通常为Hadamard Transform。变换后采用硬阈值的方式将小于超参数(lambda_3D)的成分置为0。同时统计非零成分的数量作为后续权重的参考。最后通过在第三维的一维反变换和二维反变换得到处理后的图像块。这里会涉及到一个凸优化的硬阈值(Hard Threshold)的概念。
第三步，聚合：将这些图块逆变换后放回原位，利用非零成分数量统计叠加权重，最后将叠放后的图除以每个点的权重就得到基础估计的图像，权重取决于置0的个数和噪声强度，此时图像的噪点得到了较大的去除。

第二大步：最终估计

1、分组：基础估计已经极大地消除了噪点对于含噪原图的每个目标图块，可以直接用对应基础估计图块的欧氏距离衡量相似程度。按距离从小到大排序后取最多前MAXN1个。将基础估计图块、含噪原图图块分别叠成两个三维数组。所以这一步与第一步中不同的是这次会得到两个三维数组，一个是噪声图像形成的三维数组一个是基础估计得到的三维数组。
2、协同滤波：两个三维矩阵都进行二维和一维变换，这里的二维变换采用DCT变换。不同之处在于，用维纳滤波（Wiener Filtering）将噪声图形成的三维矩阵进行系数放缩，该系数通过基础估计的三维矩阵的值以及噪声强度得出。这一过程用如下公式表示，其中(w_p)是维纳滤波的系数：
3、聚合：与第一步中一样
相对于基础估计图，最终估计图还原了更多原图的细节。

再话图算法—最短路

发表于 2020-04-29 | 阅读次数:

最近真是加把劲骑士。今天复习一下最短路径，即给定图计算从起点到终点的最短路径。常用算法有Dijsktra、Bellman-ford、SPFA、Floyd算法。

Dijsktra单源最短路

基本思想：设置已访问节点S，然后每次从V-S中选择离起点s的最短路径最小的节点u，之后以u为中介，调整s到从u经过能到达的所有顶点v的最短距离，执行n次即可。简单来说，就是每次选择未访问最短距离点，选择后借助这个点开放相关边，再借助相关边更新最短路。

const int MAXV=1000;
const int INF=0x3fffffff;

int n,G[MAXV][MAXV];
int dis[MAXC];
bool vis[MAXV]={false};

void Dijstra(int s) //s means source
{
    fill(dis,dis+MAXV,INF); //慎用memset,fill为algorithm库提供的函数
    dis[s]=0;

    for(int i=0;i<n;i++)  //重复n次
    {
        int u=-1,MIN=INF; //找到dis[u]最小
        for(int j=0;j<n;j++) //找到u
        {
            if(vis[j]==false&&dis[j]<MIN)
            {
                u=j;
                MIN=dis[j];
            }
        }

        if(u==-1) return; //说明剩下的顶点和s不连通
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            //如果v没访问 且 u能到达v 且 能够达到更优的dis
            if(vis[v]==false&&G[u][v]!=INF && dis[u]+G[u][v]<dis[v])
            {
                dis[v]=dis[u]+G[u][v];
                //pre[v]=u
            }
        }
    }
}

邻接链表版的就略了，它可以一定程度减小时间复杂度，降低空间开销。
以上只是求解了最短距离，并未求解最短路径。实际上，我们添加一个pre[MAXV]数组，其中pre[v]表示从起点到顶点v的最短路径上v的上一个前驱节点。初始时，pre[i]指向自身i。最后，在更新可更新边的时候，将pre[v]确定为本次循环确定的节点u。要访问路径，从最后一个节点递归访问即可。

void DFS(int s,int v) //从终点v开始递归
{
    if(v==s){
        printf("%d\n",s);return;
    }
    DFS(s,pre[v]);
    printf("%d\n",v);
}

同时，dijsktra算法也有很多变体，比如最短路不止一条，往往会新增一个关于开销的量度：

给每一条边新增一个另一个维度的边权，即除了距离，还有花费，希望路上少花点钱
给每个点增加一个点权，希望能够搜集更多的物资

直接问如果有，有几条
对于这三种，增加一个数组来存放新增的边权或者点权或者最短路径条数，然后修改优化dis[v]那个步骤即可。以第一个情况为例：

for(int v=0;v<n;v++)
{
    if(vis[v]==false&&G[u][v]!=INF)
    {
        if(dis[u]+G[u][v]<dis[v])
        {
            dis[v]=dis[u]+G[u][v];
            cos[v]=cos[u]+cost[u][v]; //cos和dis一样，cost和G类似
        } else if(dis[u]+G[u][v]==dis[v]&&c[u]+cost[u][v]<cost[v])
        {
            cos[v]=cos[u]+cost[u][v];
        }
    }
}

而数有几条最短路,新增一个数组num，令从起点s到达顶点u的最短路径条数为num[u]，最初num[s]=1其他为0,而会引起多条最短路的情况是在u这个点可以平等选择多个点：

for(int v=0;v<n;v++)
{
    if(vis[v]==false&&G[u][v]!=INF)
    {
        if(dis[u]+G[u][v]<dis[v])
        {
            dis[v]=dis[u]+G[u][v];
            num[v]=num[u];
        }else if(d[u]+G[u][v]==d[v])
        {
            num[v]+=num[u];
        }
    }
}

Bellman-Ford&SPFA

一旦出现负边权，Dijsktra算法就会失效。BF算法主要思想是设置一个数组d用来存放最短距离，同时返回一个bool值：如果其中存在从源点可达的负环，那么返回false；否则返回true，此时d中存放的值就是最短距离。

此时如果不存在从源点可达的负环那么d中所有值应该达到最优了，对所有边在判断一次，如果仍然可以松弛，就说明存在从源点可达的负环返回false。其复杂度是O(n*Edge).

for(each edge uTov)
{
    if(d[u]+length[uTov]<d[v]) return false;
    return true;
}

邻接链表：

struct Node{
    int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool Bellman(int s)
{
    fill(d,d+MAXV,INF);
    d[s]=0;

    for(int i=0;i<n;i++) //循环n次
    {
        for(int u=0;u<n;u++) //遍历所有边
        {
            for(int j=0;j<Adj[u].size();j++)
            {
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v])
                {
                    d[v]=d[u]+dis;
                }
            }
        }
    }
    //判断负环
    for(int u=0;u<n;u++)
    {
        for(int j=0;j<Adj[u].size();j++)
        {
            int v=Adj[u][j].v;
            int dis=Adj[u][j].dis;
            if(d[u]+dis<d[v])
            {
                return false;
            }
        }
    }
    return true;
}

BF算法主要是在O(VE)的E上开销太大了，但其中存在很多无意义操作，通过队列优化就得到了SPFA算法，复杂度降低为O(kE),k一般不超过2.
SPFA

弗洛伊德算法

全源最短路，囿于复杂度，一般一次能跑的节点不能超过200.

void Floyd()
{
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                //两者可达且可优化
                if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

再话图算法之图的遍历

发表于 2020-04-28 | 阅读次数:

前言

定义，出度入读，有向图无向图，点权边权，邻接矩阵，邻接链表，有向图的强连通分量，无向图的连通分量，连通块..

struct Node{
    int v,w;
    Node(int _v,int _w): v(_v),w(_w) {} //constructor
}
Adj[index].push_back(Node(3,4));

DFS

dfs
在实际的题目中，可能遇到比较坑的情况，比如要删边避免回路。
邻接矩阵实现：

const int MAXV=1000; //max vertices,设计算法不能超过千万级别复杂度
const int INF=1000000000;

int n,G[MAXV][MAXV];
bool vis[MAXV]={false}; //bool array要显式初始化

void DFS(int u,int depth)
{
    vis[u]=true;
    //do something for u in here
    /**/
    //下面对所有u能够直接到达的分支节点进行枚举
    for(int v=0;v<n;v++)
    {
        if(vis[v]==false&&G[u][v]!=INF) //未被访问且可达
        {
            DFS(v,depth+1);
        }
    }
}

void DFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(vis[u]==false)
        {
            DFS(u,1);
        }
    }
}

邻接链表实现：

vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false};

void DFS(int u,int depth)
{
    vis[u]=true;
    //do something at u in here
    /**/
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false){
            DFS(v,depth);
        }
    }
}

void DFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(vis[u]==false)
        {
            DFS(u,1);
        }
    }
}

一道比较好的题目在P359，有空回头刷刷。

BFS

邻接矩阵版：

int n,G[MAXV][MAXV];
bool inq[MAXV]={false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);

    inq[u]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v=0;v<n;v++)
        {
            if(inq[v]==false&&G[u][v]!=INF)
            {
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void BFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(inq[u]==false)
        {
            BFS(q);
        }
    }
}

邻接链表版：

vector<int> Adj[MAXV];
int n;
bool inq[MAXV]={false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int i=0;i<Adj[u].size();i++)
        {
            int v=Adj[u][i];
            if(inq[v]==false)
            {
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void BFSTraverse()
{
    for(int u=0;i<n;i++)
    {
        if(inq[u]==false)
        {
            BFS(u);
        }
    }
}

有时候需要给定BFS的层次，这时候需要进行一些调整。

struct Node{
    int v;
    int layer;
}

vector<Node> Adj[N];
void BFS(int s)
{
    queue<Node> q;
    Node start(s,0); //起始点s，层次为0
    q.push(start);
    inq[start.v]=true;
    while(!q.empty())
    {
        Node top=q.front();
        q.pop();
        int u=top.v;
        for(int i=0;i<Adj[u].size();i++)
        {
            Node next=Adj[u][i];
            next.layer=top.layer+1;
            if(inq[next.v]==false)
            {
                q.push(next);
                inq[next.v]=true;
            }
        }
    }
}

同样的好题在P365，有空回来看看。

再话二叉排序树

发表于 2020-04-27 | 阅读次数:

昨天复习了一下二叉树，却没有记录广义树。广义树采用静态实现，孩子域改成vector child，用来记录孩子节点的在静态数组中的index即可，比较复杂的情况是拿这棵树去DFS&BFS,其实也就那么回事。BST比较有用的特征是inOrderTraverse得到的是一个有序序列。

查找

一个平凡二叉树一般是没有特性的，而BST具有大小关系，所以可以选择其中一颗子树进行向下探测，所以查找将会得到一条路径。

void search(node* root,int x)
{
    if(root==NULL){
        //说明是空树
        printf("search failed\n");
        return;
    }
    if(x==root->data)
    {
        printf("%d\n",root->data);
    }else if(x<root->data)
    {
        search(root->lchild,x);
    }else{
        search(root->rchild,x);
    }
}

插入与建立操作

对一个BST，查找一个节点是顺着一条路径，因此如果能够查找成功，说明已经存在；否则，查找失败，说明这个查找失败的地方正是节点需要插入的地方，显然插入的复杂度是O(layer)级别的。插入和查找差不太多。建立一颗bst也就是插入一系列节点的过程。

void insert(node8 &root,int x)
{
    if(root==NULL)
    {
        root=newNode(x); //之前有过newNode的函数
        return;
    }
    if(x==root->data)
    {
        return; //已经存在，直接返回
    }else if(x<root->data){
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

node* Create(int data[],int n)
{
    node* root=NULL;
    for(int i=0;i<n;i++)
    {
        insert(root,data[i]);
    }
    return root;
}

需要注意的是，即便是一组相同的数字，如果插入顺序不同，最后生成的BST也可能不同。

BST节点删除

BST删除一般有两种方法，复杂度都是O(layer)，重点在于怎么保持删除后仍然是BST。对于给定节点，在BST中比节点权值大的最小节点为后继，比节点权值小的最大节点为前驱。所以我们需要先来寻找以当前节点root为根的树中的最大或者最小权值的节点，用于辅助寻找前驱或后继。

node* findMax(node* root)
{
    while(root->rchild!=NULL){
        root=root->rchild;
    }
    return root;
}
node* findMin(node* root)
{
    while(root->lchild!=NULL){
        root=root->lchild;
    }
    return root;
}

基本思路分为四步，第一步是root为空则return；第二步时如果当前root权值大于目的x，则说明要在左子树里面递归删除x的节点；第三步是如果当前root权值小于目的x，则说明要在其右子树递归去删除值为x的节点。第四步比较复杂，当root值等于目的x：

如果当前root没有左右孩子则说明是叶子直接删除
如果当前节点存在左孩子，则在左子树中寻找节点前驱pre，让pre的数据覆盖root，接着在左子树中删除pre。

如果当前节点存在右孩子，则在右子树中寻找节点后继next，让next的数据覆盖root，接着在右子树中删除next。

void deleteNode(node* &root,int x)
{
    if(root==NULL) return;
    if(root->data==x){
        if(root->lchild==NULL&&root->rchild==NULL){
            root=NULL;
        }else if(root->lchild!=NULL){
            node* pre=findMax(root->lchild);
            root->data=pre->data;
            deleteNode(root->rchild,pre->data);
        }else{
            node* next=findMax(root->rchild);
            root->data=next->data;
            deleteNode(root->rchild,next->data);
        }
    }else if(root->data>x){
        deleteNode(root->lchild,x);
    }else{
        deleteNode(root->rchild,x);
    }
}