算法分析与设计
渐进上界：得到一个问题规模充分大时一个算法的时间复杂度的上界
。
相同定义 渐进下界
渐进精确界：既是渐进上界，又是渐进下界
最优算法：算法A所在的算法类中的其他算法，在最坏（或平均）情况下，执行基本操作的次数不比A更少。
最坏情况下的排序次数使用W
最好情况下的排序次数使用B
平均情况下的排序次数使用A
第一章：排序问题
排序：n个数据元素按照key递增或者递减排序
n个元素的序列有n！种不同排列，每种排列用”Π“标记
一、直接插入排列
特点：每次比较后发生一次移动或者不发生移动
额外空间：o(1)
时间：
1.最好情况：待排序序列已经有序，需要n-1次比较，0次移动
2.最坏情况：待排序序列逆序，需要次比较，
次移动。
3.平均情况A(n)：求解所有情况的时间不现实，所以选则求解插入第i个元素时的平均比较次数，再求和
对直接插入排序的分析：直接插入排序每次比较操作最多移动一次数据，每次比较最多消灭一个逆序对，直接插入排序中有多少逆序对就要至少比较几次
最坏情况：待排序序列完全逆序，个逆序对，则其时间复杂度最少为
,且无法改进。
平均情况：技巧：两个相反情况的逆序共有个，每个占一半为平均情况,相反情况指的是对于两种情况，这两者的排序序列相反，所以这两种逆序对合起来共有这么多
note：直接插入排序这两种情况均无法再进行改进。
二、冒泡排序
将待排序的按照元素的key顺序两两比较，若逆序则交换，将最大的key元素换到了当前待排序序列的最后，若某趟冒泡没发生元素交换，那么排序结束
特点：最多需要n-1次冒泡，每次比较最多消灭一个逆序对
void bubblesort(Element E[], int n)
{
int numpairs;
int didswitch;
int j;
numpairs = n-1;//numpairs 记录当前趟比较的次数
didswitch = 1;
while(didswitch)//didswitch 记录当前趟冒泡是否交换过数据，没交换过则结束循环
{
didswitch = 0;//将didswitch置零
for(j = 0; j<numpairs; j++)
{
if(E[j]>E[j+1])
{
E[j]<->E[j+1];
didswitch = 1;
}
}
numpairs--;//每趟使得需要比较的数-1
}
}
证明冒泡排序的正确性：（数学归纳法）
时间复杂度：
B(n):最好情况：待排序序列已经有序，n-1次比较，0次移动 复杂度大小O(n)
W(n):最坏情况：待排序序列逆序，次比较，
次移动
A(n):假设每种情况出现的概率是相同的，可证
改进方法：每趟冒泡排序都跟踪第一次，最后一次交换的位置
void bubblesort(Element E[], int n)
{
int numpairs;
int firstchange,lastchange;//每趟冒泡排序第一次 ，最后一次发生交换的位置
int didswitch;
int j;
numpairs = n-1;//numpairs 记录当前趟比较的次数
didswitch = 1;
firstchange = 1;
while(didswitch)//didswitch 记录当前趟冒泡是否交换过数据，没交换过则结束循环
{
didswitch = 0;//将didswitch置零
for(j = firstchange - 1; j<lastchange; j++)
{
if(E[j]>E[j+1])
{
E[j]<->E[j+1];
if(!didswitch)
{
firstchange = j;//记录第一次交换时的位置
}
didswitch = 1;
numspairs = j;
}
}
lastchange = numpairs;
if(firstchange<1) firstchange = 1;
}
//通过及记录第一次交换时的位置，当前面排好序的时候，可以减少时间
}
三、分治策略
大规模问题分解为多个规模较小的问题——解决并合并为原问题的解
流程：划分->解决->合并
如果问题小于最小划分规模，进行直接求解，否则进行划分，然后进行小问题的解决，最后进行合并
分治策略的时间计算为划分时间+子问题解决时间，合并时间
下面的快速排序和归并排序的思想均为分治策略
四、快速排序
快排中的每趟若待排序序列为n个元素，则需要n-1次比较（随机选取一个基准，一般取首位，然后每位同基准进行比较，比基准大的放在后面，比基准小的放在基准前面），划分为2个子问题，基操作是比较操作，合并是自然形成的，代价为0。
最坏情况是每次划分两个子问题规模相差极大，分为0个和n-1个，此时的时间复杂度为
平均情况：假定待排序序列的所有排列出现的概率都相等，根据划分分为n种排列情况，每种情况出现概率设置为1/n。证明如下
估算证明过程过于复杂，这里就不做详细赘述，通过估算法或者直接推理法均可证明其时间复杂度为nlogn量级
直接推理方法证明
快速排序改进措施：
1.递归-》非递归
2.小排序问题采用直接插入法：当快排问题分成的问题规模小于等于16时候，改用直接插入算法更快
3.枢轴的选择：
3.1 预处理将待排序列随机打乱
3.2 选取基准
3.2.1 随机选择
3.2.2 每次选取尾元或者首元或者中间元或者（首+尾）/2
3.2.3 每次选取 （首元+尾元+中间元）/3
note：这些改进措施都可用于减少最坏情况出现概率，但都无法消除最坏情况出现的可能
void Qsort(Element E[],int first,int last)
{
int t;
if(first<last){
t=partition(E,first,last);
Qsort(E,first,t-1);
Qsort(E,t+1,last);
}
}
void partition(Element E[],int first,int last)//一趟快速排序
{
E[0] = E[first];
while(first<last)
{
while((first<last)&&E[last]>=E[0]){last--;}
if(first<last){E[first]=E[last];first++;}
while((first<last)&&E[first]<=E[0]){first++;}
if(first<last){E[last]=E[first];first++;}
}
t = first;
}
五、归并排序
思路：将待排序序列划分为若干有序子序列，再将两个及以上的有序子序列合并为一个有序序列
void Merge(Element E[],int s, int m, int t)// 自顶向下
//合并两个相邻的有序子序列 [s-m][m+1-t]
{
Element B[];//合并后的子序列存到B种
for(k=s,p=s,j=m+1;p<=m&&j<=t;k++)
{
if(E[p].key<=E[j].key){
B[k] = E[p++];
}
else {
B[k]=E[j++];
}
}
if(p<=m){
将E中剩余元素放到B中
}
if(j<=t){
将E中剩余元素放到B中
}
for(p=s;p<=t;p++){
E[p] = B[p];//将B中的元素放到E中
}
}
void Msort(Element E[],int s,int t)
{
if(s<t)
{
m = (s+t)/2;
Msort(E,s,m);
Msort(E,m+1,t);
merge(E,s,m,t);
}
}
归并排序中的主要操作是合并操作，合并两个有序子序列
最好情况：两个子序列刚好前后有序
最坏情况：两个子序列各元素交叉排序
特点：合并的时候每次比较至少排好一个数的位置到B[]中
二路归并排序空间复杂度o（n）；需要一个额外的n维数组B[]
依次进行合并，回写。
一趟归并，比较次数O(n)，移动次数2n，进行logn次合并，时间复杂度O（nlogn）
最坏情况：倒数第二次比较后，两个子序列中合并时两个子序列均只剩下一个元素
最好情况：一个子序列剩下一个元素，另一个子序列剩下所有元素
note：每一次合并相当于一次比较，最坏情况的意思是两个子序列中的数据放入B数组的时候总是我放一个，你放一个，这样剩下最后各一个元素。而最好情况是第一个子序列中的元素均小于第二个子序列的元素，所以一直从序列1中取出元素放入B中，当到达最后一步的时候，直接就可以将子序列2放到B中即可
因为子序列是有序
对于比较问题：
最坏情况下为nlogn
最好情况下（n/2）logn
note：最坏最好情况均为nlogn量级，但是系数改变
改进方法：
回写操作改进：交叉向E和B中写
递归改为非递归
小排序问题
先预处理一下，先做出一次扫描，找到无逆序对的最长有序子序列，同时把待排序序列划分
在合并时，若n《=20，做直接插入排序
note：归并排序没有快速排序快
六、小结1
基于比较操作的排序算法分析总结
| 算法 | 最好情况A(n) | 最坏情况W(n) |
| 直接插入排序 | ||
| 冒泡排序 | ||
| 快速排序 | nlogn | |
| 归并排序 | nlogn | （n/2）logn |
note:这两种情况在量级上无法改进
判定树可以表示任一基于比较操作的排序算法，对一个排序序列，任何一种基于比较操作的排序都可得到一棵高度相同，精度相同，但形状不同的具有相同叶子节点的判定树
这是一个对于快速排序和归并排序的演示
可以看到情况的不同会产生不同的子树，但是两颗树的高度是相同的
判定树为二叉树，非叶节点为比较操作，叶节点是可能的排序结果，（多种可能）对于n个数字排序而言，可以产生n!个叶子节点
使用判定树来分析各种基于比较操作的排序算法的性能
基于比较操作的排序算法在最坏时W(n)的下界为nlogn，即判定树的最小高度
证明
还有一种证明方法涉及到分部积分，这里不做提及
基于比较的排序算法最坏情况的时间复杂度的下界为nlogn，量级无法改进，只能改变系数
同时平均情况下的下界同样为nlogn
这个证明思路是通过公式得出A(n)，然后直接使用最高层所有叶子结点的高度和，并证明最高层的叶子节点数至少有/2，使用高度h乘以节点数即可
七、堆排序
大顶堆：父节点的数值大于左右孩子
小顶堆：父节点的数值小于左右孩子
堆的高度：根高度为1，结点高度等于父节点+1
堆属于偏序树，父子间有大小，兄弟之间无大小
堆排序流程：
1.对n个数据的序列初始建堆，大顶堆根为最大值，小顶堆根为最小值，建堆方法为筛选法和·插入法，
2.i=n，取出堆顶元素放在第i个位置上，i--
3.剩余元素重新调整为堆
7.1 建堆
筛选法建堆
1.从下到上，从右到左找到第1个非叶结点，i = [n/2]，从该节点为根的子树调整堆
2.取左右孩子，并取其较大值，该值和根比较，大于根则交换，否则不变
3.交换的情况下需要判断下移的结点是否破坏下面的堆结构，破坏则继续往下交换
4.使i--，重复上述过程
typedef SqList HeapType;
//L为序列，首先叙述流程，先从第一个非叶结点开始查找左右子树，左右孩子比它大就调换,然后继续向下调整
//建立大顶堆的伪码
void HeapAqust(SqList &L,int s, int m)//这个函数为堆以s为根的树的一次调整，使之为堆
{
int j;
L.r[0] = L.r[s];//根结点赋值给L.r[0]
for(j=2*s;j<=m;j=j*2){
if(j<m&&L.r[j].key<L.r[j+1].key)
j++;//比较左右孩子，取大值
if(L.r[0].key>=L.r[j].key)
break;
L.r[s] = L.r[j];//交换，把j结点放到s的位置
s = j;//s为刚交换的元素，继续向下调整堆
}
L.r[s]=L.r[0];//把最开始的根赋值到当前位置
}
筛选法建堆每次要调整一个结点，使得以这个结点为根节点的树为一个堆，一直向下检查
最好情况为：元素不变不需要移动，只需检查一层
最坏情况为：每层都需要移动，比较两次，一直到叶结点
插入法建堆
每插入一个数都与其父节点比较，判断是否破坏了堆
1.破坏了需要调整，父节点放到插入位置，A向上调一层，在判定A调到当前位置是否破坏了其上面的堆，若破坏了继续调整即可，子节点移动到对应位置即可，详情可查阅数据结构的插入法建堆
2.未破坏，插入结束，一次比较即可完成
3.在插入下一个数即可
void buildheap(SqList &L){
int i,j,flag,k;
for(i=2;i<=L.length;i++){
j=i;
flag=1;
while(j!=1&&flag){
k=j/2;
if(L.r[j].key<L.r[k].key){
L.r[j]<->L.r[k];
}
else
{flag=0;}
j=k;
}
}
}
证明方法同筛选法建堆：插入法建堆是O（nlogn）量级
而且由于筛选法建堆是O（n）量级，所以通常采用筛选法建堆
堆排序的最坏情况时间复杂度为nlogn量级，证明如下
可以看出，筛选法建堆优于插入法建堆
7.2 堆排序
void Heapsort(SqList L){
int i,j,k;
for(i=L.length/2;i>0;i--){//这里的length/2其实是找到第一个含有孩子的结点
HeapAqust(L,i,L.length);//初始建堆
}
//输出堆顶元素后，将堆的最后一个元素同堆顶元素交换，破坏堆的性质，重新进行筛选，最后得到排序顺序
for(i=L.length;i>1;i--){
L.r[0]=L.r[i];
L.r[i]=L.r[1];
L.r[i]=L.r[0];
HeapAqust(L,1,i-1);
}
}
流程为：
1.初始化堆O(n).
2.取出当前堆顶元素（1号），然后将最后一个元素放到堆顶
3.n = n-1 ，调整当前序列为堆
4. 重复2，3共n-1趟
改进措施一：不要每次都使堆底元素同堆顶元素交换位置，先放到额外空间上，堆顶元素空出的位置，由其子节点较大值代替，重复上述过程指导空出最下面层的一个叶结点，K放到该结点上，在观察K是否比其父节点大，K小，堆成立，K大，换位后继续比较
此改进措施的W(n)小于2log（n-1）
对于改进一的改进
重复过程到树高的一半，把K放到此位置，然后进行比较决定是上升还是下降
log（n-1）+loglogn
note:k为最后那个叶子结点
八、希尔排序
希尔排序思路：
1. 大问题划分为小问题
2.小问题采用直接插入排序（当问题规模小于16时，A（n） = O（n^2/4）相较于nlogn快）
3. 小问题完成后再一步步的合成大问题（分治策略反着来（分治策略为大问题划分为小问题））
流程：
1. 设定正整数增量 ht<n,即将n个元素分为ht组
2.各组内进行直接插入排序
3.再取正整数增量ht-1，重复1，2的分组排序，直到h1 = 1，共t趟
h1恒等于1，最后一趟排序所有元素
九、桶排序
不基于比较的排序，要求关键字的取值范围是已知的
流程为
1. 分配关键字，根据每个元素的关键字的值将其分配到对应的桶中-》O(n)
2.每个桶内部分配的元素按照某种排序算法排序，取决于具体选择什么排序算法
3.收集桶：收集的时候按照关键字将k个桶队列首尾链接即可
十、基数排序
思路：多关键字的思想，（要求每个关键字取值范围已知）
方法：低位有限LSD
1.先对k^(d-1) 进行桶排序，再依次对k^(d-2)……进行桶排序
2.总共做d趟
使用静态链表进行存储，基数排序各元素基础位置不变，只是改变了相应的指针
每进行一趟得到关于一个关键字的序列，再将此序列进行桶排序即可，一共d趟
int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int maxData = data[0]; ///< 最大数
/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
for (int i = 1; i < n; ++i)
{
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p)
{
//p *= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete []tmp;
delete []count;
}
第二章：选择问题
在n个元素的序列中选择极值元素，次元，中间元等。
策略：
1.排序策略：把数组排好序，然后直接取出第k个元素
总之：每个具体问题的解决都可以想出很多具体实施算法，都是结合各种排序算法想出来的流程
对策论
对于一个具体的选择问题p，分析求解基于比较的解决策略的时间复杂度下界用来评判对问题的p的解决策略是不是一个好策略
基于比较的选择问题：n个元素找第k小，不同的算法节点数不同，无法确定树高，故无法使用决策树
T指的是针对一种具体输入I，使用解决方法A的时间复杂度
上述式子的意思是针对问题p所有揭发最坏时间复杂度的最小值，即该问题p的下界
这样的算法在W(n)中是最好的，那么这个算法就是这个问题的最好解法
对策论：构造一套对于一切解决问题p的算法都适用的输入策略，从而问题求解做尽量多的比较和判断，即在相应的输入策略下，时间复杂度尽可能大
Find max
方法一
max = E[1];
min = E[1];
for(index = 2;index<=n;index++)
{
if(E[index]>max) max = E[index];
if(E[index]<min) min = E[index];
}
#总计2n-3次比较
方法2
冒泡排序
find max 用n-1次比较
find min 用n-2次比较
上述方法find max 和 min 各自单干
方法三
进一步优化，降低比较次数
当n = 2k时，E[i]与E[i+1]比较，胜者放在A数组，败者放在B数组，然后再各自进行比较
若n个数据元素中x为max,y为min，那么 除了x外，其他的数据元素在比较中都失败过； 除了y外，其他的数据元素在比较中都胜过。
若把输赢作为一个信息，至少需要2n-2个信息
每一个数据元素的状态有以下4种：
1. W：从未失败，至少赢过一次
2. L：从未赢过，至少失败一次
3. WL：既成功过，也失败过，至少各一次
4. N：尚未参加过比较
初始时，所有元素均未参加比较，状态都是“N”
若n为偶数
初始所有的数据元素状态均为N。
一次比较获得2个信息只有(N,N)这种情况。而这种情 况最多进行n/2次，获得n个信息。即：经过n/2次比较， 最多获得n个信息。
其他每次比较最多产生1个信息，还需 2n-2-n=n-2个信 息，至少需要n-2次比较
所以至少要进行n/2+ n-2次比较。
若n为奇数
初始所有的数据元素状态均为N。
一次比较获得2个信息只有(N,N)这种情况。而这种情 况最多进行（n-1）/2次，获得n-1个信息。
其他每次比较最多产生1个信息，还需 2n-2-n+1=n-1个 信息，至少需要n-1次比较
所以至少要进行(n-1)/2+ n-1次比较。
找次大元
任何一个败给最大元以外其它数据元素的都不可能成 为次大元
锦标赛法-二叉树
使用锦标赛法找最大元，可以为寻找次大元提供更多有用信息
找次大元前先寻找最大元，n-1次比较
直接失败于max的元素有[log n]（向上取整）
随后在和最大元比较直接失败的元素中寻找最大元[log n]（向上取整）-1次比较
算法实现（数组）
for(last = 2*n-2;last>=2;last-=2)
if(E[last]>E[last+1])
E[last/2] = E[last];
else E[last/2] = E[last+1];
//使用一个数据存储，尾部为叶子结点，数组长度为所有结点数
//上述代码为寻找最大元，并且把最大元存储在数组首部
寻找次大元
max = E[1];
second = -OO;
i=1;
while(i<n){
i=i*2;
if(E[i]!=max){i = i+1; if(E[i]>second) second = E[i]}
else {if(E[i]>second second = E[i+1])}
}
证明：n个数据元素中找次大元最坏情况下至少需要 比较n+[log n]-2次
首先确定最大元，保证second不是最大的（对策论：构造最坏输入，使得最大元候选多）
给每个数据元素赋权重w(x),初始w(x)=1。
一次比较后，败者将权重全部转赠给赢者，其权重变为0。
奇数个比较会使得其中一个元素直接进入下一轮，如本例题中的x3
查找中间元--分治法
将E[]中的数据元素分为两个集合S1，S2，S1元素均小于S2元素，则中间元去数据元素多的集合中找，借助一趟快速排序进行划分
最好情况下，划分很均匀，一次划分找到中间元
对坏情况下，两个子序列太极端，相差过多，要进行多次划分才能找到
将p个元素为一组，确定每组中间元，构成集合M，然后求解M中间元m，将中间元划分为如下图所示的四个区域
每组数从上到下按从大到小排序
证明：找中间元问题再n为奇数的时候，最坏情况下要比较至少3/2n - 3/2次
使用对策论构造最坏输入策略
尽可能让每次比较均为非关键比较，要得到中间元，就要得到n-1/2个s和n-1/2个l
关键性比较至少要n-1次，非关键比较在最坏情况下为n-1/2次 （与一个小于中间元的数比较，比这个数大）
在最坏情况下，求n个元素中第k 小的数据元素至少需要n+min(k，n-k+1)- 2次比较
第三章：查找问题
1.顺序查找
用可变长度数组存储动态集合，使用可变数组空间代替静态数组，查找时间复杂度在O（n）量级
先分配一个小数组，需要时，数组空间加倍，将原空间的数组移动到新空间，额外数据的移动工作在o（n）量级
2.红黑树
红黑树是满足特定结构要求的二叉搜索树
n个结点的红黑树高度不超过2log（n+1）
所有外部结点均为黑色
链接向黑结点的边为黑边
黑色长度为改路径上的黑边数量
黑色深度为根节点到该节点的黑色长度
红黑树定义
二叉排序树
结点为黑色或红色
根结点为黑色
所有外部结点均为黑色
每个红色节点的两个子结点均为黑色，不能有两个连续的红色结点
关键性质
从根到叶子的最长的可能路径不多于最短的可 能路径的两倍长。
下列结点颜色为红或黑、外部结点为黑色的二叉排序 树是RBh和ARBh ：
(1)一个外部结点是一个RB0
(2) h≥1时，一个二叉排序树是ARBh ----其根为红色，左 右子树均为RBh-1
(3) h≥1时，一个二叉排序树是RBh ----其根为黑色，左 右子树均为RBh-1或ARBh
引理和证明
1.RBh树和 ARBh树的黑色高度为h.
设T为RBh
T至少有2^h-1个内部黑结点
T至多有4^h-1个内部结点
任一黑结点的深度至多为其黑深度的2倍
证明：设T为有n个内部结点的红黑树，没有结点深度大于 2log(n+1)，即树的高度最多2log(n+1)
红黑树插入删除虽然很复杂，但是操作时间依然可以维持在o(log n)
1. 插入位置----根据二叉排序树的定义确定
2. 新插结点初始颜色为红色
3. 若新插结点为根结点，将其改为黑色，插入操作结束；否则若其父结点为黑色，则插入操作结束；否则进行调整
4. 设新插结点为N
簇cluster：内部结点集，包含一个黑结点， 所有由该黑结点通过非黑边能够达到的 红结点
临界簇：如果簇中存在一个结点由簇的 根到该结点路径长度大于1。
在插入过程中，如果树中不存在临界簇，那 么符合红黑树的定义，不需要调整
新插结点为N，其父节点P，祖父节点G，叔父节点U
如果叔父节点U也是红色，则将改变P和U的颜色为黑 色，改变其祖父节点G为红色
现在新节点N有了一个黑色的父节点P。因为通过父节 点P或叔父节点U的任何路径都必定通过祖父节点G， 在这些路径上的黑节点数目没有改变。
红色的祖父节点G的父结点也有可能是红色的，将G 当成是新插入的节点继续进行调整
新插结点为N，其父节点P，祖父节点G，叔父节点U
叔父结点U是黑色或缺少：
(1) (新插结点N的父)结点P是P的父结点G的左孩子
新结点N是其父结点P的左孩子----右单旋转----调换P和其父结点的颜色;
新结点N是其父结点P的右孩子----先左后右双旋转----同时修改颜色;
(2) (新插结点N的父)结点P是P的父结点G的右孩子
新结点N是其父结点P的右孩子----左单旋转----调换P和其父结点的颜色;
新结点N是其父结点P的左孩子----先右后左双旋转----同时修改颜色;
口诀：叔叔红，倒三角，叔叔黑，中间做根红，孩子左右给
第四章 动态等价关系与并查集
第五章 图
图的存储：邻接矩阵，邻接表
深度优先遍历搜索
从图中某个未被访问的顶点v0 出发，访问此顶点，然后依次从v0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v0有路径相通的顶点都被访问到。
若图中仍存在未被访问的顶点，则从中选择一点做出发点，重复上述过程，直至图中所有的顶点都被访问到。
时间复杂度
邻接矩阵存储----O(n+n2 )
邻接表存储----O(n+e)
广度优先遍历搜索
从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
若图G中任意两个顶点之间都 有路径相通，则称此图为连通图
若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。
有向无环图拓扑排序
拓扑排序定义：
图G=(V,E)是n个顶点的有向图。图G的拓扑排序（toplogical order）是指给图中的每一顶点赋予1,…,n的不同整数，使得如果vw属于E,则v的拓扑序号小于w的。
定理：若有向图G中存在回路，则G不存在拓扑排序
深度优先搜索生成树
1. 若w是undiscovered的，则vw称为tree edge，v变成w的父节点（深度优先搜索生成树）
2. 若w是v的祖先，则vw称为back edge（包括vv这种情况）出现回边，代表图有回路
3. 若w是v的子孙，且在此前已经被discovered，则vw称为desendant edge
4. 若w和v没有任何ancestor/descendant关系，则vw称为cross edge
无向图的边只有tree edge and back edge
设计时器time，初始为0，每访问一个节点time+1，每结束一个结点的深度优先搜索 time+1
深度优先搜索过程记录每个结点v的discoverTime(v) 和finishTime(v)
discoverTime(v)：结点v的被访问的时间
finishTime(v) ：从结点v出发做深度优先搜索结束的时间
利用时间可以判断一条边是否为回边等
割点
一个联通图如果删除任意一个顶点与其相邻的边，仍然是联通图的话，称其为二连通图
割点：无向图若存在2个不同的点x，w。二者之间任一个路径都包含顶点v，则称v是图G的一个割点
采用深度优先遍历搜索对边进行划分和判断割点
假设在深度优先搜索过程，从dfs（G，w）返回到v，在以w为根的子树上的结点不存在回边指向v的真祖先，那么v是割点
在深度优先搜索树中，若v不是根结点，那么v是割点当且仅当v不是叶子结点，v存在一棵子树，其上的结点不存在回边指向v的真祖先
检测二联通分量的条件
back = discoverTime[v];
back = min(back,dicoverTime[w])
back = min(back,wBack)
当w返回v时，若wBack >= discover[v] -> 发现一个二联通分量
第八章：图的优化问题和贪心算法
最优化问题：根据问题给出的某些约束条件，满足这些约束条件的姐被称为可行解，有一类问题的可行解不止一个，其中最好的解称为最优解，给定一个问题，给出一个要优化的目标函数，求解最优解，即为最优化问题
最优子结构性质：但一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
note：问题具有最优子结构性质是该问题可用贪心算法或者动态规划算法求解的关键特征
1.贪心算法
思想：总是做出当前看来最好的选择，并不从整体最优来考虑
某种意义上是每一步都是局部最优选择，一步步产生全局解
缺点：由于贪心算法不是从全局考虑，所以它得到的解不一定是整体最优解
我们希望得到全体最优解，但到底是不是需要我们进行证明
特点：
贪心算法是迭代算法，一步一步进行的
贪心算法是自顶向下的，不做试探，没有回溯，每次做一个贪心选择就将所求问题简化为一个规模更小的子问题，最后得到问题的一个最优解
贪心选择性质：如果一个问题的整体最优解可通过一系列局部最优的选择最终得到，则这个问题具有贪心选择性质
图优化问题：最小生成树
图的DFS产生的生成树是否是最小生成树？ 答：不是
最小生成树：权值最小的树
1、Prim算法构建最小生成树
算法设计：
G=(V,E)是联通网，V和E是最小生产树的点集和边集，初始状态：U={u0|u0∈V}，E为空集合
a. 从V和V-U中的点中构成的边中，找一条权值最小的边加入E中，v0并入U
b. 重复a，直到U=V为止，此时E中共有n-1条边，构成了最小生成树
算法实现：（使用优先队列实现）
优先队列内部存放：
1.候选结点与生成树中的节点相连的所有边中权值最小的边
2.候选结点
3.候选结点通过改变与树中相连的结点
算法流程：
初始顶点加入队列
队列不空，通过锦标赛算法getMin边
相应候选结点加入生成树
从队列中删除该点
找到当前生成树所有的候选顶点
更新候选结点和当前候选边
新的候选结点插入队列-》重复二
算法时间复杂度为o(n方)
prim算法是贪心算法，不一定找到的生成树是最小生成树（MST）
第十章：动态规划
以空间换时间：让时间复杂度从指数数量级降低到多项式数量级
思想：将待求解问题分为若干子问题
分解的子问题往往不是相互独立的
需要保存已经求解的子问题答案
例子1：斐波那契数列问题
当n大的时候，可以将Fn的问题划分为Fn-1和Fn-2的问题
分治策略的代码如下：
时间复杂度为2的n/2次幂，为指数量级算法，原因在于计算量重复的子问题
int feibonaqi(int n){
int f,f1,f2;
if(n<2)
f=n;
else
f1=feibonaqi(n-1);
f2=feibonaqi(n-2);
f=f1+f2;
}
动态规划策略：
自底向上方法:时间复杂度为O(n),空间复杂度为O(2).
if(n<=0) return n;
prev1=0;
prev2=1;
for(i=2;i<=n;i++)
cur=prev1+prev2;
prev2=prev1;
prev1=cur;
return cur;
例子2：青蛙跳台阶
f(1)=1,f(2)=2
f(n)=f(n-2)+f(n-1) 如果第一个跳一级台阶，那么就剩下f(n-1)方法，第一次跳二级台阶，那么就剩下f(n-2)种算法
动态规划：自底向上（从规模最小的规模向上求解），自顶向下（从问题开始向下求解）
关键在于找到递推关系
例子3：币值最大化
给定一排n个硬币，其面值均为整数C1,C2,C3...，这些整数并不一定两两不同，问如何选择硬币，使得其在原始位置互不相邻的条件下，所选硬币金额最大。
设所选硬币的最大金额为F(n),根据问题将可行的选择分为两组
第一组为包含第一枚硬币：表示为Cn+F(n-2)
第二组为不包含第一枚硬币F(n-1)
进而得到递归方程F(n)=max{Cn+F(n-2)，F(n-1)}
F(0)=0,F(1)=C1
10.1 矩阵连乘积
多个矩阵相乘：由于矩阵乘法满足结合律，改变计算次序可以改变计算次数
确定一个策略，确定n个矩阵最优连乘次序
方案1：穷举法
列出所有可能的计算次序，并计算出每一个计算次序所需要的计算次数
时间复杂度为（n-1)！
方案2：贪心法（不能得到最优解）
贪心策略1：每次选择计算量最少的两个矩阵相乘
贪心策略2：每次消去维数最大的数，比如一个矩阵可以分为m维✖n维
贪心策略2对于：A:20✖2,B:2✖15,C:15✖40,D:40✖4无法得到最优解
方案3：最优子结构性质
自顶向下：从i乘到j记为A[i:j]
设这个计算次序在矩阵Ak和Ak+1之间隔开，则其相应为A[i:k] A[k+1:j]
矩阵连乘的行列存放在dim[0,n]----对dim数组操作
mmTry2(dim,low,high){
if(high-low==1) bestCost=0;
else bestCost=∞；
for(k=low+1;k<high;k++)
a=mmTry2(dim,low,k);
b=mmTry2(dim,k,high);
c=cost of mult at k;
bestCost = min{bestCost,a+b+c};
return bestCost;
}
动态规划
从规模为1的子问题开始，先把所有规模为1的子问题全求解出来，再用规模递增的顺序依次求解所有规模为2的子问题，为3的，一直到为n的问题，这样调用的优点是求解一个问题，他的所有可能的子问题的解一定都能被求出，只需要直接拿来找最优解即可
（A1,An）为原问题，其余的都为子问题
cost[i][j]:纪录（Ai，Aj）子问题的最优解，即最少数乘次数
last[i][j]:记录子问题的最优解方案是如何断开的，要使用j-i此-次找到最小值
void matrixchain(int *d, int **cost, int **last){
for(i=1;i<=n;i++){cost[i][i]=0;last[i][i]=-1;}#初始化
for(l=2;l<=n;l++)#L表示问题规模
for(i=1;i<=n-l+1;i++)//处理规模为l的问题是，i取值在1~n-l+1，j取值在l-1~n
{j=i+l-1;
cost[i][j]=cost[i][i]+cost[i+1][j]+d[i-1]*d[i]*d[j]-;
last[i][j]=i;
for(k=i+1;k<j;k++)
{t=cost[i][k]+cost[k+1][j]+d[i-1]*d[k]*d[j];
if(t<cost[i][j])
{cost[i][j]=t; last[i][j]=k;}
}
}
}
从k处断开，last存储断开位置，计算每次断开后其余位置断开的各个计算值，取最小
最优二叉搜索树问题
问题：n个元素建立一棵二叉搜索树，在全部查找成功的情况下，怎么坚力这颗二叉树使得平均检索时间最小
策略为四种：
1.穷举法：计算所有可能的二叉树平均检索时间： 4的n次方
2.贪心法：不一定保证正确
3.分治策略
4.动态规划
考虑一个无穷大的栈，进栈序列为1~n，有多少种出栈序列和n个结点二叉树的时间复杂度保持一致
证明：日后补上
故考虑栈的方法：
对于每个元素：必须进栈一次，出栈一次
设进栈为状态‘1’，出栈为状态‘0’，n个数据元素的进出栈状态对应2n位二进制数
note：1的数量必须比0的数量多，入栈的数量大于等于出栈的数量
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
14
0- 0
已为社区贡献3条内容
所有评论(0)