针对数据结构的部分学习笔记。
栈
出栈排列个数：\(C_{2n}^n\)，卡特兰数
栈模拟
中缀转后缀
原理：
中缀转后缀的原理是单调栈(维护一个优先级递增的栈)，从栈底到栈顶的优先级必然递增，输出时可以保证优先级高的先输出(出栈)。中缀表达式和后缀表达式的不同仅在于符号位置不同，数字之间相对顺序是一样的，因此遇到数字可以直接输出，而遇到符号需要考虑其相对顺序（优先级），中缀转后缀仅遵循一条原则，优先级高的先输出，相同优先级不能改变相对顺序。因此，用单调栈存储递增的优先级符号，在出栈时判断优先级是否相等(相等时需要将先入栈的元素先输出)和大于(大于时显然需要出栈)，达到目的。
算法：
一个符号栈，遇到数字输出，遇到符号先将栈中大于等于自己优先级的输出，再入栈，遇到“(”直接入栈，遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(” 为止，注意:“(” 不加入后缀表达式。
后缀表达式计算
原理：
由中缀转后缀之后，连续的符号的优先级(假设括号提升了某些算符的优先级)一定是单调递减，非连续的算符之间被数隔开(最后一个算符优先级相同)，而运算原则是优先级高的先运算，相同优先级的从左到右运算，因此从左到右扫描，遇到符号序列直接运算即可，因为整体先算优先级最高的和局部先算是等价的，最终由于数字的分割，最后运算符一定是相同优先级的，故而等价。简单画个草图：
算法：
一个结果栈，从左到右扫描，数字入栈，符号pop俩数字算结果之后再入栈，直到扫描完毕。
字符串
KMP算法：
思路：
本质：下一个潜在匹配位置等于前面字符串的最长公共前后缀长度，因为长度等于最后一个相等位置下标+1，即长度代表下一个位置，即绿色图形的长度（由本质关系可以直接手推next数组而不考虑算法实现）。因此next表和dp数组关系:
\(next[i] = dp[i-1]\)
最长公共前后缀的dp转移方程：
\(dp[i] = j+1 \quad if \quad s[j] = s[i] \quad else \quad j=dp[j-1] \quad recursively\)
其中\(dp[i]\)表示\([s_0,s_1,\cdots,s_i]\)的字串的最长前后缀的长度。\(j\)初值为\(dp[i-1]\)，\(s[i]=s[j]\)时，j是下标，因此长度等于\(j+1\)；否则情况下，两边的前面的元素已经相等，再找更里面的疑似位置，即\(dp[j-1]\)。
排序
0.. 稳定性分析
排序稳定是不改变元素间相对位置。
排序的稳定性取决于实现，但显然实现稳定的算法可以减少一次key相同时的交换，所以能以稳定的方式实现尽量时以稳定的方式实现，不会故意实现一个不稳定的（稳定的算法可以故意实现一个不稳定的版本，纯属闲的）。。
一个稳定的排序算法可以减少数据的移动，如果待排序的数据是一个很大的object，那么稳定的排序算法将节约很多数据移动带来的损耗（稳定排序的实际意义）。
插入排序：稳定，比较到元素相同的时候，就放到这个相同元素的后面，不会再交换一次。
冒泡排序：稳定，比较到元素相同的时候就停止了，不会再交换。
归并排序：稳定，相同的元素在不同子序列中，合并的时候如果元素相同，则优先放置左边的子列元素，可以实现稳定。
基数排序：稳定，可以人为控制相同桶编号的元素进出桶的顺序和原序列顺序一致，因此可以实现稳定。
选择排序：不稳定，很显然存在小元素在与当前元素相同元素的后面时，需要交换小元素和当前元素，破坏稳定性。
快速排序：不稳定，选一个数放到最终的位置上去，假设从右选取元素，往左的比较到相同元素时，可能左边的不满足小于等于自身，此时需要交换左边比自己大的元素和自己，这时候显然破坏了稳定性。
堆排序：不稳定， 假设有两个相同元素，根节点在排序被替换成了比这两个元素小的元素，这两个元素是此时最大的元素，则需要将这两个元素之一提到根节点去输出，而这两个节点在原序列中的顺序可能会在建堆的时候变掉，建堆时，一个元素在前面一半，另一个在后面一半，down操作可能会把前面的那个元素放到后面元素的后面作为叶子节点，因此在排序的时候无法通过左右顺序来恢复原始顺序。因此不稳定。
希尔排序：不稳定，相同元素可能会被划分到不同的子序列，子序列排序时可能破坏相对顺序。
基于比较的排序算法，最坏情况下最少的比较次数为：\(\log_2 (n!) = \Theta(\log_2(n))\)，每次比较产生两种结果，最多有\(n!\)种结果，所以\(2^m \geq n!\)，所以\(m=\log_2 (n!)\)
- 插入排序
从第2个元素开始，往前面的元素插入新元素。
时间复杂度分析：
best case：每次插入仅比较一次，放在原位置，时间复杂度\(O(n)\)。
worst case ：时间复杂度\(O(n^2)\)。
average case：插入第i个元素时，平均比较的次数
分析时考虑所有permutation下的情况的平均：
如图前面i个元素已经排序好，\(C_{i:j}\)表示下标为i的元素插入到已排序表的下标为j的位置需要的比较次数，显然\(C_{i:j} = i-j+1\)，那么一趟的平均比较次数就为\(\overline{C_i}=\sum_{j=0}^{j=i} i-j+1 = \frac{i}{2} + 1-\frac{1}{i+1}\)
由于每次排序都要走n-1趟，所以总的比较次数就为
\(\overline{C} = \sum_{i=1}^{i=n-1} \overline{C_i} = \frac{(n-1) n}{4}+n-H_n \in \Theta\left(n^2\right)\)
其中\(H_n = \sum_{k=1}^n \frac{1}{k}\)
空间复杂度分析：
\(O(1)\)
稳定性分析：
稳定。比较到元素相同的时候，就放到这个相同元素的后面，不会再交换一次。
初始状态影响分析：
比较次数和初始序列有关，最好情况下每趟比较1次，不发生交换。
- 堆排序：
建堆：从\(\frac{n}{2}\)位置开始往前down，因为后面一半最终一定全是叶子节点，前面一半都经过down了之后，后面半段显然不需要在down了；堆排序：每次第一个元素和最后一个元素交换，然后down。
时间复杂度分析：
建堆：
第h层最多有\(2^{h-1}\)个节点，向下down的次数为\(H-h\)
所以\(\sum_{h=1}^{h=H} 2^{h-1}(H-h)\)
这里可以用数列推导一下，
\[A_H = \sum_{h=1}^{h=H} 2^{h-1}(H-h) \\ A_{H+1} = \sum_{h=1}^{h=H+1} 2^{h-1}(H-h) \\ =\sum_{h=1}^{h=H} 2^{h-1}(H-h) + \sum_{h=1}^{h=H} 2^{h-1} + 0 \\ =A_H + 2^H -1 \]递推一下，\(A_H = A_{H-1} + 2^{H-1} -1 = A_{H-2} + 2^{H-2} + 2^{H-1} -2 = \cdots = A_1 + \sum_1^{H-1}2^h - (H-1)\)
又因为\(H = log_2n + 1\)，带入有\(A_H = 2n-2-log_2n\)
因此时间复杂度为\(O(2n) = O(n)\)
排序：
best case：无论什么permutation，由于交换首尾数据，总是会破坏堆的定义，因此每趟都需要down一下。时间复杂度为\(O(nlogn)\)
worst case：同理，时间复杂度为\(O(nlogn)\)
average case: 时间复杂度为\(O(nlogn)\)
应用：priority_queue，注意，stl里用于compare的函数需要和堆排序对应，最大堆在经过堆排序之后是从小到达排列的，因此compare函数对应的是less，这和其他排序算法是一致的。
空间复杂度分析：
\(O(1)\)，对数组而言是in-place的，不需要额外的空间。(down等操作可以用循环实现，无需递归)
初始状态影响分析：
如果序列已经是最大堆且排序好了，构建堆的时候则不需要down，每个节点和自己的两个子节点比较一下即可；而如果初始序列是最小堆且有序，构建堆的时候不仅要和两个子节点比较，还需要进行递归的down操作，每次down里面会有比较操作，所以比较操作会增加。因此初始状态会影响比较次数。需要注意的是，构建堆的时间复杂度分析时我们考虑的是down的次数，而不是比较次数。
- 快速排序
利用的是分治思想，每次找到一个枢纽量，确保枢纽量前的元素小于等于自身，枢纽量后的元素大于等于自身，返回子序列处理后的枢纽量的位置，递归对枢纽量左边的子序列和右边的子序列做这样的处理，直到所有子序列处理完。
实现一个partition函数，递归调用之。
partition函数常用两种实现，一种是两边同时往中间找到第一个不满足的元素，不断交换使之满足，最后得到两遍均满足定义的位置；另一种是从左到右同时维护两个子序列，如果元素比待比较元素小，则交换使之进入左边的子序列，否则不处理(因为此时一定是在右边的子序列中)，如图：
时间复杂度分析：
worst case：树高为\(n\)，时间复杂度\(O(n^2)\)
best case：树高为\(logn\)，时间复杂度\(O(nlogn)\)
average case：
平均时间复杂度即是求平均的比较次数，树中节点总比较次数记为\(X = \sum_i \sum_j X_{ij}\)，其中如果节点i和节点j比较了则\(X_{ij}=1\)，否则为0。即求\(E[X]\)。
\[E[X] = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} E[X_{ij}] \]假设i和j交换的概率为\(p_{ij}\)，则根据其分布律可以得到\(E[X_{ij}] = 1 * p_{ij} + 0 * (1-p_{ij}) = p_{ij}\)
因此\(E[X] = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} p_{ij}\)，而对于任意序列\([s_i,s_{i+1},\cdots,s_j]\)节点i和j而言，只有在节点i或者节点j被选为pivot时两者才有机会比较，否则一定会被分到两个subarray中去，从此不再有比较的机会。
因此对于序列\([s_i,s_{i+1},\cdots,s_j]\)，随机选取pivot时仅有两种情况满足要求，其概率\(p_{ij} = \frac{2}{j-i+1}\)。
所以，平均比较次数为，令\(k=j-i+1\)
\[E[X] = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \frac{2}{j-i+1} \\ = \sum_{i=0}^{n-1} \sum_{k=1-i}^{n-i} \frac{2}{k} < \sum_{i=0}^{n-1} \sum_{k=1}^{n-1} \frac{2}{n} \\ =\sum_{i=0}^{n-1} O(2log(n-1)) \\ =O(2nlog(n-1)) = O(nlog(n)) \]所以时间复杂度为\(O(nlogn)\)
空间复杂度分析：
\(O(logn)\)，快排的实现基于递归，调用栈里最要要存树高个函数调用信息。
初始状态影响分析：
比较次数和初始序列有关，快排比较的树每层比较次数和都是\(O(n)\)，总的比较次数就是\(O(hn)\)，因此总比较次数取决于树高，初始序列基本有序时树退化为度1的树，此时比较次数次数最多。
- 基数排序
优先级高的后排。
时间复杂度分析：
worst case: \(O(nd)\)，每趟都要把所有元素放到桶里，再取回，走d趟。
best case: \(O(nd)\)
average case: \(O(nd)\)
空间复杂度分析：O(d+n)
-
希尔排序
每次选择递减的增量划分组，组内进行插入排序。可以优化的是，组间可以用多线程并行排序。 -
冒泡排序
两两比较，大的在右。如果某一趟中没有调用元素交换，则已完成排序。因此比较次数也是和初始序列有关的，因为最好情况下只需要一趟。
- 选择排序
每次选择最小的放到左边，因此这个选择的过程需要比较所有剩余元素，比较次数和初始序列无关。
- 计数排序
数小时，开个数组，把数存到以他为key的数组里去，遍历数组把存的数据全输出。
- 归并排序
思想是分治算法，每次将序列进行二分分组，然后对两个子序列再次调用递归，之后将两个分组进行合并。
顺序统计量
最大/小值
时间复杂度：\(\Theta(n)\)
快选
求解第k大数，利用快排：
PARTITION(arr,l,r)
x = arr[r]
i = l-1
for j=l to r-1
if(arr[j]>= x)
i=i+1
swap(arr[j], arr[i])
i=i+1
swap(arr[i], arr[r])
return i
RANDOM_PARTITION(arr,l,r)
i = RANDOM(l,r)
swap(arr[i], arr[r])
return PARTITION(arr,l,r)
QUICK_SELECT(arr,l,r,k)
idx = RANDOM_PARTITION(arr,l,r)
if(idx == k) return arr[idx]
if(idx>k) return QUICK_SELECT(arr, l, idx-1, k)
return QUICK_SELECT(arr, idx+1, r, k)
时间复杂度分析：
随机pivot导致左边两边大致相等，快选只对一边递归，所以递归树为单子节点树，问题规模每次变成原来一半：
\[T(n) = T(n/2) + n \]根据主定理，平均时间复杂度为\(\Theta(n)\)
最坏时间复杂度：还是\(\Theta(n^2)\)，递归树高为n。。
改进快选-BFPRT算法
想法：用序列的中位数作为pivot划分子数组，则一定平衡。
近似：数据分成\(n/5\)组，每组5个元素，求每组中位数(5个里的中位数)，得到\(n/5\)组中位数，再取这些中位数的中位数，作为pivot划分。其他和快选一样。
时间复杂度分析：
最坏时间复杂度\(\Theta(n)\)，其中问题规模n需要大于一个常数值才能得到这样的复杂度。
树
结论
节点数 = 边数+1 = 度和+1
树的度：Max(节点度)
非空二叉树叶子结点个数：度2节点数+1
二叉树后序遍历 = 二叉树前序先右后左遍历的序列的转置，即(中右左)^T = (左右中)
→ 如果前序序列=后序序列，说明(左右中)=(中左右)，此时只有左右都为空树时成立，即只有根节点
→ 如果前序序列=后序序列的转置，(中左右)=(中右左)，此时需要保证每个节点只有左子树或者右子树或者左右子树都为空才能成立，即该树的度不能超过1
n个节点的二叉树有n+1个空指针域
森林转二叉树：左孩子右兄弟
二叉树的顺序存储时，最后一层的null也要存完，空间要算上。
分支节点：有孩子的节点。
Full Binary Tree： 二叉树中每个节点度要么是0要么是2
Perfect Binary Tree：填满的二叉树
Complete Binary Tree：除了最后一层不满其他都满
牛逼程度：Full < Complete < Perfect
二叉树遍历(非递归)
先序遍历：主流有两种实现，一种实现是用栈存储访问优先级从低到高(栈顶优先级高于栈底)，入栈时确保栈的“单调”。另一种实现是用栈存储访问路径，单独用一个指针指向栈顶元素的后继，如果栈顶元素有右孩子，则该后继为右孩子，若栈顶元素无右孩子，则需要出栈找下一个栈顶元素的后继。
对于第一种实现，我给出下面代码：
PreOrder1(Node* root, std::function<void(const Node*&)> visit){
stack<int> s;
s.push(root);
while(!s.empty()){
Node* p = s.top();
s.pop();
visit(p);
if(p->right) s.push(p->right);
if(p->left) s.push(p->left); // 左树的优先级高于右树，后入栈
}
}
对于第二种实现，需要现维护一个指针用于指向后继。
PreOrder2(Node* root, std::function<void(const Node*&)> visit){
stack<int> s;
Node* p = root;
while(!s.empty() || p){
while(p){// 沿着左子树全访问一遍，存下路径
visit(p);
s.push(p);
p=p->left;
}
// 此时p为空指针，需要找到栈顶元素的后继
p = s.top()->right;
s.pop();
}
}
中序遍历
中序遍历主流也是用线索法，即用一个指针描述后继节点，与先序的线索法类似，只不过沿着左树走到底的时候并不访问，只是记录路径，在到底了之后才进行访问。
InOrder(Node* root, std::function<void(const Node*&)> visit){
stack<int> s;
Node* p = root;
while(!s.empty() || p){
while(p){// 沿着左子树走到底，存下路径
s.push(p);
p=p->left;
}
// 此时p为空指针,栈顶元素可以访问了，之后需要找到栈顶元素的后继
visit(s.top());
p = s.top()->right;
s.pop();
}
}
那中序遍历是否可以利用先序遍历那种优先级法实现呢，在不借助其他数据结构的情况下显然不行。且看一下下面错误的代码：
void InOrder_Wrong(Node* root, std::function<void(const Node*&)> visit){
stack<Node*> s;
s.push(root);
while(!s.empty()){
Node* p = s.top();
s.pop();
if(p->right) s.push(p->right);
visit(p); // 错误的原因在于visit的位置其实没影响，放在if前if后甚至放在后面也都是前序遍历
if(p->left) s.push(p->left);
}
}
这样实现的仍然是前序遍历，毕竟不是递归，顺序执行的时候入栈和访问数据没有依赖关系，所以无差别。
后序遍历
前面说过后序遍历本质可以用先序先右后左的转置实现，转置可以用栈先存起来后一个个取，因此可以在先序遍历的基础上写出两种遍历方法，即优先级法和线索法(统称为双栈法)：
PostOrder1(Node* root, std::function<void(const Node*&, bool)> visit){
stack<int> s;
s.push(root);
while(!s.empty()){
Node* p = s.top();
s.pop();
visit(p, true); // visit函数加一个bool的wait，结果先存到栈里，之后统一访问
if(p->left) s.push(p->left);
if(p->right) s.push(p->right); // 左树的优先级高于右树，后入栈
}
visit(nullptr, false); // 统一访问
}
PostOrder2(Node* root, std::function<void(const Node*&, bool)> visit){
stack<int> s;
Node* p = root;
while(!s.empty() || p){
while(p){// 沿着右子树全访问一遍，存下路径
visit(p, true);
s.push(p);
p=p->right;
}
// 此时p为空指针，需要找到栈顶元素的后继
p = s.top()->left;
s.pop();
}
visit(nullptr, false); // 统一访问
}
哈夫曼树
原理：带权路径最小的二叉树。要实现带权路径最小，应该让权值大的路径更短，权值小的路径更长，基于此设计贪心算法构造哈夫曼树。
最小WPL的树，其中\(WPL = \sum w_ih_i\)
h为路径高度，w为该路径(节点的权值)。
过程：
贪心，每次选权值最小的两个节点组合。
扩展：
三叉、四叉哈夫曼树。需要补充一些虚拟节点，权值为0，然后再每3/4个一组贪心构造哈夫曼树即可。
哈夫曼编码
原理：哈夫曼编码想构造一种二进制编码，一是希望编码之后码的总长是最小的，二是希望编码之间没有冲突。结合哈夫曼树，如果我们用路径表示编码，这样不同字符对应的路径就完全不一样，可以实现无冲突；而使用频率表示权值，那么使用频率高的就理应有更短的编码，因此就完全和哈夫曼树对应上了，这样可以实现总码长最小。
路径上左边0，右边1，路径上01的组合代表一个节点的编码。
图
结论
完全图的边数：无向图(\(\frac{n(n-1)}{2}\))，有向图(\(n(n-1)\))
子图：V的子集和E的子集构成的子集中能构成图的集合。光是两个子集不一定能构成图，没有点只有边就不是图。
有关连通图：
- 无向图讨论连通分量，有向图讨论强连通分量，(强)连通分量本身是一个子图
- 讨论连通分量时，针对的是顶点，极大连通子图只是确保“该子图不能再增加顶点，否则不连通”，因此原来连通的话就只有一个极大连通子图，原来不连通则有多个连通子图；对于极小连通子图，等于最小生成树。所以“极大”往往指点数不能再大了，而“极小”则是说边数不能再少了。
- 讨论强连通分量时，就有极大强连通子图(点不能再多)和极小强连通子图(边不能再少)。
度：无向图中，度和 = 2 * 边数；有向图中，入度和 = 出度和 = 边数
简单路径、简单回路：要求路径中不能经过重复点，这称之为“简单”
图的路径长度：路径上边的数目，不是点的数目。
有向图的连通分为强连通和弱连通，强连通任意点可达，弱连通则是化为无向图之后连通。
图的存储：
- 邻接矩阵：二维数组表示
- 邻接表：顶点用数组表示，边用链表(另一个点的序号，下一条边指针)表示。
- 十字链表：存有向图的，顶点用数组表示，用链表表示边，链表节点存储(边的首节点序号，尾节点序号，与首节点序号相同的下一条边的指针，与尾节点序号相同的下一条边的指针)，相比于邻接表节约了些重复边
- 邻接多重表：存无向图的，类似十字链表，边链表为(边的首节点序号，边的尾节点序号，头的下一条边，维的下一条边，边权)
广度(深度)优先生成树：对图从某个节点开始进行广度(深度)优先遍历，则遍历过程中能到达且未被访问过的点就是孩子节点，这样能够得到一棵树。
最小生成树的性质：
- 不唯一，若权值都不等则唯一
- 最小生成树的边数 = 顶点数 - 1
最小生成树
- prim算法
用数组维护set到所有节点的距离，每个距离默认是无穷大，每次新增节点时更新这些距离(更新自己以及和自己相连点到set的距离，再利用相连点里的最小距离确定下一个添加的点)。
时间复杂度分析：
\(\sum O(1) + O(|V|) = O(|V|) + O(|V|^2) = O(|V|^2)\)
- kruskal算法
用并查集实现
KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
时间复杂度分析：
边排序:\(O(|E|log|E|)\)，
遍历边并查找、合并：\(\sum O(log|V|) | O(1) = O(|E|log|V|) + O(|E|) = O(|E|log|V|)\)，
总复杂度：由于最小生成树的前提是连通图，所以\(|V| \leq |E|\)，因此时间复杂度主要取决于边排序，复杂度为\(O(|E|log|E|)\)
最短路
- 单源最短路-Dijkstra算法：
类似Prim算法，用数组维持set到所有点的距离，源点距离为0，每次新增节点，更新距离数组，但仅仅如此无法得到最短路和最短距离，因此需要一个辅助数组记录parent，也就是加入新节点前辅助数组的parent(如果距离更小则更新，否则不更新)。
最终的最短路径和最短距离可以利用辅助数组得到。
时间复杂度分析：
和Prim算法一致：\(O(|V|^2)\)
问题：如果边权为负值，考虑一种特殊情况，两个节点成环，边权为负，则显然不会有最短路，最短路可以通过无限走环减少路径权值；那如果无环会不会有问题？也会！下面这种情况，先将2加入set，此时再将1加入时，无法更新2，导致出问题：
graph LR 0((0)) --7--> 1((1)) 1((1)) --"-5"--> 2((2)) 0((0)) --5--> 2((2))- 多源最短路算法-Floyd算法
理论上可以用\(|V|\)次Dijkstra算法实现，复杂度为 \(O(|V|^3)\)
Floyd算法
Floyd算法使用DP优化，原始的Floyd算法可以描述为:
\[A[k][i][j] = min\{A[k-1][i][j], A[k-1][i][k] + A[k-1][k][j]\} \]其中\(A[k][i][j]\)定义为只能使用前k个节点作为中间节点时，节点i到节点j的最短路径长度。
很显然这一算法需要\(O(n^2)\)的空间复杂度，通过滚动数组技巧，可以将空间复杂度降低为\(O(n)\)
很显然，\(A[k][i][j]\)在计算完之前是等于\(A[k-1][i][j]\)的，因此第一维可以省略；后面两项中，可以证明\(A[k-1][i][k] = A[k][i][k]\)，也可以省略，同理\(A[k-1][k][j] = A[k][j]\)，证明过程如下：
\[A[k][i][k] = min\{A[k-1][i][k], A[k-1][i][k] + A[k-1][k][k]\} \\ = min\{A[k-1][i][k], A[k-1][i][k] + 0\} \\ = A[k-1][i][k] \]\[A[k][k][j] = min\{A[k-1][k][j], A[k-1][k][k] + A[k-1][k][j]\} \\ = min\{A[k-1][k][j], 0+A[k-1][k][j]\} \\ = A[k-1][k][j] \]因此利用该原理，dp状态转移方程优化为了
\[A[i][j] = min\{A[i][j], A[i][k] + A[k][j]\} \]从而，我们需要维护一个\(n \times n\)的数组，循环n次，更新上述状态方程即可。
时间复杂度分析：\(O(|V|^3)\)
问题：负权值时，如果存在环，一样的不能work；如果不存在环，后于Floyd算法会更新之前节点的最优值，所以仍然能够work。
有向无环图
1⃣️ 有向无环无权图
用来描述公共子式：
用来实现拓扑排序：
AOV网，边无权重，点有序号→活动发生先后顺序
2⃣️ 有向无环有权图
AOE网，边有权重，漫水浇灌(终点完成一定是所有路径均已到达)→关键路径(最长路径)
事件最早发生时间\(\leftrightarrow\)前面进来的所有活动都发生完了：\(t_v(k) = max\{t_v(j) + weight(j,k)\}\)
其中\(j\)为指向\(k\)的所有节点。
事件最迟发生时间\(\leftrightarrow\)从后往前沿着最长的路径回退：\(t_v(k) = min\{ t_v(j) - weight(i,j) \}\)
其中\(j\)为\(k\)指向的所有节点。图确定的情况下，关键路径确定，终点的结束时间时确定的。后面节点最迟发生时间选择最长的权重路径返回，才是上一个的最迟发生时间。
活动最早开始时间\(\leftrightarrow\)前面的事件发生完了\(\leftrightarrow\)前面的事件的最早开始时间。事件本身是瞬时不花时间的，因此事件的开始和结束是同时。
活动最迟开始时间\(\leftrightarrow\)后面的事件最迟发生时间-边权。边的开始时间+边的花费时间 = 事件开始时间。
活动时间余量：活动最迟开始时间与最早开始时间的差，差等于0则是关键上的活动
关键路径：关键路径是源点到汇点的最长路径。关键路径表示完成工程的最短工期，关键路径上的活动称为关键活动，关键路径可能不止一条。
强连通分量
先介绍一下tarjan算法的基础，即四种递归树的边和，之后引出tarjan算法。
DFS递归树和四种对应的边：
要理解这四种边的定义，给出伪代码往往比较容易解释：
num用于记录时间戳，mark记录是否在路径上。
tree edge： 第一次被“发现”的点
forward edge：在自己的孩子节点路径上被发现，自己也能到达的点
cross edge：在非自己孩子节点路径上被发现，自己也能到达的点
back edge：路径上的节点，有back edge则一定成环了
有了上述定义，我们先考虑一个问题，如何判断一个图是强连通分量呢？
按照强连通分量的定义，应该是最大的那个能够两两节点可达的子图，进一步的，在DFS中，我们用栈记录每次发现的点，因此我们的路径上能够保证栈底到栈顶是单向可达的，如果栈顶到除了栈顶以外的其他顶点也可达，则此时必成环，且此时必是强连通子图，但不一定是极大的。而在回溯之后回到“收束点”时，才能确认此时的栈中顶点组成的图是强连通分量，如下图的红色点：
因此，出栈时机应该在循环结束处理。
综上，DFS是利用tree edge尽可能扩大节点数目，确保“极大”，通过找到可回到时间戳更小的节点确认存在环，此时对应的边是cross edge或者back edge，近而在DFS回溯时输出路径上的强连通分量的节点。
基于上述分析，我们写出以下算法：
#include <bits/stdc++.h>
using namespace std;
class Graph{
private:
vector<vector<int>> edges;
int n;
public:
Graph(int num): n(num){edges.resize(num);};
void addEdge(int i, int j);
void SSC(int u);
void dfs(int t,int u,vector<int>& time_line, vector<int>& ans, vector<int>& in_sk, stack<int>& sk);
};
void Graph::addEdge(int i, int j){
edges[i].push_back(j);
}
void Graph::SSC(int u){
vector<int> ans(n, -1);
vector<int> time_line(n, -1);
vector<int> in_sk(n, 0);
stack<int> sk;
dfs(0, u,time_line, ans, in_sk, sk);
}
void Graph::dfs(int t, int u, vector<int>& time_line, vector<int>& ans, vector<int>& in_sk, stack<int>& sk){
// time_line 记录每个节点进入dfs的时间点
// ans 记录每个节点能回到的最短时间点
// in_sk 记录是否在栈中，在栈中说明在一条路径上
// sk 存路径上的节点
time_line[u] = t;
ans[u] = t;
sk.push(u);
in_sk[u] = 1;
for(auto& v:edges[u]){
if(-1 == time_line[v]){ // tree edge，发现节点
dfs(t+1, v, time_line, ans, in_sk, sk);
ans[u] = min(ans[u], ans[v]); // dfs探索完一条路径更新当前节点的回溯时间
}else if(in_sk[v]){ // back/cross edge -> 此时栈中一定有环，v就是环的入口
ans[u] = min(ans[u], time_line[v]);// 此时回溯时间要更新为环的入口的时间
}
// 为什么不处理forward edge？
// 因为forward edge指向的节点时间戳更大，我要找的是能够到达更小时间戳的节点
}
if(ans[u] == t){
int w = -1;
cout << "-------group---------"<<endl;
while(w!=u){
w = sk.top();
in_sk[w] = 0;
sk.pop();
cout << w << " ";
}
cout << endl << "-------group---------"<<endl;
}
}
int main()
{
auto g = Graph(7);
g.addEdge(0,1);
g.addEdge(1,2);
g.addEdge(2,0);
g.addEdge(1,3);
g.addEdge(1,4);
g.addEdge(1,6);
g.addEdge(3,5);
g.addEdge(4,5);
g.SSC(0);
return 0;
}
时间复杂度分析：
在dfs访问的基础上，增加栈存储路径信息，时间复杂度和dfs的时间复杂度相同\(O(|E|+|V|)\)
求强连通分量应试：
前面强连通分量的算法告诉我们强连通分量一定是环，那么入度或者出度为0的节点一定不在环上，应该先干掉，这些干掉的点构成一个单独的强连通分量；除掉这些点的过程中删除了某些到达这些点的出边，从而导致图中可能出现一些新的不在环上的点，继续除掉并输出之。此时，图中一定有环，但是可能是多个环，因此需要把连接多个最大的环的边(桥)给删掉，就得到了所有的强连通分量。
简而言之，只需要简单的三步：
- 删掉入度或者出度为0的点和对应的边，输出之，这一个顶点构成一个强连通分量
- 继续寻找满足条件1的点，删除之。
- 剩余点里面找到桥，删除之，得到所有的强连通分量。
桥和割点
桥和割点一般是无向图中的概念，是连接两个连通子图的边，从上述分析中可以看出，桥其实就是对应有向图中的cross edge。因此，如果要求桥和割点，也可以用tarjan算法找到DFS树的cross edge即可。
最大流
强连通分量讨论有向无权图的连通情况，而最大流讨论有向有权图的流量情况的源节点到目标节点的最大流量。最大流算法基于求阻塞流的算法发展：
Naive(阻塞流)：
阻塞流算法引入residual graph概念，该图存储原图中每条边还剩多少流量可用，因此初始化时就是原图的边权。我们在resudual graph上寻找任意一条简单路径，将该路径流量用到最大，之后再不断寻找新的能够增加流量的简单路径，直到无法新增流量，此时网络陷入阻塞，称之为阻塞流。阻塞流本质上是一种贪心算法，只不过没法保证是最大流。
因此，阻塞流算法可以形式化描述为：
- 构建residual graph(空闲量)，所有操作在residual graph上进行
- 寻找增广路(任意简单路径)，能找到则根据路径上的最小容量更新residual graph
- 反复找并更新，找不到时，结束。此时\(Flow = Capacity - Residual\)
求的的并不一定是最大流，因此叫阻塞流。最大流是一种特殊的阻塞流。
Ford-Fulkerson算法：
阻塞流算法的问题在于无法将已经尝试分配的流部分进行调整Ford-Fulkerson假定阻塞流的贪心策略一定能找到最大流，再次基础上允许在分配流之后改变residual graph图的结构，添加反向边，此时图的结构在每次寻找增广路的过程中不断改变，最终能确保找到的是最大流。其形式化描述大致如下：
- 构建residual graph(空闲量)，所有操作在residual graph上进行
- 寻找增广路(任意简单路径)，能找到则根据路径上的最小容量更新residual graph，并在residual graph上添加一条反向的权值等于最小容量的边(用于反悔的反向边)
- 反复找并更新，找不到时，结束。删掉反向边。此时\(Flow = Capacity - Residual\)
算法复杂度\(O(MaxFlow|E|)\)
Edmonds-Karp算法：
与Ford-Fulkerson不一样，Edmonds-Karp算法则是探索改变贪心策略同时改变网络结构来寻找最大流，贪心策略的改变直接影响了算法复杂度，而网络结构的改变则是和Ford-Fulkerson保持一致，保证了最大流一定可以找到。其贪心策略调整为将网络视为有向无权图时，找到最短的增广路更新residual graph。这一块的改进仅仅是把Edmonds-Karp算法在寻找增广路时的DFS改成了BFS，减少了在找增广路上的开销，因此提升了时间复杂度。
- 构建residual graph(空闲量)，所有操作在residual graph上进行
- 寻找最短增广路(将网络视作有向无权图)，能找到则根据路径上的最小容量更新residual graph，并在residual graph上添加一条反向的权值等于最小容量的边(用于反悔的反向边)
- 反复找并更新，找不到时，结束。删掉反向边。此时\(Flow = Capacity - Residual\)
算法复杂度\(O(|E|^2|V|)\)
最小割
S-T Cut：所用从集合S到集合T的边的权重之和。
Minimum S-T Cut：Min{S-T Cut}
最大流的流量 = 最小割的容量
算法：
- 利用最大流算法找到最大流，得到residual graph
- 在residual graph中，s能够到达的节点放到集合S中，不能到达的节点放到集合T中，得到最小割。
二分图
定义：
节点被划分为两个集合，集合之间有边，集合内无边。
二分图判定：
染色算法：bfs交替染色，染色过程中如果节点已经被访问过，则检查颜色是否一样，如果一样，则停止，不是二分图，否则继续访问和染色。
原理：如果图是二分图，则一定可以染色，沿着两个集合之间的边交替染色即可；如果一个图可以染色，那么必然可以将同种颜色的节点放在一个集合中，两个集合之间有边，此时集合内部必无边，因为有边的话必然在染色过程中发现同色导致染色失败。
所以，能否染色和图是否二分是等价条件。
二分图匹配：
一个匹配是指匹配的边没有相同的节点。
无权图：
需要求解匹配的边数量最大的匹配。
方法1：转化为最大流问题。
添加s节点和t节点分别与两个集合相连，集合之间的边转化为有向边，求此图的最大流对应的就是最大匹配。(因为限制了每个节点进出流量都是1，所以最大流时一定是一一连接的，因此此时是最优匹配)
方法2: 匈牙利算法
匈牙利算法
两个概念：
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，这条路以为匹配点为起始点，另一个未匹配点为终点。这样的一条路叫增广路。如果这样的路存在，那么将这条路上所有的匹配边变成非匹配边，非匹配边变成匹配边，会出多一条匹配边出来(从未匹配到未匹配，这条路径上未匹配边的数量等于匹配边数量+1)，这样就实现了“增广”。多出来的这条边，会导致多一组匹配，因此匈牙利算法是通过不断寻找增广路来增加匹配，从而实现最大匹配。
算法原理：
贪心算法，贪心规则是找增广路。
有权图-Kuhn-Munkres(KM)算法：
任务描述，给定二分图\(G=(X \cup Y, X \times Y)\)，其中\(w(xy)\)表示节点\(x\)和节点\(y\)的边的权值。我们需要求一个对\(Y\)的permutation \(\pi\)，使得\(\sum_i w(x_iy_{\pi_i})\)最大。此时permutation下\(X\)和\(Y\)的对应关系为最优匹配。这里是最大匹配，有时候也需要最小匹配，对应这时候权重矩阵称之为代价矩阵，最小化代价。因此，有权图的二分图匹配问题本质上是一个组合优化问题。
思路和方法
在处理带权二分图匹配的问题上，我们往往希望构造一个具有相同解的子图，并在该子图上进行求解。KM算法引入了“标号算法”来构建这样的子图：
先定义合理标号的概念，即满足任意两节点之间的标号和大于等于两节点之间的权重，就是合理标号：\(l(x)+l(y) \geq \omega(x y)\)，将标号后的图\(G_l\)所有\(l(x)+l(y)=\omega(xy)\)的节点和边留下，就得到了一个“相等子图”，也就是上面说的具有相同解的子图。
那为什么要用标号的方式构造呢？我的理解是引入更多的变量实现“松弛化”，类似拉格朗日乘子法。这样松弛化之后可以将原问题转化为一个以往已经解决了的问题，并且保证两者有相同的解。松弛化之后，我们是一定可以构造出“相等子图”的，此时我们再用无权图的二分图匹配算法(上面讲的)，直接就得到了最优匹配。
那么现在摆在我们面前的有2个问题，一是如何证明我们构造的相等子图得到的完全匹配是权重最大的匹配；二是我们要如何构造？
- 证明构造的相等子图得到的完全匹配是权重最大的匹配
第一个问题，参考“参考文献”：
这意味着我们在构造相等子图时(调整标号)，需要根据下一步是否能够找到完全匹配，而进行动态调整，因此算法设计就是设计如何调整(贪心)标号。
- 如何构造
现在我们来回答第二个问题。
首先，assignment矩阵的每行减去该行最大值并不影响该问题的解，这样处理后相等子图的边一定来自于assignment矩阵中的“0”位置。同理，每列的值减去最大值也不影响最终解的构造，反而会让更多的“0”出现，因此先做这两步方便构造相等子图。
下一步，构造相等子图，也就是选边。选边的可视化过程等价于在某个“0”位置划掉他的那一行和那一列，表示这俩节点已经配对了，划掉之后再在剩余的元素里面找0划线，如果所有元素都能划掉，则说明这是一个有效匹配，此时必定是最大匹配，上面证明过了。选0的时候要尽可能保证划掉同行同列的0的数量尽可能少，这点也比较好理解，划掉的0越多表示这个匹配对其他人的影响就越大，我们尽量选择对别人影响小的0。如果此时无法划出一个有效匹配，此时就需要继续“加0”才能构造出匹配，因此将剩余元素减去他们之中的最大值，就一定能构造出0，然后再用构造出的0划线，重复直到得到一个有效匹配，此时是最大匹配。
步骤：
- 每行减去最大值，每列减去最大值。构造“0”位置以便构造相等子图。
- 选边。贪心的选择对别人影响最小的“0”位置构造边。选边的过程可以用匈牙利算法处理。
- 处理。如果此时是有效匹配，结束。如果此时无法构造出有效匹配，贪心地构造出0，继续选边直到构造出有效匹配。
总结：
KM算法本质是将原始的组合优化问题松弛化为相等子图构建问题，用贪心算法找到满足条件的相等子图，匈牙利算法在KM算法中仅仅是用来构造相等子图用的，匈牙利算法是KM算法的一部分。
查找
- 折半查找
折半查找的判定树是平衡二叉树，因为总是从中间元素开始找，所以两边的元素数量差不多，任意根节点左右子树数量差不多。而且，由于折半的时候取中间节点时有floor或者ceil操作，所以节点分配是有倾向性的(所以可能不是完全二叉树，但是除了最后一层肯定都是满的)。
n个节点的折半查找唯一确定判定树，而n个节点的二叉查找树不是唯一确定的。
折半查找的判定树树高为\(\lceil log_2(n+1)\rceil\)，简要证明一下：
对于一个高为\(h\)，节点数为\(n\)的折半查找判定树，前\(h-1\)层必满，所以n的范围应该是\(2^{h-1} - 1 \lt n \leq 2^h -1\)，进一步写成h的范围：\(log_2(n+1) \leq h \lt log_2(n+1)+1\)
进一步有
\(h-1<\log _2(n+1) \leq h\)，对不等式三边同时向上取整，则
\(h-1<\left\lceil\log _2(n+1)\right\rceil \leq h\)
因为h只能取整数，所以\(h=\left\lceil\log _2(n+1)\right\rceil\) ，同理也可证\(h=\left\lfloor\log _2(n+1)\right\rfloor+1\)，只需要证明时换成向下取整即可。
这一结论同样适用于完全二叉树。
- 分块查找
块内无序，块间有序。块间可用二分查找，块内顺序。
平均时间复杂度为\(O(n_{block})+O(n_{item})\)，即块内查找的平均时间复杂度加上块间查找的平均时间复杂度，对于顺序查找是\(O(\frac{b+1}{2}) + O(\frac{s+1}{2})\)，对于折半查找则是\(O(log_2 b)+O(\frac{s+1}{2})\)
- b树
所有节点平衡因子都等于0的m路平衡查找树。为了保证空间利用率，b树约定了每个非终端、非根节点都要至少有\(\lceil \frac{m}{2} \rceil\) 个分支。
查找：先在节点内的顺序表里查找，没找到说明在下一层，根据目标节点和查找位置关系到下一层去查。
插入：m路的b树，不能超出m路，超出则要和父亲节点一起重新分配，送一个人上去当父亲，就可以防止“溢出了”
删除：
删除关键字需要两步走。
- 如果删除节点后导致节点失去父亲，那么把要删除的关键字的最大左孩子关键字或者最小右孩子关键字copy到被删除关键字位置，然后准备删除孩子节点，走到第二步
- 此时不仅对应第一步的失去父亲的情况，还对应本身就要删除这个孩子的情况，两种情况进行统一处理。如果删除这个关键字不影响b树定义，那就删掉；如果影响b树定义(至少要有\(\lceil \frac{m}{2} \rceil\) 个分支，叶节点全在最后一层)，此时只能找兄弟姐妹借了，如果能借到，皆大欢喜，借不到(影响兄弟姐妹的b树定义)，就让父亲下来，用父亲当兄弟补。
注意：
- n个关键字的b树有n+1个失败节点(可以理解为区间)
- 算总节点个数的时候不加上终端节点(失败节点)
- b树的关键字数目=所有非终端节点关键字数目=终端节点个数 →n个非叶节点的m阶b树，最少关键字数目是 \(1 + (n-1)(\lceil \frac{m}{2} \rceil -1)\)
- b树不支持顺序查找，只支持随机查找，随机查找体现在节点内关键字数组支持下标访问；不支持顺序查找则意味着拿不到下一个元素，因为下一个元素可能需要经过父亲节点到下一个兄弟节点，b树并不能直接支持(虽然理论上可以通过类似中序遍历实现)。
哈希表
冲突：在存数据的时候，地址已经被占用了，要采取的手段。
堆积：冲突之后往后堆数据，堆得多了可能和其他堆碰撞。链式处理不会堆积，因为不会再碰撞。
冲突处理：
- 链式处理：链表往后加数据
- 开放处理：（探测的时候挨个试，直到试到能放）
线性探测：试试下一个
平方探测（二次探测）：\(H_i=(H(key) + d_i) %m\)，其中\(d_i=0^2,1^2,-1^2 \cdots,k^2,-k^2\)
双散列：再用一个散列以第一个散列算出来的地址作为key查下一个地址
随机探测：随机地址
填装因子：填充率。填装因子越大，发生冲突情况越多，平均查找长度越大。
影响平均查找长度的因素：填装因子、冲突处理方法、散列函数。
注意：
- 后面没比较
- 线性探测查找成功时，探测位置相邻的也不一定是同义词，可能中间隔了个别的
堆
建堆：从最后一个有儿子的节点开始从后往前down，时间复杂度\(O(n)\)
查找：时间复杂度\(O(logn)\)
插入：往后面插入，然后up，因为此时其他分支路径都满足堆的定义，只有加入节点的分支可能不满足堆的定义，因此只需要调整这一路径。时间复杂度\(O(logn)\)
删除：堆底元素和待删除元素交换，删除之，down。最后一个元素是潜在的最大节点(最小堆)，放到根节点必然破坏至少一个子节点的定义，复杂情况就是两个子节点都比此时根节点小，而down时会选择两个子节点中更小的节点放上去，此时必然能够满足一颗子树的定义，down完都满足定义。时间复杂度\(O(logn)\)
高阶数据结构
AVL树
定义：
- 是一颗二叉排序树
- 左右子树高度差小于等于1
- 任意子树为AVL树
失衡：
在插入删除节点时，会破坏整颗AVL树的平衡性，因此需要在失衡时进行平衡调整。在失衡时，我们需要找到我们插入/删除节点后，对哪个节点的平衡性影响最大，即修改以该节点为根的子树结构，可以保证全局仍然平衡。以插入为例，如果我们找到了影响失衡的节点，我们将这颗子树调节平衡，并且高度和插入前一致，我们就能确保整棵树是平衡的。我这里姑且将这种节点命名为失衡节点。而调整子树结构，本质上也只需要调整三个节点的结构，下面详细描述。
因此，调整策略就分为简单的两步：
- 找到失衡节点，这对我们来说是相当容易的，应试的话一眼能看出来，代码实现的话在路径上找到第一个平衡因子绝对值大于1的点。
- 调整以失衡节点为根节点的子树结构，使得调整后和插入/删除节点前的高度一致，并且平衡。
我们现从插入节点开始考虑：
插入节点时，失衡节点一定在从根节点到插入节点的路径上，且离插入节点最近。这是很显然的，我们需要调整离插入节点最近的一颗子树就可以了。按照书上的分类，是有四种情况需要调整，我们这里以书上的情况为例，而用上述的调整策略进行演示，免去记忆。
第一种情况：
我们找到失衡节点n，考虑如何调整这颗子树。这时候左子树高，右子树低，因此需要左子树变矮一些，右子树变高一些，此时刚好能平衡。之所以将n变为i的右节点，因为是一颗二叉排序树，调整之后不能破坏二叉排序树定义，因此只能以旋转的形式调整。之后蓝色的子树不能没地方接，但出于二叉排序树的定义，只能接在n节点左边(因为他原来就是n节点的左子树)。
第二种情况：
与第一种类似，不赘述。
第三种情况：
n节点失衡，因此把ik-u那条路往上拽，右边下沉1，才能使得n节点的平衡因子为0，又由于要满足二叉排序树的定义，所以拽了之后只能让k当根，其他任意一个节点当根节点都会破坏定义。
第四种情况：
与第三种差不多不赘述。
删除节点时，同理找到失衡节点，进行上述调整。
调整策略总结：找到插入路径上离不平衡子树的根节点最近的三个节点，这三个节点重排，其他按照二叉排序树定义接上。
名称辨识：考试的话还是要知道LL旋转RR旋转之类的是啥意思的，LL旋转对应的是失衡节点的左孩子的左子树插入了节点，其他同理。
红黑树
其他
Strassen’s algorithm for matrix multiplication：用分治思想做矩阵乘法
Rod Cutting：动态规划算法
LCS问题：动态规划算法
编辑距离：动态规划算法
viterbi算法：动态规划算法
霍夫曼编码：贪心算法
P/NP/NPC
P问题：能够在多项式时间内解决的问题
NP问题：能够在多项式时间内验证结果是否正确的问题
NP-Hard问题：所有的NP问题都能reduce到的问题Q是NP-Hard问题，因此难度上NP ≤ NP-Hard，目前已经发现了在多项式时间内无法验证的算法，所以NP-Hard问题一定是“天外天”，如下图所示
NPC问题：可以理解为最难的NP问题，也就是NP问题和NP-Hard问题的交界
P问题显然能够在多项式时间内验证，所以P\(\subseteq\)NP
NPC问题是最难的NP问题，所以NPC\(\subseteq\)NP
如果科学家能够在多项式时间内解决NPC问题，那么可以得到P=NP
Decision problems: 决策问题，答案只能是yes/no，NPC问题只使用于决策问题，因此优化问题要先转化为决策问题要证明其是否是NPC问题。
Optimization problems：优化问题，一般是找到最优解，一个问题的Optimization problems要至少难于其Decision problems
Optimization problems → Decision problems ： 决策问题的输入为某个instance pair和阈值，优化问题的解转化为Decision problem进行验证。例如最短路问题是优化问题，其对应的决策问题为给定某两个图中的节点和路径长度阈值k，判断是否存在长度为k的路径。
Reductions
证明问题A是NPC问题的步骤：
- 证明A是NP问题。即在多项式时间内可以验证。
- 将一直的NPC问题B reduce到问题A，map B问题的输入到A问题的输入，保证结果一致。能够reduce则说明A问题是NPC问题。
常见的NPC问题：
布尔可满足性问题:
给定一个布尔方程， 判断是否存在一组布尔变量的真值指派使整个方程为真的问
题
0-1整数规划
给定一个整数 矩阵 C和一个整数向量d，判断是否存在一个0-1向量x，使得Cx=d
分团问题
给定无向图G和正整数k，判定G中是否包含有大小为k的集团。
Set packing
给定一个有限集合S和一些S的子集，求问是否可以其中的k个子集，它们两两不相
交。
最小顶点覆盖问题
给定图 G=(V,E)和数k，判定是否存在包含大小至多为k的顶点覆盖。
集合覆盖问题
给定全集U，以及一个包含n个集合且这n个集合的并集为全集的集合S。集合覆盖
问题要找到S的一个最小的子集，使得他们的并集等于全集。
反馈点集问题
给定有向图H和整数k，判定是否存在集合R⊆V，其中有向图H中的每个有向环都包
含R中的一个点。
反馈弧集问题
给定有向图H和整数k，判定是否存在集合S⊆E，其中有向图H中的每个有向环都包
含E中的一个边。
有向哈密尔顿环
给定有向图H，判定其是否经过图中每个顶点且仅一次的回路。
无向哈密尔顿环
给定无向图G=(V,E)，判定其是否经过图中每个顶点且仅一次的回路。
每句话至多3个变量的布尔可满足性问题
给定三元合取范式f，对布尔表达式f中的布尔变量赋值，是否可使f的真知为真。
图着色问题
给定无向图G=(V,E),用k中颜色为V中的每一个定点分配一种颜色，使得不会有两个
相邻定点具有同一种颜色。
分团覆盖问题
给定无向图G’和整数k，判定N’是k的联合，并且是较少团。
精确覆盖问题
给定了一个全集S以及它的m个子集S1、S2、..Sm以后，要求出一组子集，使这组
子集的并等于原来的全集S，且各子集两两不交。
Hitting set 问题
给定一个由 n 个元组组成的有限集合 S ={S1 , ..., Sn}, 元组中的元素取自符号集 U =
{u1 , ..., um}, 判定集合U 是否存在一个子集 U′, U′≤k ,使得对于 S 中的任何一个元组
Si, 满足 Si ∩U′≠φ
Steiner tree 问题
给定无向图 G=(V E)及子集 R ⊆V 图中每条边权值wr∈R+。找出连接R中所有顶点且
边权值之和最小的树。
三维匹配问题
存在一个集合M⊆W×X×Y，并且W，X，Y为不想交的集合，|W|=|X|=|Y|=q。判定是
否存在一个集合M'⊆M，使得|M'|=q，并且M'在W，X，Y三维上不存在交集。
背包问题
给定的整数 Cj,j=1,2,...n和b，判定是否存在{1,2,...,n}的子集B，使得(C1+C2+...+Cj)=b
Job sequence问题
给定m个性能相同的处理器，n个作业J1,J2,...Jn，每个作业的运行时间t1,t2,...tn以
及时间T，是否可以调度这m个处理器，使得他们最多在时间T里完成这n个作业。
划分问题
给定一个具有n个整数的集合S，是否能把S划分成两个子集S1和S2，使得S1中的整
数之和等于S2中的整数之和
最大割问题
无向图最大割。
标签：元素,匹配,复杂度,路径,算法,数据结构,节点,考研 From： https://www.cnblogs.com/aoru45/p/17794064.html