本篇内容整理自胡凡的《算法笔记》，主要目的是对C++程序设计做一个快速而又系统的回顾，因此只涉及到基础内容及应用，以及一些编程技巧，也可以当作「算法入门手册」使用。如需「进阶版」请移步「算法思想」系列。

0x00 C/C++ 程序设计基础

1
#include<bits/stdc++.h>

黑盒测试

大部分在线评测系统都采用多点测试的方式，即将所有输入数据放在一个文件里，系统会让程序去读取这个文件，然后执行程序并输出结果。因此必须保证程序能够反复执行代码的核心部分，这就要用到循环。

（1）while(T–) 型

给定了测试数据的组数，因此只需要用一个变量T来存储，并在程序开始时读入即可。

1
2
3
4
scanf("%d", &T);
while(T--) {
    ...
}

（2）while…EOF 型

没有给定测试数据的组数，因此需要反复读取，直至文件末尾。

  • scanf 函数的返回值为其成功读入的参数的个数，当读到文件末尾时，scanf 函数会返回 -1，即 EOF。
1
2
3
while(scanf("%d %d", &a, &b) != EOF) {
    ...
}

0x01 算法入门专题

  • 字符串专题
  • 数学专题

1. 表达式计算问题

对于一般形式的表达式，通常称为中缀表达式（infix）。但这种表达式在计算时面临的主要问题有：

  1. 运算符有优先级

  2. 括号会改变计算的次序

为了方便表达式的（计算机）计算，波兰数学家发明了一种将运算符写在操作数之后的表达式表示方式，称为后缀表达（postfix），或逆波兰表示。

中缀表达式 后缀表达式（RPN）
a + b a b +
a + b * c a b c * +
a + b * c + ( d * e + f ) / g a b c * + d e * f + g * +

1）中缀表达式计算

【中缀到后缀】

从左至右遍历中缀表达式中每个数字和符号：

  • 若是数字直接输出，即成为后缀表达式的一部分；
  • 若是符号：
    • 若是)，则将栈中元素弹出并输出，直到遇到“(”， “(”弹出但不输出；
    • 若是(，+，* 等符号，则从栈中弹出并输出优先级高于当前的符号，直到遇到一个优先级低的符号；然后将当前符号压入栈中。（优先级+，-最低，*，/次之，“(”最高）
  • 遍历结束，将栈中所有元素依次弹出，直到栈为空。

【后缀表达式计算】

从左至右遍历后缀表达式中每个数字和符号：

  • 若是数字直接进栈；

  • 若是运算符（+，-，*，/），则从栈中弹出两个元素进行计算（注意：后弹出的是左运算数）。

  • 遍历结束，将计算结果从栈中弹出（栈中应只有一个元素，否则表达式有错）。

【伪代码】

实际上，对于上述问题我们没有必要像编译程序那样先将中缀表达式转换为后缀表达式，然后再进行计算，而是可以同时进行。

为此，可设两个栈，一个为数据栈，另一个为运算符栈，主要思路为：

  • 当一个运算符出栈时，即与数据栈中的数据进行相应计算，计算结果仍存至数据栈中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<cstdio>
#include<string>
#include<stack>

using namespace std;

inline bool isDigit(int c) { return ('0' <= c && c <= '9'); }
inline bool isOper(int c) { return (c == '+' || c == '-' || c == '*' || c == '/'); }
inline bool isLbrkt(int c) { return c == '('; }
inline bool isRbrkt(int c) { return c == ')'; }

inline int getPrior(int c) {
	int prior;
	switch(c) {
		case '+':
		case '-':
			prior = 1; break;
		case '*':
		case '/':
			prior = 2; break;
		case '(':
			prior = 3; break;
		default:
			prior = 0; break;
	}
	return prior;
}

stack<int> num, oper;

void popAndCalc();

int main() {
	string expr = "24/(1+2+36/6/2-2)*(12/2/2)";	// =18
	for(int i = 0; i < expr.length(); i++) {
		if(isDigit(expr[i])) {
			int d = 0;
			while(isDigit(expr[i])) {
				d *= 10;
				d += expr[i] - '0';
				i++;
			}
			num.push(d);
			i--;
		} else if (isOper(expr[i])) { // 运算符
			while(!oper.empty() && !isLbrkt(oper.top())) {	// 非空且非左括号 
				if(getPrior(oper.top()) < getPrior(expr[i])) {
					break;
				}
				// 若栈顶元素优先级大于当前元素，则弹栈，并计算 
				popAndCalc();
			}
			oper.push(expr[i]);
		} else if(isLbrkt(expr[i])) {
			oper.push(expr[i]);
		} else if(isRbrkt(expr[i])) {
			while(!isLbrkt(oper.top())) {	// 非左括号，则弹栈并计算 
				popAndCalc();
			}
			oper.pop();	// 弹出左括号 
		} 
	}
	while(!oper.empty()) {	// 符号栈非空，则弹栈并计算 
		popAndCalc();
	}
	printf("%d\n", num.top()); 
}

void popAndCalc() {
	// 不检验操作是否正确，只是弹栈并计算 
	int op = oper.top(); oper.pop();
	int d2 = num.top();  num.pop(); 
	int d1 = num.top();  num.pop();
	int res;
	switch(op) {
		case '+': res = d1 + d2; break;
		case '-': res = d1 - d2; break;
		case '*': res = d1 * d2; break;
		case '/': res = d1 / d2; break;
		default: break;
	}
	num.push(res);
}

2）后缀表达式转中缀表达式

后缀表达式的特点是：一定以两个操作数开始，且以操作符结尾，形如“a b + c d e + * *”就是一个后缀表达式。

基于这个特性，我们可以从左到右遍历，以此构建表达式树。

表达式树的特点就是：树的树叶是操作数（常数或变量），而其他节点为操作符。

由于一般的操作符都是二元的，所以表达式树一般的都是二叉树。

表达式树的建立过程，与哈密顿树十分类似，逐个读取后缀表达式的每个符号：

  • 如果符号是操作数，那么我们就建立一个单节点树并将一个指向它的指针压入栈中；
  • 如果符号是操作符，则从栈中弹出两棵树T2和T1，并形成一颗以操作符为根的树，其中T1为左儿子，T2为右儿子；
  • 然后将新的树压入栈中，继续上述过程。

其具体过程可以参见这篇博客。

【伪代码】

  • 注：目前尚未优化括号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<stack>
#include<vector>
#include<cstdio>
#include<string>

using namespace std;

inline bool isSpace(int c) { return c == ' '; }
inline bool isDigit(int c) { return ('0' <= c && c <= '9'); }
inline bool isOper(int c) { return (c == '+' || c == '-' || c == '*' || c == '/'); }

struct Node {
	int data;
	char op;
	bool isLeaf;	// 1: data  0: op
	Node *lchild, *rchild;
	
	Node() {}
	Node(int _data) {
		data = _data;
		isLeaf = true;
		lchild = rchild = NULL;
	}
	Node(char _op, Node *_lchild, Node *_rchild) {
		op = _op;
		isLeaf = false;
		lchild = _lchild;
		rchild = _rchild;
	}
};

void inOrder(Node *root) {
	if(root == NULL) return ;
	
	if(!root->isLeaf) printf("(");
	
	inOrder(root->lchild);
	if(root->isLeaf) {
		printf("%d", root->data);
	} else {
		printf("%c", root->op);
	}
	inOrder(root->rchild);
	
	if(!root->isLeaf) printf(")");
}

void postOrder(Node *root) {
	if(root == NULL) return ;
	
	postOrder(root->lchild);
	postOrder(root->rchild);
	if(root->isLeaf) {
		printf("%d", root->data);
	} else {
		printf("%c", root->op);
	}
}

int main() {
	// a b + c d e + * *	->		a + b x (c x (d + e)) 
	// 1 2 + 3 4 5 + * *	->		(1+2)x3x(4+5))=81
	string expr = "10 2 + 3 4 5 + * *";
	// 1. 处理后缀表达式，构建树结点 
	stack<Node*> s;
	for(int i = 0; i < expr.length(); i++) {
		if(isSpace(expr[i])) continue;
		
		if(isDigit(expr[i])) {
			int d = 0;
			while(isDigit(expr[i])) {
				d *= 10;
				d += expr[i] - '0';
				i++;
			}
			s.push(new Node(d));
			i--;
		} else {	// 运算符 
			Node *t2 = s.top(); s.pop();
			Node *t1 = s.top(); s.pop();
			Node *op = new Node(expr[i], t1, t2);
			s.push(op);
		}
	}
	
	// 2. 建树，并输出中缀表达式 
	Node *root = s.top();
	inOrder(root);		printf("\n");
	//postOrder(root);	printf("\n");	
	
	// 3. 优化中缀表达式的括号
	// 比较复杂，暂略 
	
	return 0;
}

关于括号优化，实际上，只有当当前结点为加法运算符且父结点为乘法运算符时，才需要加括号。

因此可得如下前序遍历代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inOrder(Node *root, bool lastIsMult) {
	if(root == NULL) return ;
	if(root->isLeaf) {
		printf("%d", root->data);
		return ;
	}
	// 分支节点 
	bool isMult = isMultOper(root->op);
	if(lastIsMult && !isMult) printf("(");	// 上一层是乘法运算符，而这一层是加法运算符 
		
	inOrder(root->lchild, isMult);
	printf("%c", root->op);
	inOrder(root->rchild, isMult);
	
	if(lastIsMult && !isMult) printf(")");
}

2. 字符串匹配问题

给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。

1
2
string s = "BBC ABCDAB ABCDABCDABDE";
string t = "ABCDABD";

【暴力解法】

在字符串匹配中，最自然的做法就是，用两个指针i 和j 分别指向待匹配串s 和匹配串t ，每次遇到一个不匹配的字符时，j 都要重头开始遍历，表现在代码上如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> pattern(const string &s, const string &t) {
    vector<int> res;
    int len1 = s.length(), len2 = t.length();
    int i = 0, j = 0;
    while(i < len1 && j < len2) {
        if(s[i] == t[j]) {
            i++, j++;
        } else {
            i = i - j + 1;	// i回到开始匹配的那一位的下一位
            j = 0;			// j回到0，重新开始匹配
        }
        if(j == len2) {		// 匹配成功
        	res.push_back(i - j);
            j = 0;			// j回到0，往下接着匹配 
            // 根据题目要求决定i是否需要回溯
            i = i - j + 1;	// i回到开始匹配的那一位的下一位，这样能保证ABABA里能找到两个ABA 
        }
    }
    return res;
}

【KMP算法】

在继续下面的内容之前，有必要在这里介绍下两个概念：真前缀 和 真后缀。

  • 字符串：china
  • 真前缀：c, ch, chi, chin
  • 真后缀：hina, ina, na, a

前面的暴力解法忽略了一个基本事实：

  • 当i与j指向的串不匹配时，其实我们已经知道了指针 i 前面的长度为 j 的串，一定是t的某个真前缀。

  • 我们设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，而是继续把它向后移，这样就提高了效率。

    如果这个真前缀中的某个真后缀，与t的某个真前缀相匹配，我们就可以直接从这个位置开始匹配，而不用每次都从头开始了。

    （这里说的有点绕，但核心思想就是这样，如果不太懂可以参考上面的链接。）

具体做法就是设置一个跳转数组 next ：

  • next数组的求解基于串 t 的“真前缀”和“真后缀”，即 next[j] 等于 t[0]…t[j - 1] 最长的相同真前后缀的长度 。

    image-20210321102459219

因此，剩余的工作就是求解 next 数组，并利用这个数组进行匹配了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void calcNext(const string &t, vector<int> &next) {
	int len = t.length();
	next[0] = -1;
	int k = -1;
	int j = 0;
	while(j < len - 1) {
		if(k == -1 || t[j] == t[k]) {
			k++, j++;
			next[j] = k;	// 表示串t的前j-1个字符有k个匹配 
		} else {
			k = next[k];
		} 
	}
}

vector<int> KMP(const string &s, const string &t) {
	vector<int> res;
	// 计算next数组 
	int len1 = s.length(), len2 = t.length();
    vector<int> next(len2);
	calcNext(t, next);
	// 模式匹配
	int i = 0, j = 0; 
    while(i < len1 && j < len2) {
    	if(j == -1 || s[i] == t[j]) {
    		i++, j++;
		} else {
			j = next[j];	// 当前字符匹配失败，直接从next[j]开始比较，i的位置不变 
		}
		if(j == len2) {	// 匹配成功
        	res.push_back(i - j);
            // 根据题目要求决定i是否需要回溯, 注意要
            i = i - j + 1;	// i回到开始匹配的那一位的下一位，这样能保证ABABA里能找到两个ABA 
            j = 0;		// j回到0，往下接着匹配 
        }
	}
	return res;
}

【总结】

通过观察上面的代码会发现，暴力解法与KMP算法的不同之处仅在于：

  • 当字符匹配失败时，暴力解法的 i 需要回溯到开始匹配的那一位的下一位，j回溯到0 ；而KMP算法的 i 是不需要回溯的，j 回溯到 next[j] 的位置。

需要注意的是，当匹配完整个串时，根据题目要求决定直接返回还是继续寻找：

  • 如果选择继续寻找，则 i 和 j 都需要回溯。考虑从 “ABABA” 中匹配 “ABA” ，如果不回溯i，将会导致只能匹配到一个 “ABA”。

3. 快速线性筛法求素数

素数即质数，线性筛法求素数，其基本思想为：

  • 用一个数组 $a$ 来标记自然数，$a[i]$ 为1表示自然数 $i$ 为合数，为0表示为素数。
  • 初始时，我们认为所有自然数都是素数，然后从2开始遍历，每轮筛掉一批合数，直到n为止。
  • 至此，我们就得到了从2-n的所有素数。

那么如何筛除合数呢？最朴素的做法是：

  • 当前数 i 的所有倍数均为合数，即 2i, 3i, 4i, …, ki，直到 ki > n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int MAXN = 1000007;
bool num[MAXN] = {0};		// 0: 素数，1: 合数 
vector<int> prime;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 2; i <= n; i++) {
    	if(!num[i]) {	// 素数 
    		prime.push_back(i);
		} 
		for(int j = i+i; j <= n; j+=i) {
			num[j] = 1;	// 合数 
		}
	}
    return 0;
}

这种做法是把当前数的所有倍数都标记为合数，显然这一定会有很多冗余，那如何改进呢？

  • 我们不再遍历所有倍数，而是标记当前数 $i$ 与 （目前为止找到的）所有质数 $prime[0]$ ~ $prime[j]$ 的乘积。

  • 这种求素数的算法很容易被理解，但是也存在缺陷：

    • 对于一个数30，可分解为 $30=215=310=5*6$，显然，当循环2,3,5,6,10,15时都会筛除一次30这个数，而当n很大时，就会出现许多的冗余操作。

为了提高效率，快速线性筛法的算法应运而生，其核心思想在于：

  • 当 $i \ % \ prime[j] == 0$ 时，就break掉，继续遍历下一个自然数。

这保证了每个数只会被其最小的质因子筛除。

举个例子，对于一个数9，9 * 2 = 18 将18标记为合数，循环继续； 9 * 3 = 27 将27标记为合数，此时发现 9 % 3 = 0，循环退出。

如果将循环继续下去会出现筛除9 * 5 = 45的情况，而45 = 15 * 3，在15时会被再筛去一次。

【伪代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int MAXN = 1000007;
bool num[MAXN] = {0};		// 0: 素数，1: 合数 
vector<int> prime;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 2; i <= n; i++) {
    	if(!num[i]) {	// 素数 
    		prime.push_back(i);
		} 
		for(int j = 0; j < prime.size(); j++) {
			if(i * prime[j] <= n) {
				num[i * prime[j]] = true;	// 合数 
			}
			// 核心代码：剪枝，保证每个合数只会被它的最小质因数筛去
			if(i % prime[j] == 0) {
				break;
			}
		}
	}
    return 0;
}

0x02 C++ 标准模板库（STL）

C++中为使用者提供了标准模板库（Standard Template Library，STL），其中封装了很多相当实用的容器，且定义与常用函数大同小异，在使用时都需要在宏定义下加上一句 using namespace std; 。

下面介绍一些较为常用的几个。

1. vector

vector翻译为向量，但这里使用「动态数组」的叫法更容易理解，作用类似于 Java 中的 ArrayList。

使用vector需要添加头文件 #include<vector> ，此外，还需要加上一句 using namespace std; 。

1）vector的定义与初始化

单独定义一个 vector：

1
vector<typename> name;

typename 可以是基本类型（int、double、char、结构体），也可以是STL模板（vector、set、queue）。

（1）不带参数的构造函数初始化

1
2
//初始化一个size为0的vector
vector<int> abc;

（2）带参数的构造函数初始化

1
2
3
4
//初始化size,但每个元素值为默认值
vector<int> abc(10);    //初始化了10个默认值为0的元素
//初始化size,并且设置初始值
vector<int> cde(10，1);    //初始化了10个值为1的元素

（3）通过数组地址初始化

1
2
3
int a[5] = {1,2,3,4,5};
//通过数组a的地址初始化，注意地址是从0到5（左闭右开区间）
vector<int> b(a, a+5);

（4）通过同类型的vector初始化

1
2
3
vector<int> a(5,1);
//通过a初始化
vector<int> b(a);

（5）通过insert初始化

1
2
3
4
5
//insert初始化方式将同类型的迭代器对应的始末区间（左闭右开区间）内的值插入到vector中
vector<int> a(6,6);
vecot<int> b;
//将a[0]~a[2]插入到b中，b.size()由0变为3
b.insert(b.begin(), a.begin(), a.begin() + 3);
  • insert也可通过数组地址区间实现插入
1
2
3
4
int a[6] = {6,6,6,6,6,6};
vector<int> b;
//将a的所有元素插入到b中，同样是左闭右开区间
b.insert(b.begin(), a, a+6);
  • 此外，insert还可以插入m个值为n的元素
1
2
//在b开始位置处插入6个6
b.insert(b.begin(), 6, 6);

2）vector容器内元素的访问

vector一般由两种访问方式：

（1）通过下标访问

1
vi[index];

（2）通过迭代器访问

迭代器（iterator）可以理解为一种类似指针的东西，定义：

1
vector<typename>::iterator it = vi.begin();	// begin()为vi的首元素地址

易知 vi[i] 和 vi.begin() + i 是的等价的。

需要注意的是，end() 并不是 vi 的尾元素地址，而是尾元素的下一个地址。在 C++ 中，这种「左闭右开」的思维很常见，务必注意。

3）vector常用函数

（1）push_back()

顾名思义，push_back(x) 就是在 vector 后面添加一个元素 x，时间复杂度为 $O(1)$ 。

（2）pop_back()

pop_back() 用于删除 vector 的尾元素， 时间复杂度为 $O(1)$ 。

（3）size()

size() 用来获得 vector 中元素的个数， 时间复杂度为 $O(1)$ 。

（4）clear()

clear() 用来清空 vector 中的所有元素， 时间复杂度为 $O(N)$ 。

（5）insert()

insert(it, x) 用来向 vector 的任意迭代器 it 处插入一个元素 x， 时间复杂度为 $O(N)$ 。

（6）erase()

  • 删除单个元素：erase(it) 即删除迭代器为 it 处的元素。
  • 删除一个区间内的所有元素：erase(first, last) 即删除 [first, last) 区间内的所有元素。

2. set

set翻译为集合，是一个内部自动有序且不含重复元素的容器。

  • 使用set需要添加头文件 #include<set> 及 using namespace std; 。

  • set的定义及常见用法与vector大同小异，因此略。

3. string

在 C 语言中，一般使用字符数组 char str[] 来存放字符串，为了方便字符串操作，C++ 在 STL 中对 string 类型进行了封装。

使用 string 需要添加头文件 #include<string> 及 using namespace std 。

1）string的定义

定义string的方式与基本类型相同：

1
string str;

如果要初始化，可直接赋值：

1
string str = "abcd";

2）string 中内容的访问

（1）通过下标访问

  • 一般来说，可以直接像字符数组那样访问 string，即 str[i] ；

  • 如果要读入和输出整个字符串，则只能使用 cin 和 cout 。但实际上也能使用 c_str() 将string类型转换为字符数组再进行输出：

    1
    printf("%s\n", str.c_str());

（2）通过迭代器访问

一般仅通过（1）即可满足访问的要求，但是有些函数比如 insert() 和 erase() 则要求以迭代器为参数，其定义如下：

1
string::iterator it;

3）string常用函数示例解析

（1）operator+=

这是string的加法，可以直接将两个 string 拼接起来。

（2）compare operator

两个 string 类型可以直接使用 ==、!=、<、<=、>、>= 比较大小，比较规则是字典序。

（3）length() / size()

返回 string 的长度，即存放的字符数，时间复杂度为 $O(1)$ 。

（4）insert()

  • insert(pos, string) ： pos 位置插入字符串 string。

    1
    str.insert(3, str2);

  • insert(it, it2, it3) ：it 为原字符串的欲插入位置，it2 和 it3为待插字符串的首尾迭代器，表示串 [it2, it3) 将被插在 it 位置上。

    1
    str.insert(str.begin()+3, str2.begin(), str2.end());	// 把str2插入在str的3号位上

（5）erase()

  • 删除单个元素：str.erase(it)
  • 删除一个区间内的所有元素：
    1. str.erase(first, last) ，即删除 [first, last)
    2. str.erase(pos, length) ，其中 pos 为需要开始删除的起始位置，length为删除的字符个数。

（6）clear()

clear() 用于清空 string 中的数据，时间复杂度一般为 $O(1)$ 。

（7）substr()

substr(pos, len) 返回从 pos 号位开始、长度为 len 的子串，时间复杂度为 $O(len)$ 。

（8）find()

str.find(str2) ：

  • 当 str2 是 str 的子串时，返回其在 str 中第一次出现的位置；

  • 否则，返回 string::npos 。

    string::npos 是一个常数，其本身的值为 -1 或者 unsigned_int 的最大值，用以作为 find 函数失配时的返回值。

（9）replace()

  • str.replace(pos, len, str2) 把 str 从 pos 号位开始、长度为 len 的子串替换为 str2；
  • str.replace(it1, it2, str2) 把 str 的迭代器 [it1, it2) 范围的子串替换为 str2。

4. map

map翻译为映射，可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）。

使用 map 需要添加头文件 #include<map> 及 using namespace std 。

map 会以键从小到大的顺序自动排序，这是由于 map 内部是使用红黑树实现的（set也是），在建立映射的过程中会自动实现从小到大的排序功能。

1）map的定义

1
map<typename1, typename2> mp;

2）map容器内元素的访问

（1）通过下标访问

和访问普通数组是一样的，可以直接使用 mp['c'] 来访问它对应的 value。

（2）通过迭代器访问

1
map<typename1, typename2>::iterator it;

通过 it->first 和 it->second 来分别访问键和值。

3）map常用函数

（1）find()

find(key) 返回键为 key 的映射的迭代器，时间复杂度为 $O(logN)$ 。

（2）erase()

  • 删除单个元素：mp.erase(it) 或 mp.erase(key)
  • 删除一个区间内的所有元素：mp.erase(first, last) ，同样为左闭右开区间 [first, last)

（3）size()

size() 用来获取 map 中映射的对数，时间复杂度为 $O(1)$ 。

（4）clear()

clear() 用来清空 map 中的所有元素，复杂度为 $O(N)$ 。

5. queue

queue 翻译为队列，在 STL 中作为一个先进先出的容器。

使用 map 需要添加头文件 #include<queue> 及 using namespace std 。

1）queue的定义

1
queue<typename> name;

2）queue容器内元素的访问

由于队列（queue）本身就是一种先进先出的限制性数据结构，因此在 STL 中只能通过 front() 来访问队首元素，或通过 back() 来访问队尾元素。

3）queue常用函数

（1）front()、back()

front() 和 back() 分别获得队首元素和队尾元素。

（2）push()

push(x) 将 x 插入队尾。

（3）pop()

pop() 令队首元素出队。

（4）empty()

empty() 检查 queue 是否为空。在使用 front() 和 back() 前，务必判断队列是否为空。

（5）size()

size() 返回 queue 内元素的个数。

6. priority_queue

priority_queue 又称为优先队列，其底层使用堆来实现的。在任何时候，队首元素一定是当前队列中优先级最高的那一个。

使用 map 需要添加头文件 #include<queue> 及 using namespace std 。

1）priority_queue的定义

1
priority_queue<typename> name;

2）priority_queue容器内元素的访问

和队列（queue）不同的是，优先队列只能通过 top() 来访问队首元素（也可以说是堆顶元素）。

3）priority_queue常用函数

（1）top()

top() 可以获得队首元素（即堆顶元素）。

（2）push()

push(x) 令 x 入队，并自动调整底层数据结构，时间复杂度为 $O(logN)$。

（3）pop()

pop() 令队首元素出队。

（4）empty()

empty() 检查优先队列是否为空。在使用 front() 和 back() 前，务必判断队列是否为空。

（5）size()

size() 返回优先队列内元素的个数。

4）priority_queue内元素优先级的设置

（1）基本数据类型的优先级设置

优先队列的默认优先级是数字大的优先级越高（大顶堆），即下面两种优先队列的定义是等价的：

1
2
priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;

在第二种定义方式中，

  • vector<int> 表示承载底层数据结构堆（heap）的容器；
  • less<int> 是对第一个参数的比较类，less<int> 表示数字大的优先级越大，greater<int> 表示数字小的优先级越大。

如果想把最小的元素放在队首（小顶堆），则只需如下定义：

1
priority_queue<int, vector<int>, greater<int>> q;

（2）结构体的优先级设置

我们不妨对水果的名称和价格建议一个结构体。现在希望按水果的价格高的为优先级高，则需要重载（overload）小于号 “<” 。

1
2
3
4
5
6
7
struct fruit {
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {
        return f1.price < f2.price;
    }
}

其中，friend 为友元，bool operator < (fruit f1, fruit f2) 则对 fruit 类型的操作符 “<” 进行了重载。

这里务必注意，如果再重载大于号会导致编译出错。因为从数学上来说，f1 > f2 等价于判断 f2 < f1，因此只需要重载小于号即可。

此时就可以直接定义 fruit 类型的优先队列，其内部就是以价格高的水果为优先级高：

1
priority_queue<fruit> q;

同理，如果想要以价格低的水果为优先级高，那么只需要把 return 中的小于号改成大于号即可，如下：

1
2
3
4
5
6
7
struct fruit {
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {
        return f1.price > f2.price;	// 改为大于号，表示价格更低的优先级更高
    }
}

这里重载大于号 “>” 也可以，但在定义时就需要：

priority_queue<fruit, vector, greater> q;

因为默认的定义方式中，优先级比较函数为 less<int> ，即小于号 “<”。

不难注意到，这里重载小于号和排序函数 sort() 中的 cmp 函数有些相似，只是效果看上去似乎是“相反”的。

比如对于 return f1.price > f2.price ：

  • 在排序中，是按价格从高到低排序；

    符合正常思维，价格越高，优先级越高（返回1），因而应排在前面，所以是从高到低排序。

  • 在优先队列中，却是把价格低的放到队首（堆顶）。

7. stack

stack 翻译为栈，是 STL 中实现的一个后进先出的容器。

使用 stack 需要添加头文件 #include<stack> 及 using namespace std 。

1）stack的定义

1
stack<typename> name;

2）stack容器内元素的访问

由于栈（stack）本身就是一种后进先出的限制性数据结构，因此在 STL 中只能通过 top() 来访问栈顶元素。

3）stack常用函数

（1）top()

top() 获得栈顶元素，时间复杂度为 $O(1)$ 。

（2）push()

push(x) 将 x 入栈，时间复杂度 $O(1)$ 。

（3）pop()

pop(x) 弹出栈顶元素，时间复杂度 $O(1)$ 。

（4）empty()

empty() 可以检查栈是否为空。

（5）size()

size() 返回 stack 内元素的个数。

8. pair

pair 是一个很实用的“小玩意”，当想要将两个元素绑定在一起作为一个合成元素、又不像因此定义结构体时，使用 pair 可以很方便地作为一个替代品。实际上，pair 可以看做一个内部有两个元素的结构体。

1
2
3
4
struct pair {
    typeName1 first;
    typeName2 second;
}

使用 pair 需要添加头文件 #include<utility> 及 using namespace std 。

1）pair的定义

1
pair<typename1, typename2> name;

如果想在定义 pair 时进行初始化，只需跟上一个小括号即可：

1
pair<string, int> p("haha", 5);

如果想要在代码中临时构建一个pair，有如下两种方式：

1
2
3
4
// 1. 将类型定义写在前面，后面用小括号内两个元素的方式
pair<string, int> ("haha", 5)
// 2. 使用自带的 make_pair 函数
make_pair("haha", 5)

2）pair中元素的访问

按正常结构体的方式访问即可，p.first 或 p.second 。

3）pair常用函数

两个pair类型数据可以直接使用 ==、!=、<、<=、>、>= 比较大小，比较规则是先以 first 的大小作为标准，只有当 first 相等时才去判别 second 的大小。

9. algorithm头文件下的常用函数

使用 algorithm 头文件，需要添加头文件 #include<algorithm> 及 using namespace std 。

1. 基本运算函数

  • max(x, y) 、min(x, y)：取 x 和 y 中的最大/小值，参数必须是两个，可以是浮点数。
  • abs(x)：取绝对值，x 必须是整数，浮点型的绝对值可使用 math.h 下的 fabs() 函数。
  • swap(x, y) ：交换 x 和 y 的值。

2. next_permutation()

next_permutation() ：给出一个序列在全排列中的下一个序列。

例如，当 n = 3 时的全排列：

1
2
3
4
5
6
123
132
213
231
312
321

这样 231 的下一个序列就是 312。

对于下面的程序：

1
2
3
4
int a[] = {2, 3, 1};
while(next_permutation(a, a+3)) {
    printf("%d%d%d", a[0], a[1], a[2]);
}

输出结果为：

1
2
312
321

3. reverse()

reverse(it1, it2) ：将数组指针或容器的迭代器在 [it1, it2) 之间的元素进行反转。

1
2
3
4
5
6
int a[] = {0, 1, 2, 3, 4, 5};
reverse(a, a+4);
// 3, 2, 1, 0, 4, 5
string str = "abcdefg";
reverse(str.begin() + 2, str.begin() + 5);
// abedcfg

4. fill()

fill() 可以把数组或容器中的某一段区间赋为某个相同的值。

1
fill(a, a+5, 233);	// 将 a[0]~a[4]均赋值为233

5. lower_bound() 和 upper_bound()

lower_bound() 和 upper_bound() 需要用在一个有序数组或容器中。

  • lower_bound(first, last, val) 用来寻找在数组或容器的 [first, last) 范围内第一个值大于等于 val 的元素的位置。

  • upper_bound(first, last, val) 用来寻找在数组或容器的 [first, last) 范围内第一个值大于 val 的元素的位置。

  • 如果是数组，则返回该位置的指针；如果是容器，返回该位置的迭代器。时间复杂度为 $O(log(last-first))$ 。

显然，如果只是想要获得欲查元素的下标，就可以不使用临时指针，而直接令返回值减去数组首地址即可。

6. sort()

顾名思义，sort() 就是用来排序的函数，它根据具体情形使用不同的排序方法，效率较高。

一般来说，不推荐使用 C 语言中的 qsort() 函数，原因是其用起来比较繁琐，涉及很多指针的操作。

而且 sort() 在实现中规避了经典快速排序中可能出现的会导致实际复杂度退化到 $O(n^2)$ 的极端情况。

1）如何使用 sort 排序

sort 函数的使用必须加上头文件 #include<algorithm> 和 using namespace std; ，其使用的方式如下：

1
sort(首元素地址， 尾元素地址的下一个地址， 比较函数（非必填）);

当没有比较函数时，默认进行递增排序。

2）如何实现比较函数 cmp

比较函数 cmp 用来“告诉” sort 何时需要交换元素。

  • 当 cmp(a, b) 返回 true 时，表明 a 优先级高于 b，a 排在 b 的前面。

（1）基本数据类型数组的排序

默认按照从小到大的顺序排序，如果想要从大到小排序，可以这样写：

1
2
3
bool cmp(int a, int b) {
    return a > b;
}

（2）结构体数组的排序

现定义如下结构体：

1
2
3
struct node {
    int x, y;
}

如果想先按 x 从大到小排序，但当 x 相等的情况下，按照 y 从小到大排序，那么：

1
2
3
4
5
6
bool cmp(node a, node b) {
    if(a.x != b.x) 
        return a.x > b.x;
    else
        return a.y < b.y;
}

（3）容器的排序

以 vector 为例，从大到小排序：

1
2
3
4
bool cmp(int a, int b) {
    return a > b;
}
sort(vi.begin(), vi.end(), cmp);	// 对整个vector排序

对于 string 来说：

1
2
string str[3] = {"bbbb", "cc", "aaa"}
sort(str, str + 3);		// 将string型数组按字典序从大到小输出

0x03 数据结构专题

1. 栈

栈（stack）是一种后进先出的数据结构。栈顶指针是始终指向栈的最上方元素的一个标记，通常记为 TOP。

栈的常见操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 清空操作，将栈顶指针置为-1，表示栈中没有元素
void clear() {
    TOP = -1;
}
// 获取栈内元素个数
int size() {
    return TOP + 1;
}
// 判空
bool empty() {
    if(TOP == -1)	return true;
    else			return false;
}
// 压栈
void push(int x) {
    s[++TOP] = x;
}
// 弹栈
void pop() {
    TOP--;
} 
// 取栈顶元素
int top() {
    return s[TOP];
}

2. 队列

队列（queue）是一种先进先出的数据结构，队列总是从队尾加入元素，而从队首移除元素。一般来说，需要一个队首指针 front 来指向队首元素的前一个位置，而使用队尾指针 rear 来指向队尾元素。

队列的常见操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 清空操作，还原为初始状态
void clear() {
    front = rear = -1;
}
// 获取栈内元素个数
int size() {
    return rear - front;
}
// 判空
bool empty() {
    if(front == rear)	return true;
    else				return false;
}
// 入队，排在队尾
void push(int x) {
    q[++rear] = x;
}
// 出队，移除队首
void pop() {
    front++;
} 
// 取队首元素
int get_front() {
    return q[front + 1];	// 注意需要+1
}
// 取队尾元素
int get_rear() {
    return q[rear];
}

3. 链表

1）链表的概念

按正常方式定义一个数组时，计算机会从内存中取出块连续的地址来存放给定长度的数组；而链表由若干个节点组成，且结点在内存中的存储位置通常是不连续的。

链表的结点一般由两部分构成，即数据域和指针域；

1
2
3
4
struct node {
    typename data;	// 数据域
    node* next;		// 指针域
}

2）为链表结点分配内存空间

使用malloc函数或new运算法为链表结点分配内存空间。

（1）malloc 函数

malloc 函数时C语言中 stdlib.h 头文件下用于申请动态内存的函数，返回类型是申请的同变脸类型的指针，基本用法如下：

1
2
int* p = (int*) malloc(sizeof(int));
node* p = (node*) malloc(sizeof(node));

（2）new运算符

new 是C++中用来申请动态空间的运算符，其返回类型同样是申请的同变脸类型的指针，基本用法如下：

1
2
int* p = new int;
node* p = new node;

可以看到 new 的写法比 malloc 要简洁许多，只需要 “new + 类型名” 即可分配一块该类型的内存空间。

（3）内存泄露

C/C++语言的设计者认为，程序员完全有能力自己控制内存的分配与释放，因此把对内存的控制操作全部交给了程序员。

内存泄露是指使用 malloc 和 new 开辟出来的内存空间在使用过后没有释放，导致其在程序结束之前始终占据该内存空间。

  1. free 函数对应 malloc 函数：free(p) ；
  2. delete 运算符对应 new 运算符：delete(p) 。

3）链表的基本操作

（1）创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
node* create(vector<int> Array) {
    node *p, *pre, *head;
    head = new node;	// 创建头结点
    
    head->next = NULL;	// 头结点不需要数据域，指针域初始为 NULL
    pre = head;			// 头结点不需要数据域，指针域初始为 NULL
    for(int i = 0; i < Array.size(); i++) {
        p = new node;	// 新建结点
        p->data = Array[i];
        p->next = NULL;
        pre->next = p;	// 前驱结点链接当前结点
        pre = p;		// 把pre设为p，作为下个结点的前驱结点
    }
    return head;		// 返回头结点指针
}

（2）查找元素

链表的查询操作每次都需要从头开始，时间复杂度为为 $O(N)$ 。

1
2
3
4
5
6
7
8
9
10
11
int search(node* head, int x) {
    int count = 0;		// 计数器
    node* p = head->next;
    while(p != NULL) {
        if(p->data == x) {
            count++;
        }
        p = p->next;
    }
    return count;
}

（3）插入元素

将 x 插入到第pos个位置上。

1
2
3
4
5
6
7
8
9
10
void insert(node* head, int pos, int x) {
    node* p = head;
    for(int i = 0; i < pos - 1; i++) {
        p = p->next;	// 保证pos位置不越界
    }
    node* q = new node;
    q->data = x;
    q->next = p->next;
    p->next = q;
}

（4）删除元素

对链表来说，删除元素是指删除链表上所有值为给定的数x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void del(node* head, int x) {
    node* p = head->next;
    node* pre = head;
    while(p != NULL) {
        if(p->data == x) {
            pre->next = p->next;
            delete(p);
            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

4）反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *p = pHead;
        ListNode *nex = nullptr;
        while(p != nullptr) {
            nex = p->next;
            p->next = pre;
            
            pre = p;
            p = nex;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        // 1. 统计组数 n
        ListNode *p = head;
        int cnt = 0, n = 0;
        while(p != NULL) {
            cnt++;
            if(cnt == k) {
                n++, cnt = 0;
            }
            p = p->next;
        }
        if(n == 0)     // 无需翻转
            return head;
        
        // 2. 按组翻转链表
        ListNode *pre, *nex;
        ListNode *preHead, *preTail;
        ListNode *curHead, *curTail;
        // init
        p = head;
        while(n--) {    // 总共翻转n组，且必能翻转n组，无需判断NULL
            // 2.1 组内翻转
            cnt = 0;
            pre = NULL;
            curHead = p, curTail = NULL;    // 翻转前保存当前组的首尾结点
            while(cnt < k) {    // 翻转当前组
                nex = p->next;
                p->next = pre;
                
                pre = p;
                p = nex;
                cnt++;
            }
            // 当前组内翻转完成，交换首尾结点
            curTail = curHead;
            curHead = pre;
            // 2.2 组间翻转
            // 前一个组的尾preTail连到当前组的头curHead，当前组的尾curTail连到后一个组的头p
            if(curTail == head) {    // 如果当前在第一组，则修改整个链表头head
                head = curHead;
                curTail->next = p;
            } else {
                preTail->next = curHead;
                curTail->next = p;
            }
            
            preHead = curHead;
            preTail = curTail;
        }
        return head;
    }
};

2021-5-27-第二次解题思路：似乎更简单一点？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        int n = 0;    // 结点个数
        ListNode *p = head;
        while(p != NULL) {
            n++; p = p->next;
        }
        int m = n / k;// m组
        if(m == 0) return head;
        
        // 当m > 0时
        ListNode *lastEnd, *lastHead;
        ListNode *curHead, *curEnd;
        p = head;
        for(int i = 0; i < m; i++) {
            curEnd = p;
            // 组内翻转
            ListNode *pre = NULL;
            ListNode *nex = NULL;
            int j = 0;
            while(j < k && p != NULL) {    // 其实p肯定不会是NULL
                nex = p->next;
                p->next = pre;

                pre = p;
                p = nex;
                j++;
            }
            // 组间相连
            curHead = pre;
            if(i == 0) {
                head = curHead;
            } else {
                lastEnd->next = curHead;
            }
            
            lastEnd = curEnd;
            lastHead = curHead;
        }
        lastEnd->next = p;
        
        return head;
    }
};

4. 树与二叉树

1）树的定义与性质

（1）树的定义

  • 树的层次（layer）从根结点开始算起，即根结点为第一层。
  • 把结点的子树棵树称为结点的度（degree），而树中结点最大的度称为树的度。叶子结点被定义为度为0的结点。
  • 由于一条边连接两个结点，且树种不存在环，因此对有n个结点的树，边数一定是n-1。且满足连通、边数等于顶点数减1的结构一定是一棵树。
  • 多棵树组合在一起称为森林（forest），即森林是若干棵树的集合。

（2）二叉树的定义

二叉树由根结点、左子树、右子树组成，且左子树和右子树都是二叉树。

注意区分二叉树与度为2的树的区别。

  • 度不同
    • 度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。
    • 二叉树的要求是度不超过2，节点最多有两个叉，可以是1或者0。
  • 次序不同
    • 度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。

在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

下面介绍两种特殊的二叉树：

  1. 满二叉树：每一层的结点个数都达到了当层能达到的最大结点数。
  2. 完全二叉树：除了最下面的一层外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点。

2）二叉树的存储结构与基本操作

（1）二叉树的存储结构

1
2
3
4
5
struct node {
    typename data;	// 数据域
    node* lchild;	// 指向左子树根结点的指针
    node* rchild'	// 指向右子树根结点的指针
}

新建结点：

1
2
3
4
5
6
7
// 生成一个新结点，v为结点权值
node* newNode(int v) {
    node* Node = new node;
    Node->data = v;
    Node->lchild = Node->rchild = NULL;	// 初始状态下没有左右孩子
    return Node;
}

（2）二叉树结点的查找、修改

1
2
3
4
5
6
7
8
9
10
void search(node* root, int x, int newdata) {
    if(root == NULL) {
        return ;
    }
    if(root->data == x) {
        root->data = newdata;
    }
    search(root->lchild, x, newdata);
    search(root->rchild, x, newdata);
}

（3）二叉树结点的插入

结点的插入位置一般取决于数据域需要在二叉树中存放的位置，且对给定的结点来说，它在二叉树中的插入位置只会有一个。因此可以得到结论：二叉树结点的插入位置就是数据域在二叉树中查找失败的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
// insert函数将在二叉树中插入一个数据域为x的新结点
// 注意根结点指针root要使用引用，否则插入不会成功
void insert(node* &root, int x) {
    if(root == NULL) {		// 空树，说明查找失败，也即插入位置（递归边界）
        root = newNode(x);
        return ;
    }
    if(由二叉树的性质，x应该插在左子树) {
        insert(root->lchild, x);
    } else {
        isnert(root->rchild, x);
    }
}

这里很关键的一点是**根结点指针root使用了引用&**。如果不使用引用，root = new node 这个语句对root的修改就无法作用到原变量上（即上一层的 root->lchild 与 root->rchild）上去，也就不能把新结点接到二叉树上面。

（4）二叉树的创建

1
2
3
4
5
6
7
8
// 二叉树的建立
node* Create(int data[], int n) {
    node* root = NULL;	
    for(int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

（5）完全二叉树的存储结构

对完全二叉树来说，除了采用二叉链表的存储结构歪，还有更方便的存储方法。

对一棵完全二叉树，如果给它的所有结点按从上到下、从左到右的顺序进行编号。

那么对完全二叉树当中的任何一个结点x，其左孩子的编号一定是2x，而右孩子的编号一定是2x+1。

3）二叉树的遍历

二叉树的遍历有四种：先序遍历、中序遍历、后序遍历，以及层次遍历。其中，前三种都是用DFS实现，而层次遍历一般用BFS实现。

对于前三种遍历方式，左子树一定先于右子树，且所谓的“先中后”都是指根结点root在遍历中的位置。

（1）先序遍历

先序遍历的顺序是 “ 根结点 → 左子树 → 右子树 ”。对于一棵二叉树的先序遍历序列，序列的第一个一定是根结点。

1
2
3
4
5
6
7
8
9
10
11
void preorder(node* root) {
    if(root == NULL) {
        return ;		// 到达空树，递归边界
    }
    // 访问根结点 root，例如将其数据域输出。
    printf("%d\n", root->data);
    // 访问左子树
    preorder(root->lchild);
    // 访问右子树
    preorder(root->rchild);
}

（2）中序遍历

中序遍历的顺序是 “ 左子树 → 根结点 → 右子树 ”。因此，只要知道根结点，就可以通过根结点在中序遍历序列中的位置区分出左子树和右子树。

1
2
3
4
5
6
7
8
9
10
11
void inorder(node* root) {
    if(root == NULL) {
        return ;
    }
    // 访问左子树
    inorder(root->lchild);
    // 访问根结点 root，例如将其数据域输出。
    printf("%d\n", root->data);
    // 访问右子树
    inorder(root->rchild);
}

（3）后序遍历

后序遍历的顺序是 “ 左子树 → 右子树 → 根结点”。对后序遍历来说，序列的最后一个一定是根结点。

1
2
3
4
5
6
7
8
9
10
11
void postorder(node* root) {
    if(root == NULL) {
        return ;
    }
    // 访问左子树
    postorder(root->lchild);
    // 访问右子树
    postorder(root->rchild);
    // 访问根结点 root，例如将其数据域输出。
    printf("%d\n", root->data); 
}

总的来说，必须知道中序遍历序列才能唯一地确定一棵树。因为只有通过中序遍历序列才能利用根结点把左右自述分开，从而递归生成一棵二叉树。

（4）层序遍历

层序遍历是指按层次的顺序从根结点向下逐层进行遍历，且对同一层的结点为从左到右遍历。这个过程和BFS很像，因为BFS进行搜索总是以广度作为第一关键词，而对应到二叉树中广度又恰好体现在层次上。

1
2
3
4
5
6
7
8
9
10
11
void LayerOrder(node* root) {
    queue<node*> q;		// 注意队列里存的是地址
    q.push(root);
    while(!q.empty()) {
        node* now = q.front();	// 取队首元素
        q.pop();
        printf("%d", now->data);
        if(now->lchild != NULL) q.push(now->lchild);	// 左子树非空
        if(now->rchild != NULL) q.push(now->rchild);	// 右子树非空
    }
}

4）从遍历序列中重建二叉树

【结论】

中序序列可以与先序序列、后序序列、层序序列中的任意一个来构建唯一的二叉树，而后三者两两搭配或是三个一起上都无法构建唯一的二叉树。

【示例】

假设已知先序序列为 pre1, pre2, …, pren，中序序列为 in1, in2, …, inn，重建这棵二叉树。

image-20210307102538238

如上图所示，可以首先通过先序序列确定根结点，在由中序序列将其划分为左子树和右子树，得到左右子树的结点个数，进而能够在先序序列中划分出左右子树，并对左右子树递归进行上述操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 当前先序序列区间为 [preL, preR]，中序序列区间为 [inL, inR]，返回根结点地址
node* create(int preL, int preR, int inL, int inR) {
    if(preL > preR) {
        return NULL;	// 先序序列长度小于等于0时，直接返回
    }
    node* root = new node;		// 新建根结点
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++) {
        if(in[k] == pre[preL]) {	// 在中序序列中找到根结点
            break;
        }
    }
    
    int numLeft = k - inL;		// 左子树的结点个数
    // 左子树的先序区间为 [preL + 1, preL + numLeft]，中序区间为 [inL, k-1]
    root->lchild = create(preL + 1, preL + numLeft, inL, k - 1);	// 返回左子树的根结点
    // 右子树的先序区间为 [preL + numLeft + 1, preR]，中序区间为 [k + 1, inR]
    root->rchild = create(preL + numLeft + 1, preR, k + 1, inR);	// 返回左子树的根结点
    
    return root;		// 返回根结点地址 
}

5）从树的遍历看 DFS 与 BFS

（1）深度优先搜索与先序遍历

事实上，对所有合法的DFS求解过程，都可以把它画成树的形式，此时死胡同等价于树中的叶子结点，而岔道口等价于树中的非叶子结点，并且对这棵树的DFS遍历过程就是树的先序遍历的过程。

在DFS过程中，提到过剪枝的概念，即对某条可以确定不存在解的子树采取直接剪断的策略，前提是要保证剪枝的正确性，否则可能因减掉了有解的子树而最终获得了错误的答案。

（2）广度优先搜索与层序遍历

事实上，对所有合法的BFS求解过程，都可以把它画成树的形式，并将其转换为树的层序遍历的问题。

6）寻找最近公共祖先

基本思想为从根结点开始递归向下查找两个子节点 t1 和 t2。

  • 递归返回条件为当前节点为待查节点 t1 或 t2；

  • 对于两个子树的查找结果，有三种可能：

    1. 左右子树均非空，即 t1 和 t2 分别在左右子树，那么 root 即为最近公共祖先；
    2. 左子树非空，右子树为空，即 t1 和 t2 均在左子树，那么 left 返回的结点即为最近公共祖先；
    3. 右子树非空，左子树为空，与2刚好相反。
1
2
3
4
5
6
7
8
9
10
Node* searchAncestor(Node *root, Node *t1, Node *t2) {
	if(root == NULL || root == t1 || root == t2) return root;
	
	Node *left = searchAncestor(root->child1, t1, t2);
	Node *right = searchAncestor(root->child2, t1, t2);
	if(left && right) 
		return root;
	else 
		return left == NULL? right : left;
}

7）判断二叉树是否为二叉查找树/完全二叉树

牛客网 - 判断一棵二叉树是否为搜索二叉树和完全二叉树

二叉查找树的特点是：左孩子 < 根结点 < 右孩子，因此中序遍历的结果一定是一个递增序列，基于此判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    void inOrder(TreeNode* root, vector<int>& inSeq) {
        if(root == NULL) return ;
        
        inOrder(root->left, inSeq);
        inSeq.push_back(root->val);
        inOrder(root->right, inSeq);
    }
    
    vector<bool> judgeIt(TreeNode* root) {
        // write code here
        bool isST = true;
        // 1. 验证二叉搜索树
        // 中序遍历，值一定是递增的
        vector<int> inSeq;
        inOrder(root, inSeq);
        for(int i = 0; i < inSeq.size() - 1; i++) {
            if(inSeq[i] > inSeq[i+1]) {
                isST = false;
                break;
            }
        }
        return isST;
    }
};

完全二叉树的判断相对复杂一些。

  • 对于根节点，我们定义其编号为 1。然后，对于每个节点 v，我们将其左节点编号为 2 * v，将其右节点编号为 2 * v + 1。
  • 我们可以发现，树中所有节点的编号按照层序遍历顺序正好是升序。
  • 然后，我们检测编号序列是否为无间隔的 1, 2, 3, …，事实上，我们只需要检查最后一个编号是否正确即可，因为最后一个编号的值最大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return bool布尔型vector
     */
    struct Node {
        int val;
        int index;
        struct Node *left;
        struct Node *right;
        
        Node() {}
        Node(int _val, int _index) {
            val = _val;
            index = _index;
        }
    };
    
    Node* createTree(TreeNode* root, int ind) {
        if(root == NULL) return NULL;
        
        Node* node = new Node(root->val, ind);
        node->left = createTree(root->left, 2 * ind);
        node->right = createTree(root->right, 2 * ind + 1);
        return node;
    }
    
    vector<bool> judgeIt(TreeNode* root) {
        // 2. 验证全二叉树
        // 层序遍历，并按下标从1开始编号，验证最后一个元素编号是否为n即可。
        Node* nRoot = createTree(root, 1);	// 重建二叉树，加入编号信息
        vector<int> layerOrder;				// 层序遍历
        queue<Node*> q;
        q.push(nRoot);
        while(!q.empty()) {
            Node* node = q.front(); q.pop();
            layerOrder.push_back(node->index);
            
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        int n = layerOrder.size();
        isFT = layerOrder[n - 1] == n;
        
        return isFT;
    }
};

5. 树的延伸算法

1）二叉查找树（BST）

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，又称为二叉搜索树。其核心思想是：左子树上所有结点均小于等于根结点，右子树上所有结点均大于根结点。

（1）查找操作

BST的性质决定了每次只需要选择其中一棵子树进行遍历，因此查找将会是从树根到查找结点的一条路径，故最坏复杂度是 $O(logn)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// search 函数查找二叉查找树中数据域为x的结点
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);		// 往左子树搜索x
    } else {
        search(root->rchild, x);		// 往右子树搜索x
    }
}
（2）插入操作

当需要查找的值在BST中查找失败时，说明这个地方一定是结点需要插入的地方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// insert 函数将在二叉树中插入一个数据域为x的新结点（注意参数root要加引用&）
void insert(node* &root, int x) {
    if(root == NULL) {		// 空树，查找失败，亦即插入位置
        root = newNode(x);
        return ;
    }
    if(x == root->data) {
        return ;			// 查找成功，结点已存在，返回
    } else if(x < root->data) {
        insert(root->lchild, x);		// 往左子树搜索x
    } else {
        insert(root->rchild, x);		// 往右子树搜索x
    }
}
（3）创建操作

建立一棵二叉查找树，就是先后插入n个结点的过程，这和一般二叉树的建立是完全一样的：

1
2
3
4
5
6
7
8
// 二叉查找树的建立
node* Create(int data[], int n) {
    node* root = NULL;
    for(int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}
（4）删除操作

我们首先定义两个概念，对于二叉查找树中的某个结点 x，

  • 把比结点权值小的最大结点称为该结点的前驱；
  • 把比结点权值大的最小结点称为该结点的后继。

显然，结点的前驱是该结点左子树中的最右结点，而结点的后继则是该结点右子树中的最左结点。

当我们删除二叉查找树中的某个结点 x 时，为了保证删除操作之后仍然是一棵二叉查找树，需要用 x 的前驱结点或后继结点覆盖 x。

如下图，如果需要删掉根结点5，一种办法是用结点4（前驱）来覆盖结点5，另一种办法是用结点6（后继）来覆盖结点5。

image-20210307130118715

下面两个函数用来寻找以 root 为根的树中最大或最小权值的结点，用以辅助寻找结点的前驱和和后继：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 寻找以 root 为根结点的树中的最大权值结点
node* findMax(node* root) {
    while(root->rchild != NULL) {
        root = root->rchild;		// 不断往右，直到没有右孩子
    }
    return root;
}
// 寻找以 root 为根结点的树中的最小权值结点
node* findMin(node* root) {
    while(root->lchild != NULL) {
        root = root->lchild;		// 不断往左，直到没有左孩子
    }
    return root;
}

假设决定用结点N的前驱P来替换N，那么删除操作的基本思路如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 删除以root为根结点的树中权值为x的结点
void deleteNode(node* &root, int x) {
    if(root == NULL)	return;		// 不存在权值为 x 的结点
    if(x == root->data) {			// 找到欲删除结点
        if(root->lchild == NULL && root->rchild == NULL) {
            // 叶子结点，直接删除
            root = NULL;
        } else if(root->lchild != NULL) {
            // 左子树不为空时，优先用前驱覆盖root
            node* pre = findMax(root->lchild);
            root->data = pre->data;
            deleteNode(root->lchild, pre->data);	// 在左子树中删除结点pre
        } else {
            // 左子树为空但右子树不为空时，用后继覆盖root
            node* next = findMin(root->rchild);
            root->data = next->data;
            deleteNode(root->rchild, next->data);	// 在右子树中删除结点next
        }
    } else if(x < root->data) {
        deleteNode(root->lchild, x);// 在左子树中删除x
    } else {
        deleteNode(root->rchild, x);// 在右子树中删除x
    }
}

需要注意的是，总是优先删除前驱（或后继）容易导致树的左右子树高度极不平衡，使得二叉查找树退化成一条链。解决的办法有两种：

  1. 每次交替删除前驱或后继；
  2. 记录子树高度，总是优先在高度较高地一棵子树里删除结点。

当然，上述代码还可以通过很多手段优化。例如，找到欲删除结点5的后继结点6后，不进行递归，而是将结点6的右子树替代结点6，成为结点8的左子树。

（5）二叉查找树的性质

“对二叉查找树进行中序遍历，遍历的结果是有序的”。这是因为二叉查找树本身就具有 “左子树 < 根结点 < 右子树” 的特点，而中序遍历又是按照 “左子树 → 根结点 → 右子树” 的顺序进行访问的，因而中序遍历序列是有序的。

2）平衡二叉树（AVL）

首先考虑一下上一小节的二叉查找树有什么缺陷。考虑使用序列 {1,2, 3, 4, 5} 来构建二叉查找树，会得到如下图所示的BST：

image-20210307145811736

显然，这棵二叉查找树是链式的，此时对这棵树中结点进行查找的复杂度就会达到 $O(n)$ 。为了能使树的高度在每次插入元素后仍然能爆出 $O(logn)$ 的级别，平衡二叉树（AVL）诞生了。

AVL仍然是一棵二叉查找树，只是增加了“平衡”的要求。

  • 平衡：对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1。
  • 平衡因子：对AVL树的任意结点来说，其左子树与右子树的高度之差称为该节点的平衡因子。

因此需要在树的结构中加入一个变量 height，用来记录以当前结点为根结点的子树的高度：

1
2
3
4
struct node {
    int v, height;
    node* lchild, rchild;
}

显然，结点 root 所在子树的高度等于其左子树的 height 与右子树的 height 的较大值加1：

1
2
3
4
5
6
7
8
9
10
// 获取以root为根结点的子树的height
int getHeight(node* root) {
    if(root == NULL)	return 0;
    return root->height;
}
// 更新结点root的height
void updateHeight(node* root) {
    // max(左孩子的height， 右孩子的height) + 1
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
（1）查找操作

由于 AVL 是一棵二叉查找树，因此查找操作与 BST 相同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// search 函数查找二叉查找树中数据域为x的结点
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);		// 往左子树搜索x
    } else {
        search(root->rchild, x);		// 往右子树搜索x
    }
}
（2）旋转操作

如下图，以左旋为例，假设B希望成为根结点，由于 A < B，因而A将成为B的左子树，那么B原来的左子树 ◆ 呢？考虑到 A < ◆ < B，于是让 ◆ 成为A的右子树即可。

image-20210307154641717

这个调整过程被称为左旋（Left Rotation），可以分为三个步骤：

  1. 让 B 的左子树 ◆ 成为 A 的右子树；
  2. 让 A 成为 B 的左子树；
  3. 将根结设定为结点 B。
image-20210307154851200

对应的代码如下：

1
2
3
4
5
6
7
8
9
// 左旋（Left Rotation）
void L(node* &root, node* temp) {	
    // root指向A，temp指向B
    root->rchild = temp->lchild;	// 步骤1
    temp->lchild = root;			// 步骤2
    updateHeight(root);		// 更新结点A的高度
    updateHeight(temp);		// 更新结点B的高度
    root = temp;					// 步骤3
}

右旋（Right Rotation）和左旋是对称的过程，即左旋的逆过程，实现步骤和左旋基本相同，直接上代码：

1
2
3
4
5
6
7
8
9
// 右旋（Right Rotation）
void R(node* &root, node* temp) {	
    // root指向B，temp指向A
    root->lchild = temp->rchild;	// 步骤1
    temp->rchild = root;			// 步骤2
    updateHeight(root);		// 更新结点B的高度
    updateHeight(temp);		// 更新结点A的高度
    root = temp;					// 步骤3
}
（3）插入操作

AVL 的插入操作比较复杂，且需要用到旋转操作，我们一步一步分析：

  • 在往 AVL 中插入一个结点时，一定会有结点的平衡因子发生变化，此时可能会有结点的平衡因子的绝对值大于1。

    （且只可能是2或-2，因为只插入了一个结点，树的高度只可能变化1）

  • 显然，只有在从根结点到该插入节点的路径上的结点才可能发生平衡因子变化，因此只需对这条路径上失衡的结点进行调整。

  • 可以证明，“只要把最靠近插入节点的失衡结点调整到正常，路径上的所有结点就会平衡”。

下举例说明：

假设最靠近插入结点的失衡结点是A，显然它的平衡因子只可能是2或者-2，这两种情况是完全对称的。

  • 假设A的平衡因子是2，即左子树的高度比右子树大2，那么以A为根结点的子树一定是下图 LL型与 LR型之一。

    image-20210307164602382

    可以发现，当A的左孩子的平衡因子是1时为 LL型，是-1时为 LR型 。

  • 假设A的平衡因子是-2，即左子树的高度比右子树小2，那么以A为根结点的子树一定是下图 RR型与 RL型之一。

    image-20210307165656377

    可以发现，当A的右孩子的平衡因子是-1时为 RR型，是1时为 RL型 。

【调整】

现在考虑怎样调整这四种树型，才能使树平衡。

  • 对于LL型，可以把以C为根结点的子树看作一个整体，然后以结点A作为root进行右旋，便可以达到平衡：

    image-20210307165332820

  • 对于LR型，可以先忽略结点A，以C为root进行左旋，就可以把情况转化为LL型，然后按照上面LL型的做法进行一次右旋即可：

    image-20210307165452611

  • 对于RR型，可以把以C为根结点的子树看作一个整体，然后以结点A作为root进行左旋，便可以达到平衡：

    image-20210307165942851

  • 对于RL型，可以先忽略结点A，以C为root进行右旋，就可以把情况转化为RR型，然后按照上面RR型的做法进行一次左旋即可：

    image-20210307165959809

【汇总】

至此，对LL型、LR型、RR型、RL型的调整方法都已经讨论清楚，下面做个小小的汇总：

树型 判定条件 调整方法
LL BF(root) = 2 且 BF(root->lchild) = 1 对root进行右旋
LR BF(root) = 2 且 BF(root->lchild) = -1 先对 root->lchild 进行左旋，再对root进行右旋
RR BF(root) = -2 且 BF(root->rchild) = -1 对root进行左旋
RL BF(root) = -2 且 BF(root->rchild) = 1 先对 root->rchild 进行右旋，再对root进行左旋

【代码】

AVL树的插入代码需要在二叉查找树的插入代码的基础上增加平衡操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 插入权值为v的结点
void insert(node* &root, int v) {
    if(root == NULL) {
        root = newNode(v);
        return ;
    }
    if(v < root->v) {
        insert(root->lchild, v);		// 往左子树插入
        updateHeight(root);				// 更新树高
        if(getBalanceFactor(root) == 2) {
            if(getBalanceFactor(root->lchild) == 1) {	// LL型
                R(root);
            } else if(getBalanceFactor(root->lchild) == -1)	// LR型
                L(root->lchild);
                R(root);
            }
        } 
    } else {
        insert(root->rchild, v);		// 往右子树插入
        updateHeight(root);				// 更新树高
        if(getBalanceFactor(root) == -2) {
            if(getBalanceFactor(root->rchild) == -1) {	// RR型
                L(root);
            } else if(getBalanceFactor(root->rchild) == 1)	// RL型
                R(root->rchild);
                L(root);
            }
        }
    }
}
（4）创建操作

有了插入操作的基础，AVL树的建立就非常简单了，只需依次插入n个结点即可。

1
2
3
4
5
6
7
8
// AVL树的建立
node* Create(int data[], int n) {
    node* root = NULL;
    for(int i = 0; i < n; i++) {
        insert(root, data[i]);
    }  
    return root;
}

3）并查集

算法学习笔记(1) : 并查集

在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题的特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，计算机无法承受。

并查集是一种树型的数据结构，它的名字中 “并”、“查”、“集” 分别取自 Union（合并）、Find（查找）、Set（集合）这三个词，用于处理这类不相交集合（disjoint sets）的合并及查询问题。

实际上，并查集就是一个数字：

1
int father[N];

其中 father[i] 表示元素 i 的父亲结点，而父亲结点本身也是这个集合内的元素。对于同一个集合来说只存在一个根结点，且将其作为所属集合的标识。

（1）初始化

一开始，每个元素都是独立的一个集合，因此需要令所有 father[i] = i ：

1
2
3
for(int i = 1; i <= N; i++) {
    father[i] = i;
}
（2）查找

查找操作就是对给定的结点寻找其根结点的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
/* findFather函数返回元素x所在集合的根结点*/
// 1.递推算法
int findFather(int x) {
    while(x != father[x]) {		// 如果不是根结点，继续循环
        x = father[x];			// 获得自己的父亲结点
    }
    return x;
}
// 2.递归算法
int findFather(int x) {
    if(x == father[x])	return x;	// 如果找到根结点，返回根结点编号x
    else	return findFather(father[x]);	// 否则，递归判断x的父亲结点是否是根结点
}
（3）合并

合并是指把两个集合合并成一个集合。一般是先判断两个元素是否属于同一个集合，只有当它们属于不同集合时才合并，而合并的过程一般是把其中一个集合的根结点的父亲指向另一个集合的根结点。

1
2
3
4
5
6
7
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA != faB) {
        father[faA] = faB;
    }
}
image-20210308201334299

由于在合并的过程中，只对两个不同的集合进行合并，这就保证了在同一个集合中一定不会产生环，即并查集产生的每一个集合都是一棵树。

（4）路径压缩

前面提到的并查集查找函数是未经优化的，在极端情况（比如当元素数量很多且形成一条链时）下效率较低。

优化方法如下：

image-20210308201515458

这样相当于把当前查询结点的路径上的所有结点的父亲都指向根结点，查找时就不需要一直回溯了。

1
2
3
4
5
6
7
8
9
10
11
12
int findFather(int x) {
    int root = x;
    while(root != father[root]) {	// 寻找根结点
        root = father[root];	
    }
    // 下面把路径上的所有结点的father都改成根结点
    while(x != father[x]) {
        int a = father[x];		// 记录x的father
        father[x] = root;		// 把x的father结点指向root
        x = a;					// 回溯
    }
}
（5）应用——亲戚问题

题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#define MAXN 5005
int fa[MAXN], rank[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}
int main()
{
    int n, m, p, x, y;
    scanf("%d%d%d", &n, &m, &p);
    init(n);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        merge(x, y);
    }
    for (int i = 0; i < p; ++i)
    {
        scanf("%d%d", &x, &y);
        printf("%s\n", find(x) == find(y) ? "Yes" : "No");
    }
    return 0;
}

4）堆

堆是一棵完全二叉树，树中每个节点的值都不小于（或不大于）其左右孩子结点的值。

  • 如果父亲结点大于等于孩子结点，称为大顶堆，此时每个结点的值都是以它为根结点的子树的最大值；
  • 如果父亲结点小于等于孩子结点，称为小顶堆，此时每个结点的值都是以它为根结点的子树的最小值；

对于完全二叉树来说，可以使用数组来定：

1
2
const int maxn = 100;
int heap[maxn], n = 10;

这样的话，第一个结点将存储于数组中的1号位，并且数组i号位表示的结点的左孩子就是2i号位，而右孩子则是2i+1号位。

（1）建堆

建堆是一个向下调整的过程：

  • 总是将当前节点 i 与它的左右孩子比较，若孩子的权值比 i 还大，就将两者交换；
  • 交换完毕后继续让节点 i 和孩子比较，直到 i 的孩子的权值都比 i 的权值小或者不存在孩子结点。

向下调整的代码如下，时间复杂度为 $O(logn)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 对heap数组在[low, high]范围进行向下调整
// 其中low为欲调整结点的数组下标，high一般为堆的最后一个元素的数组下标
void downAdjust(int low, int high) {
    int i = low, j = 2 * i;		// i为欲调整结点，j为其左孩子
    while(j <= high) {			// 存在孩子结点
    	// 如果右孩子存在，且右孩子的值大于左孩子
        if(j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        // 如果孩子中最大的权值比欲调整节点i大
        if(heap[j] > heap[i]) {
            swap(heap[j], heap[i]);
            i = j;				// 保持i为欲调整节点、j为i的左孩子
            j = i * 2;
        } else {
            break;				// 孩子的权值均比欲调整节点i小，调整结束
        }
    }
}

那么建堆的过程也就很容易了。由于完全二叉树的叶子节点个数为 $\lceil n/2 \rceil$ ，因此数组下标在 $[1, \lfloor n/2 \rfloor]$ 范围内的都是非叶子节点。于是可以从 $\lfloor n/2 \rfloor$ 号位开始倒着枚举结点，对每个遍历到的结点 i 进行 $[i, n]$ 范围的调整。这种做法能够保证每个调整完的结点都是以其为根结点的子树中的权值最大的结点。

建堆的代码如下，时间复杂度为 $O(n)$ 。

1
2
3
4
5
6
// 建堆
void createHeap() {
    for(int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
}
（2）删除堆顶元素

如果要删除堆中的最大元素，即堆顶元素，并让其仍然保持堆的结构，只需要最后一个元素覆盖堆顶元素，然后对根结点进行调整即可。

代码如下，时间复杂度为 $O(logn)$ 。

1
2
3
4
5
// 删除堆顶元素
void deleteTop() {
    heap[1] = heap[n--];	// 用最后一个元素覆盖堆顶元素，并让元素个数减1
    downAdjust(1, n);		// 从上向下调整堆顶元素
}
（3）向堆中添加元素

如果想要往堆里添加一个元素，可以把其放在数组最后，然后进行向上调整操作。

  • 向上调整总是把欲调整结点与父亲结点比较，如果权值比父亲大，就交换之，反复此过程。

向上调整的代码如下，时间复杂度为 $O(logn)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 对heap数组在[low, high]范围内进行向上调整
// 其中low一般设置为1，high表示欲调整节点的数组下标
void upAdjust(int low, int high) {
    int i = high, j = i / 2;	// i为欲调整结点，j为其父亲
    while(j >= low) {
        // 父亲权值小于欲调整结点i的权值
        if(heap[j] < heap[i]) {
            swap(heap[j], heap[i]);	// 交换父亲和欲调整结点
            i = j;			// 保持i为欲调整结点，j为i的父亲
            j = i / 2;
        } else {
            break;			// 父亲权值比与调整结点i的权值大，调整结束
        }
    }
}

在此基础上，就很容易实现添加元素的代码了：

1
2
3
4
5
// 添加元素x
void insert(int x) {
    heap[++n] = x;
    upAdjust(1, n);
}
（4）堆排序

堆排序是指使用堆结构对一个序列进行排序。

我们考虑递增排序的情况，对于一个大顶堆来说，堆排序的直观思路是：

  1. 取出堆顶元素，然后将堆的最后一个元素替换至堆顶，再进行一次针对堆顶元素的向下调整；
  2. 如此重复，直到堆中只有一个元素为止。

具体实现时，为了节省空间，可以倒着遍历数组：

  • 假设当前访问到 i号位，那么将堆顶元素与 i 号位的元素交换，接着在 $[1, i-1]$ 范围内对堆顶元素进行一次向下调整即可。
1
2
3
4
5
6
7
8
// 堆排序
void heapSort() {
    createHeap();		// 建堆
    for(int i = n; i > 1; i--) {
        swap(heap[i], heap[1]);		// 交换heap[i]与堆顶
        downAdjust(1, i-1);			// 调整堆顶
    }
}

5）哈夫曼树

先介绍经典的合并果子问题：

有n堆果子，每堆果子的质量已知，现在需要把这些果子合并成一堆，但是每次只能把两堆果子合并到一起，同时会消耗与两堆果子质量之和等值的体力。显然，在进行n-1次合并之后，就只剩下一堆了。为了尽可能节省体力，请设计出合并的次序方案，使得耗费的体力最少，并给出消耗的体力值。

例如有3堆果子，质量依次为1、2、9。那么可以先将质量为 1和2的果堆合并，新堆质量为3，因此耗费体力为3。接着，将新堆与原先的质量为9的果堆合并，又得到新的堆，质量为12，因此耗费体力为12。所以耗费体力之和为3+12=15。可以证明15为最小的体力耗费值。

为了解决这个问题，我们把每堆果子都看作结点，果堆的质量视作结点的权值，这样合并两个果堆的过程可以视作给它们生成一个父结点，于是把n堆果子合并成一堆的过程可以用一棵树来表示。

如下图是将 1、2、3、4、5、6 进行合并的某一种方案。

image-20210308224644236

把叶子结点的权值乘以路径长度的结果称为这个叶子结点的带权路径长度（Weighted Path Length of Tree, WPL）。那么树的WPL就等于所有叶子结点的WPL之和。

我们称带权路径长度最小的树为哈夫曼树（又称为最优二叉树）。显然，哈夫曼树可以不唯一，但最小WPL一定是唯一的。

（1）构造哈夫曼树

下面介绍构造一棵哈夫曼树的算法：

  1. 初始状态下共有n个结点（结点权值分别是给定的n个数），将它们视作n棵只有一个结点的树；
  2. 合并其中根结点权值最小的两棵树，生成两棵树根结点的父结点，权值为这两个根结点的权值之和，这样树的数量就少了一个；
  3. 重复操作2，直到只剩下一棵为止，这棵树就是哈夫曼树。

事实上，在很多实际场景中，不需要真的去构建一棵哈夫曼树，只需要能得到最终的带权路径长度即可。因此我们需要着重掌握的是哈夫曼树的构建思想：

  • 反复选择两个最小的元素，合并，直到只剩下一个元素。

因此，一般可以使用优先队列（小顶堆）来执行这种策略。

  1. 初始状态下降果堆的质量压入优先队列；
  2. 之后每次从优先队列顶部取出两个最小的数，将它们相加并重新压入优先队列；
  3. 重复操作2，直到只剩下一个数，此时就得到了消耗的最小体力。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<queue>
using namespace std;

// 代表小顶堆的优先队列
priority_queue<long long, vector<long long>, greater<long long>> q;

int main() {
    int n;
    long long temp, x, y, ans = 0;
    // input
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &temp);
        q.push(temp);
    }
    // 构建哈夫曼树
    while(q.size() > 1) {	// 优先队列中至少有两个元素
        x = q.top();
        q.pop();
        y = q.top();
        q.pop();
        q.push(x + y);		// 取出堆顶的两个元素，求和后压入优先队列
        ans += (x + y);		// 累计求和的结果
    }
    printf("%lld\n", ans);
    return 0;
}
（2）哈夫曼编码

对于任意一棵二叉树来说，如果把二叉树上的所有分支都进行编号，且做分值标记为0，右分支标记为1，那么对树上的任意一个结点，都可以根据从根结点出发到达它的分支顺序得到一个编号，且这个编号是唯一的。并且，对于任何一个叶子结点，其编号一定不会成为其他任何一个结点编号的前缀。

这有什么用呢？我们考虑下面这个问题：

假设现在有一个字符串，它由A、B、C、D这四个英文字符的一个或多个组成，例如 ABCAD。现在希望把它编码成一个01串，这样方便进行数据传输。能想到的一个办法是把A~D各自用一个01 串表示，然后拼接起来即可。

例如可以把A用0表示、B用1表示、C用 00表示、D用 01表示，这样 ABCAD就可以用0100001表示。但是很快就会发现，解码的时候无法知道开头的 01到底是 AB还是D（因为 AB和D的编码都是 01），因此这种编码方式是不行的。

为什么不行呢？这是因为存在一种字符的编码是另一种字符的编码的前缀，例如 A 的编码是 D的编码的前缀，于是一旦有某一种字符的编码拼接在 A的编码之后能产生D的编码，就会产生混淆，例如此处把B的编码拼接在A的编码之后能产生 D的编码。

因此，需要寻找一套编码方式，使得其中任何一个字符的编码都不是另一个字符的编码的前缀，同时把满足这种编码方式的编码称为前缀编码。

考虑进一步的问题，对一个给定的字符串来说，肯定有多种前缀编码的方式，但为了信息传递的效率，需要尽量选择长度最短的编码方式。因此，我们希望出现频次最高的字符对应的编码长度应最短。而如果把频数作为叶子结点的权值，那么字符串编码成01串后的长度实际上就是这棵树的带权路径长度。

显然，这个问题已经得到解决——就是哈夫曼树。这种由哈夫曼树产生的编码方式被称为哈夫曼编码。

image-20210308232052967 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct TreeNode {	// 树结点
    char ch;
    int freq;
    TreeNode *left, *right;
    TreeNode(char x, int f): ch(x), freq(f), left(nullptr), right(nullptr) {}
};
struct cmp {
    bool operator() (TreeNode* t1, TreeNode* t2) {
        return t1->freq > t2->freq;
    }
}
TreeNode* unionTree(TreeNode* t1, TreeNode* t2) {	// 合并两棵子树为一棵树
	TreeNode* temp = new TreeNode('#', t1->freq + t2->freq);
    temp->left = t1;
    temp->right = t2;
    return temp;
}
TreeNode* getHuffmanTree(vector<TreeNode*> V) {
    // 优先队列建立哈夫曼树，结点权重为字符出现频次，显然出现频次越高，在树中的位置应该越浅
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> q;
    for(auto &v: V) {
       q.push(v);
    }
   while(q.size() > 1) {
       TreeNode* t1 = q.top(); q.pop();
       TreeNode* t2 = q.top(); q.pop();
       q.push(unionTree(t1, t2));
   }
   return q.top();
}
void getHuffmanCode(TreeNode* root, map<char, string> &mp, string code) {
    // 递归哈夫曼树，统计得到哈夫曼编码的映射表mp
    if(!root->left && !root->right) {
        mp[root->ch] = code;
        return ;
    }
    getHuffmanCode(root->left, mp, code + "0");		// 左子树为0
    getHuffmanCode(root->right, mp, code + "1");	// 右子树为1
}

需要注意的是，哈夫曼编码是针对确定的字符串来讲的。只有对确定的字符串才能根据其中各字符的出现次数建立哈夫曼树，才有对应的哈夫曼编码。

0x04 图论专题

1. 图的定义和相关术语

  • 图由顶点（Vertex）和边（Edge）组成，每条边的两端都必须是图的两个顶点（可以是相同的顶点），记号 $G(V, E)$ 表示图的顶点集为 $V$ 、边集为 $E$ 。

  • 一般来说，图可分为有向图和无向图：

    • 有向图的所有边都有方向，即确定了顶点到顶点的一个指向；
    • 无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。
    • 在某些问题中，可以把无线图当作所有边都是两条有向边的有向图。

  • 顶点的度：指和该顶点相连的边的条数。

    • 对于有向图来说，顶点的出边条数称为出度，入边条数称为入度。

  • 顶点和边都可以有一定属性，而量化的属性称为权值，分别称为点权和边权。

2. 图的存储

1）邻接矩阵

设图 $G(V, E)$ 的顶点编号为 0,1, …, N-1，那么可以令二维数组 $G[N][N]$ 来存储，这个二维数组 $G[][] $ 被称为邻接矩阵。

  • 如果 $G[i][j]$ 为 1，说明从顶点 i 到顶点 j 之间有边。
  • 如果存在边权，也可以令 $G[i][j]$ 存放边权，对不存在的边可以置为 0或-1。
image-20210309101043767

虽然邻接矩阵比较好些，但如果顶点数目太大，会爆栈，且对于稀疏矩阵来说会浪费大量空间。

2）邻接表

如果把同一个顶点的所有出边放在一个列表中，那么N个顶点就会有N个列表，这N个列表被称为图G的邻接表，记为 $Adj[N]$。

image-20210309101241933

如果邻接表只存放每条边的终点编号，而不存放边权，则可以定义为：

1
vector<int> Adj[N];

如果需要同时存放边的终点编号和边权，那么可以建立结构体 Node：

1
2
3
4
5
strcut Node {
    int v;		// 边的终点编号
    int w;		// 边权
}
vector<Node> Adj[N];

3. 图的遍历

首先介绍两个概念：

  • 连通分量：
    • 在无向图中，如果两个顶点之间可以相互到达，那么就称这两个顶点连通；
    • 如果任意两个顶点都连通，则称图 $G$ 为连通图；否则，称 $G$ 为非连通图，且称其中的极大连通子图为连通分量。
  • 强连通分量：
    • 在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，就称这两个顶点强连通。
    • 如果任意两个顶点都强连通，则称图 $G$ 为强连通图；否则，称 $G$ 为非强连通图，且称其中的极大强连通子图为强连通分量。
image-20210309102337389

为了叙述上的方便，可以把连通分量和强连通分量均称为连通块。

可以想象，如果要遍历整个图，就要对所有连通块分别进行遍历。

1）深度优先搜索

DFS遍历图的基本思路：

  • 将经过的顶点设置为已访问，在下次递归碰到这个顶点时就不再去处理，直到整个图的顶点都被标记为已访问。
1
2
3
4
5
6
7
8
9
10
11
12
13
DFSTrave(G) {	// 遍历图G
    for(G的所有顶点u) {
        if(vis[u] == false)	// 如果u未被访问
            DFS(u);
    }
}
DFS(u) {		// 访问顶点u
    vis[u] = true;	// 设置u为已访问
    for(从u出发能到达的所有顶点v) {
        if(vis[v] == false)	// 如果v未被访问
            DFS(v);	// 递归访问v
    }
}

2）广度优先搜索

和树的遍历一样，使用BFS遍历图需要使用一个队列，其基本思路是：

  • 通过反复取出队首顶点，将该顶点可到达的未曾加入过队列的顶点全部入队，直到队列为空时遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BFSTrave(G) {	// 遍历图G
    for(G的所有顶点u) {
        if(inq[u] == false)	// 如果u未曾加入过队列
            BFS(u);
    }
}
BFS(u) {		// 遍历u所在的连通块
    queue q;	
    q.push(u);	// 将初始点u入队
    inq[u] = true;
    while(!q.empty()) {
        int u = q.front();	// 取出队首元素
        q.pop();
        for(从u出发可达的所有顶点v) {
            if(inq[v] == false) {
                q.push(v)	// 将v入队
                inq[v] = true;
            }
        }
    }
}

4. 最短路径

最短路径是图论中一个很经典的问题：给定图 $G(V, E)$ ，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。

1）Dijkstra 算法

Dijkstra 算法（迪杰斯特拉算法）用来解决单源最短路问题：

  • 给定图 G 和起点 s，通过算法得到 s 到达其他每个顶点的最短距离。

【基本思想】：

  • 对图 $G(V, E)$ 设置集合 S，存放已被访问的顶点，然后重复下面的操作 n 次，直到集合 S 已包含所有顶点。
    1. 每次从集合 V-S 中选择与起点 s 的距离最小的一个顶点（记为u），访问并加入集合S。
    2. 之后，令顶点u为中介点，优化起点 s 与所有从 u 能到达的顶点 v 之间的最短距离。
  • 如果需要输出最短路径，则需要一个最短路径数组 $Spath$ ，Spath[v] 表示从源点s到顶点v的最短路径上，v的直接前驱结点。

【伪代码】：

  • 集合 S 可以使用一个 bool 型数组 vis[] 来实现；令 int 型数组 d[] 标识起点s到达其他顶点的最短距离；
1
2
3
4
5
6
7
8
9
10
11
12
Dijkstra(G, d[], s) {
    初始化;
    for(循环n次) {
        u = 使 d[u] 最小的还未被访问的定点的标号;
        记u已被访问;
        for(从u出发能到达的所有顶点v) {
            if(v未被访问 && 以u为中介点使s到顶点v的最短距离d[v]更优) {
                优化 d[v];
            }
        }
    }
}

【邻接矩阵版】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int MAXN = 1000;	// 最大顶点数
const int INF  = 10000000;

int n, G[MAXN][MAXN];		// n为顶点数
bool vis[MAXN] = {false};	// 标记数组

void Dijkstra(int s) {
    // 初始化
    fill(d, d + MAXN, INF);	// 将整个d数组赋为 INF
    d[s] = 0;	// 起点s到达自身的距离为0
    // 循环n次
    for(int i = 0; i < n; i++) {
        // 找到一个使d[u]最小的u，MIN存放该最小的d[u]
        int u = -1, MIN = INF;	
        for(int j = 0; j < n; j++) {
            if(vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        
        // 找不到小于INF的d[u]，说明剩下的顶点和起点s不连通
        if(u == -1)	return ;
        // 若找到了，则标记u为已访问过的，并以u为中介优化其余顶点
        vis[u] = true;
        for(int v = 0; v < n; i++) {
            // 如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
            if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

void outputPath(int s, int t, vector<int> &path) {
	if(s == t) {
		printf("%d ", s);
		path.push_back(s);
		return ;
	}

	outputPath(s, Spath[t], path);	// 输出s->v的前驱结点
	printf("%d ", t);				// 输出v
	path.push_back(t);
}

【堆优化版】

前面介绍的算法时间复杂度为 $O(n^2)$ ，如果边数远小于 n^2 ，可以考虑使用小顶堆进行优化，这样每次取出距离s最小的结点的复杂度为 $O(1)$ ，每次更新进行调整的复杂度为 $O(elogn)$ 。

步骤如下：

  1. 将源点s加入堆，并调整堆；
  2. 取出堆顶元素u（即距离源点s最近的结点），从堆中删除，并对堆进行调整；
  3. 对所有与u相邻的，未访问过的，满足三角不等式的顶点v进行一次松弛操作：
    • 若v在堆中，更新距离，并调整该元素在堆中的位置；
    • 若点v不在堆中，加入堆，并调整堆。
  4. 重复上述操作，直到所有结点都被松弛过。

【拓展拔高】

前面介绍了Dijkstra算法的基本思想和用法，但实际上，题目肯定不会考得这么 “裸” ，更多时候会出现这样一种情况：

  • 即从起点到终点的最短距离最小的路径不止一条。

此时，题目会给出一个第二标尺（第一标尺是距离），要求在所有最短路径中选择第二标尺最优的一条路径。

第二标尺常见有下面三种出题方法：

  1. 给每条边再增加一个边权（比如花费），要求花费之和最小；
  2. 给每个点增加一个点权（例如每个城市能收集到的物资），要求点权之和最大；
  3. 直接问有多少条最短路径。

2）Bellman-Ford 算法和 SPFA 算法

Dijkstra 算法可以很好地解决无负权图的最短路径问题，但如果出现了负权边，Dijkstra 算法就会失效。

为了解决这个问题，就需要使用 Bellman-Ford 算法（简称 BF 算法）。

现在考虑环，根据环中每条边的边权之和，可以将环分为零环、正环、负环，如下图所示。

image-20210309135136002

显然，

  • 图中的零环和正环不会影响最短路径的求解，因为零环和正环的存在不能使最短路径更短；
  • 如果图中有负环，且从源点可以到达，那么就会影响最短路径的求解。但如果负环无法从源点出发到达，那么就最短路径不会受到影响。

与 Dijkstra 算法相同，Bellman-Ford 算法设置一个数组d，用来存放从源点到达各个顶点的最短距离。同时 Bellman-Ford 算法返回一个bool值：如果其中存在从源点可达的负环，那么函数将返回 false。

【基本思想】

Bellman-Ford 算法的主要思路如下：

  • 需要对图中的边进行 V - 1 轮操作，每轮都遍历图中的所有边。
  • 对每条边 u→v，如果以u为中介点可以使 d[v] 更小，即 d[u] + length[u->v] < d[v] ，就用 d[u] + length[u->v] 更新 d[v]。

可以看出，Bellman-Ford 算法的时间复杂度为 $O(VE)$ 。

关于Bellman-Ford 算法的正确性：

  • 如果把源点s作为一棵树的根结点，那么其他结点按照最短路径的结点顺序连接，就会生成一棵最短路径树。

  • 显然，在最短路径树中，从源点s到达其余各顶点的路径就是原图中对应的最短路径。且一旦原图和源点确定，最短路径树也就确定了。此外，由于最短路径上的顶点不超过V个，因此最短路径树的层数一定不会超过V。

那么为什么要执行 V-1轮呢？

  • 由于初始状态下 d[s] 为0，且之后不会再改变（即最短路径树中第一层结点的d值被确定）；
  • 通过第一轮操作后，最短路径树中的第二层顶点（从源点s能够直达的点）的d值也会被确定下来；然后通过第二轮操作，第三层的值也会被确定下来，…，以此类推；
  • 由于最短路径树的层数不超过V层，因此Bellman-Ford算法的松弛操作不会超过V-1轮。

【伪代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(i = 0; i < n - 1; i++) {	// 执行V-1轮
    for(each edge u->v) {		// 每轮操作都遍历所有边
        if(d[u] + length[u->v] < d[v]) {	// 以u为中介点可以使d[v]更小
            d[v] = d[u] + length[u->v];		// 松弛操作
        }
    }
}
// 如果图中没有从源点可达的负环，那么d中的所有值都应当已经达到最优。
for(each edge u->v) {		// 对每条边进行判断
    if(d[u] + length[u->v] < d[v]) {	// 如果仍然可以被松弛
        return false;		// 说明图中有从源点可达的负环
    }
}
return true

【邻接表版】

由于 Bellman-Ford 算法需要遍历所有边，显然使用邻接表会比较方便，如果使用邻接矩阵，则时间复杂度会上升到 $O(V^3)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Node {
    int v, dis;		// v为邻接边的目标顶点，dis为邻接边的边权
}
vector<Node> Adj[MAXN];	// 图G的邻接表
int n;
int d[MAXN];

bool Bellman(int s) {
    /* 初始化 */
    fill(d, d + MAXN, INF);		// 将整个d数组赋为 F
    d[s] = 0;		// 起点s到达自身的距离为0
    // 以下为求解数组d的部分
    for(int i = 0; i < n - 1; i++) {	// 执行n-1轮操作
        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[i] + 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 fasle;	// 说明图中有从源点可达的负环
            }
        }
    }
    return true;	// 数组d的所有值都已经达到最优
}

【优化：SPFA算法】

Bellman-Ford 算法的每轮操作都需要遍历所有边，显然这其中会有大量无意义的操作，严重影响了算法的性能。于是注意到：

  • **只有当某个顶点 u 的 d[u] 值改变时，从它出发的边的邻接点 v 的 d[v] 值才有可能被改变 **。

由此可以进行一个优化：

  1. 建立一个队列，每次将队首顶点 u 取出，然后对从u出发的所有边 u→v 进行松弛操作，也就是判断 d[u] + length[u->v] < d[v] 是否成立；如果成立，更新 d[v] ，此时如果 v 不在队列中，就把 v 加入队列。
  2. 重复这样的操作直到队列为空（说明图中没有从源点可达的负环），或是某个顶点的入队次数超过 V-1（说明图中存在从源点的可达的负环）。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
queue<int> q;
q.push(s);
while(!q.empty()) {
    取出队首元素u;
    for(u的所有邻接边u->v) {
        if(d[u] + dis < d[v]) {	// 松弛操作
            d[v] = d[u] + dis;
            if(!inq[v]) {	// v不在队列中
                v入队;
                if(v入队次数大于n-1) {
                    return false	// 说明有可达负环
                }
            }
        }
    } 
}

这种优化后的算法被称为 SPFA（Shortest Path Faster Algorithm），它的期望时间复杂度是 $O(kE)$ ，且在很多情况下 k 不会超过2，因此十分高效。但如果图中存在从源点可达的负环，传统 SPFA 的时间复杂度就会退化成 $O(VE)$ 。

理解 SPFA 的关键是理解它是如何从 Bellman-Ford算法优化得来的。

邻接表版的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<Node> Adj[MAXN];
int n, d[MAXN], num[MAXN];
bool inq[MAXN];		// 顶点是否在队列中

bool SPFA(int s) {
    // 初始化部分
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d+MAXN, INF);
    // 源点入队部分
    queue<int> q;
    q.push(s);	
    inq[s] = true;	//源点已入队
    num[s]++;		//源点入队次数加1
    d[s] = 0;		//源点的d值为0
    // 主体部分
    while(!q.empty()) {
        int u = q.front();	// 队首顶点编号为u
        q.pop(u);
        inq[u] = false;		// 设置u不在队列中
        // 遍历u的所有邻接边v
        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;
                if(!inq[v]) {	// v不在队列中
                    q.push(v);
                    inq[v] = true;
                    num[v]++;
                    if(num[v] >= n)	return false;	// 有可达负环
                }
            }
        }
    }
    return true;	// 无可达负环
}

SPFA 十分灵活，其内部写法可以根据具体场景的不同进行调整，例如把上面的FIFO队列替换成优先队列（priority_queue），以加快速度。除此之外，上面的代码是BFS版本，如果将队列替换成栈，则可以实现DFS版本的SPFA，对判环有奇效。

3）Floyd算法

Floyd 算法（弗洛伊德）用来解决全源最短路径问题，即对给定的图 $G(V, E)$，求任意两点u，v之间的最短路径长度，时间复杂度是 $O(n^3)$ 。

Floyd 算法基于这样一个事实：

  • 如果存在顶点k，使得以k作为中介点时，顶点i和顶点j的当前最短距离缩短，则使用顶点k作为i和j的中介点。

    即当 $dis[i][k] + dis[k][j] < dis[i][j]$ 时，令 $dis[i][j] = dis[i][k] + dis[k][j]$。

由此，Floyd算法的流程如下：

1
2
3
4
枚举顶点 k in [1, n]
    以顶点k作为中介点，枚举所有顶点对i和j
    	如果 dis[i][k] + dis[k][j] < dis[i][j] 成立
    		令 dis[i][j] = dis[i][k] + dis[k][j]

可以看到，Floyd算法的思想异常简洁，代码如下：

1
2
3
4
5
6
7
8
9
10
11
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] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

对于 Floyd 算法来说，需要注意的是：

  • 不能将最外层的k循环放到内层，这会导致最后结果出错。
  • 使用与 Dij 同样的 $path$ 输出的最短路径是结果不正确的，因为 k 只是保证了 i 经过 k 到达 j 路径最短，无法保证能从k直接到j。

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行 V 次Dijkstra算法。

5. 最小生成树

最小生成树（Minimum Spanning Tree，MST）是在一个给定的无向图 G(V, E) 中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有边都是来自图G中的边，并且满足整棵树的边权之和最小。

最小生成树有3个性质：

  1. 最小生成树是树，因此其边数等于顶点数减1，且树内一定不会有环；
  2. 对给定的图 G(V, E)，其最小生成树可以不唯一，但其边权之和一定是唯一的；
  3. 由于最小生成树是在无向图上生成的，因此其根结点可以使这棵树上的任意一个节点。

求解最小生成树一般由两种算法，即 prim 算法与 kruskal 算法那，均采用贪心法的思想。

1）Prim 算法

prim 算法（也称普里姆算法）用于解决最小生成树问题。

【基本思想】

对图 G(V, E) 设置集合S，存放已被访问的顶点，然后重复下面的操作n次，直到集合S已包含所有顶点：

  1. 每次从集合 V-S 中选择 与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S，同时把这条离集合S最近的边加入最小生成树中；
  2. 之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。

可以发现，prim与Dijkstra的算法思想几乎完全相同，区别在于涉及最短距离时使用了「集合S」代替 Dijkstra中的「起点s」。

【具体实现】

  • 集合S的实现方法与Dij相同，即使用一个 vis[] 表示顶点是否被访问；
  • 使用 d[] 来存放顶点 $V_i$ 与集合S的最短距离。
1
2
3
4
5
6
7
8
9
10
11
12
Prim(G, d[]) {
    初始化;
    for(循环n次) {
        u = 使d[u]最小的还未被访问的顶点
        记u已被访问
        for(从u出发能到达地所有顶点v) {
            if(v未被访问 && 以u为中介点使得v与集合S的最短距离d[v]更优) {
                令v与集合S的最短距离d[v] = G[u][v];
            }
        }
    }
}

可以发现，prim与Dijkstra实际上是相同的思路，只不过是数组 d[] 的含义不同罢了。

【邻接矩阵版】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int n, G[MAXN][MAXN];
int d[MAXN];	// 顶点与集合S的最短距离
bool vis[MAXN] = {false};	// 标记数组，相当于集合S

int prim() {	// 默认0号为初始点，函数返回最小生成树的边权之和
	fill(d, d + MAXN, INF);	// fill函数将整个d数组赋为INF
    d[0] = 0;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int u = -1, MIN = INF;	// u使d[u]最小，MIN存放该最小的d[u]
        for(int j = 0; j < n; j++) {
            if(vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        // 若找不到小于INF的d[u]，则剩下的顶点和集合S不连通
        if(u == 1)	return -1;
        vis[u] = true;	// 标记u为已访问过
        ans += d[u];	// 将与集合S举例最小的边加入最小生成树
        for(int v = 0; v < n; v++) {
            // v未访问 && 以u为中介可以使v离集合S更近
            if(vis[v] == false && G[u][v] < d[v]) {
                d[v] = G[u][v];
            }
        }
    }
    return ans;	// 返回最小生成树的边权之和
}

和 Dijkstra 算法一样，使用这种写法的时间复杂度为 $O(V^2)$ 。

2）Kruskal 算法

kruskal 算法（也称为克鲁斯卡尔算法），采用了边贪心的策略，其思想极其简洁，理解难度比prim要低很多。

【基本思想】

在初始状态时隐去图中的所有边，这样图中每个顶点都自成一个连通块。之后执行下面的步骤：

  1. 对所有边按边权从小到大排序；
  2. 按边权从小到大测试所有边，如果当前测试边所连接的两个顶点不在同一个连通块中，则把这条测试边加入当前最小生成树中；否则将边舍弃。
  3. 重复步骤2，直到最小生成树中的边数等于总顶点数减1或是测试完所有边时结束。如果结束时最小生成树的边数小于总顶点数减1，说明该图不连通。

因此，kruskal 算法的思想简单来说就是：每次选择图中边权最小的边，如果边两端的顶点在不同的连通块中，就把这条边加入最小生成树中。

【伪代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
int kruskal() {
    令最小生成树的边权之和为ans、最小生成树的当前变数为Num_Edge;
    将所有边按边权从小到大排序;
    for(从小到大枚举所有边) {
        if(当前测试边的两个端点在不同的连通块中) {
            将该测试边加入最小生成树中;
            ans += 测试边的边权;
            最小生成树的当前边数Num_Edge加1;
            当边数Num_Edge等于顶点数减1时结束循环;
        }
    }
    return ans;
}

在这个伪代码里有两个细节似乎不太直观，即：

  1. 如何判断测试边的两个端点是否在不同的连通块中。
  2. 如何将测试边加入最小生成树中。

事实上，可以换一个角度来想。如果把每个连通块当作一个集合，那么就可以把问题转换为判断两个端点是否在同一个集合中，而这个问题在前面讨论过——对，就是并查集。

并查集可以通过查询两个结点所在集合的根结点是否相同来判断它们是否在同一个集合，而合并功能恰好可以把上面提到的第二个细节解决，即只要把测试边的两个端点所在集合合并，就能达到将边加入最小生成树的效果。

【具体实现】

于是可以根据上面的解释，把 kruskal 算法的代码写出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct edge {
    int u, v;	// 边的两个端点编号
    int cost;	// 边权
}E[MAXE];		// 最多有MAXE条边

bool cmp(edge a, edge b) {
    return a.cost < b.cost;
}

int father[N];	// 并查集数组
int findFather(int x) {		// 并查集查询函数
    while(x != father[x]) {
        x = father[x];
    }
    return x;
}

// kruskal函数返回最小生成树的边权之和，n为顶点个数，m为图的边数
int kruskal(int n, int m) {
    int ans = 0, numEdge = 0;
    for(int i = 1; i <= n; i++) {	// 假设顶点范围是[1,n]
    	father[i] = i;		// 并查集初始化
    }
    sort(E, E + m, cmp);	// 所有边按边权从小到大排序
    
    for(int i = 0; i < n; i++) {	// 从小到大枚举所有边
        edge e = E[i];
        int faU = findFather(e.u);
        int faV = findFather(e.v);
        if(faU != faV) {			// 如果两个
            father[faU] = faV;
            ans += e.cost;
            numEdge++;
            if(numEdge == n-1)	break;
        }
    }
    return ans;
}

可以看到，kruskal 算法的时间复杂度主要来源于对边进行排序，因此其时间复杂度是 $O(ElogE)$。显然，kruskal 算法适合顶点数较多、边数较少的情况。

于是，可以根据实际情况选择合适的算法：

  • 如果是稠密图（边多），则用 prim 算法；如果是稀疏图（边少），则用 kruskal 算法。

6. 拓扑排序

  • 如果一个有向图的任意顶点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图（Directed Acyclic Graph, DAG）。

  • 拓扑排序是将有向无环图 G 的所有顶点排成一个线性序列，使得对图 G 中的任意两个顶点u、v，如果存在边 u->v，那么在序列中u一定在v前面。这个序列又被称为拓扑序列。

【算法步骤】

  1. 定义一个队列 Q，并把所有入度为0的结点加入队列；
  2. 取队首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列；
  3. 反复执行操作2，直到队列为空。如果队空时入过队的结点数目恰好为N，说明拓扑排序成功，图G为有向无环图；否则，失败，图G中有环。

可使用邻接表实现拓扑排序，并用数组 inDegree[MAXN] 来计入结点的入度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> G[MAXN];	// 邻接表
int n, m, inDegree[MAXN];	// 顶点数、入度
// 拓扑排序
bool topologicalSort() {
	int num = 0;	// 记录加入拓扑排序的顶点数
	queue<int> q;
	// 初始化，将所有入度为0的结点入队
	for(int i = 0; i < n; i++) {
		if(inDegree[i] == 0) {
			q.push(i);
		}
	}
	// 主过程
	while(!q.empty()) {
		int u = q.front();		// 取队首顶点u
		printf("%d", u);		// 输出顶点u
		q.pop();
		for(int i = 0; i < G[u].size(); i++) {	// 遍历从u出发的所有边
			int v = G[u][i];	// u的后继结点v
			inDegree[v]--;
			if(inDegree[v] == 0) {	// 如果顶点v的入度减为0，则入队
				q.push(v);
			}
		}
		G[u].clear();	// 清空顶点u的所有出边（如无必要可不写）
		num++;
	}
	if(num == n)	return true;
	else	return false;
}

拓扑排序一个很重要的应用就是判断一个给定的图是否是有向无环图（DAG）。

7. 关键路径

1）AOV网和AOE网

  • 顶点活动（Activity On Vertex，AOV）网是指用顶点表示活动，而用边集表示活动间优先关系的有向图。

    • 如下图，顶点表示各项课程，也就是“活动”。

    • 有向边表示活动的先导关系，也就是“活动的优先关系”。显然，图中不应当存在有向环，否则会让优先关系出现逻辑错误。

      image-20210309213000149

  • 边活动（Activity On Edge，AOE）网是指用带权的边集表示活动，而用顶点表示事件的有向图，其中边权表示完成活动需要的时间。

    • 如下图，边 $a_1-a_6$ 表示需要学习的课程，也就是 “活动”，边权表示需要学习的时间。
    • 顶点 $V_1-V_6$ 表示到此刻为止，前面的课程已经学完，可以开始学习后面的课程了。显然”事件”仅代表一个中介状态。
    image-20210309212744080

AOE网是基于工程提出的概念，需要着重解决两个问题：

  1. 工程起始到终止至少需要多少时间；
  2. 哪些路径上的活动是影响整个工程的关键。

AOE网中的最长路径被称为关键路径（强调：关键路径就是AOE网的最长路径），而把关键路径上的活动称为关键活动。

2）最长路径

前面详细介绍过求解最短路径的三种算法，这里再简单介绍下如何求解最长路径。

对一个没有正环的图（指从源点可达的正环，下同），如果需要求最长路径长度，则可以把所有边的边权乘以-1，令其变为相反数，然后使用 Bellman-Ford 算法或 SPFA 算法求最短路径长度，将所得结果取反即可。

注意∶此处不能使用 Dijkstra 算法，原因是 Dijksta算法不能处理负边权的情况，即便原图的边权均为正，乘以-1 之后也会出现负权。

显然，如果图中有正环，那么最长路径是不存在的。

但是，如果需要求最长简单路径（也就是每个顶点最多只经过一次的路径），那么虽然最长简单路径本身存在，却没有办法通过 Bellman-Ford 等算法来求解，原因是最长路径问题是 NP-Hard 问题（也就是没有多项式时间复杂度算法的问题）。

3）关键路径

由于关键路径是有向无环图（DAG）中的最长路径，因此求解关键路径实际上就是求解DAG中的最长路径。

  • 由于关键活动是那些不允许拖延的活动，因此这些活动的最早开始时间必须等于最迟开始时间。

故可以设置数组 $e$ 和 $l$ ，其中 $e[r]$ 和 $l[r]$ 分别表示活动 $a_r$ 的最早开始时间和最迟开始时间，从而可以通过判断 e[r] == l[r] 是否成立来确定活动 r 是否是关键活动。

那么问题便转化为了「如何求解数组 $e$ 和 $l$ 」。

image-20210310091937996
  • 如上图，注意到顶点作为事件（一个中介状态），也有拖延的可能，因此会存在最早发生时间和最迟发生时间。其中，
    • 事件的最早发生时间可以理解成就活动的最早结束时间；
    • 事件的最迟发生时间可以理解成新活动的最迟开始时间；

故可以设置数组 $ve$ 和 $vl$ ，其中 $ve[i]$ 和 $vl[i]$ 分别表示事件 $i$ 的最早发生时间和最迟发生时间。

  1. 对于活动 $a_r$ 来说，只要在事件 $V_i$ 最早发生时马上开始，就可以使得活动 $a_r$ 的开始时间最早，因此 $e[r] = ve[i]$ ；
  2. 同样对于活动 $a_r$ ，它最迟必须在事件 $V_j$ 最迟发生时结束，即有 $l[r] + length[r] = vl[j]$ ，这样就得到了活动 $a_r$ 的最迟开始时间，$l[r] = vl[j] - length[r]$ 。

这样问题便进一步转化为了「如何求解数组 $ve$ 和 $vl$ 」。

（1）求解 ve

如下图所示，有 k 个事件 $V_{i1} - V_{ik}$ 通过相应的活动 $a_{r1} - a_{rk}$ 到达事件 $V_j$ ，活动的边权为 $length[r1] - length[rk]$ 。

image-20210310094842864

对于当前事件 $V_j$ ，只有在所有到达 $V_j$ 的活动都完成之后，$V_j$ 才能被 “激活”。

假设已经计算好了所有前驱事件 $V_{i1} - V_{ik}$ 的最早发生时间 $ve[i1] - ve[ik]$ ，那么事件 $V_j$ 的最早发生时间就是 $max(ve[ip] + length[rp])$ ，数学描述如下：

image-20210310095629347

于是我们知道，想要获得 $ve[j]$ 的值，必须保证 $ve[i1] - ve[ik]$ 都已得到，即在访问某个结点时要保证它的前驱结点都已经访问完毕。

显然，使用拓扑排序就可以办得到：

  • 当按照拓扑序列计算 $ve$ 数组时，总是能保证在计算 $ve[j]$ 的时候 $ve[i1] - ve[ik]$ 都已经得到。

但这时又出现了「新的问题」：

  • 通过前驱结点去寻找所有后继结点很容易，但是通过后继结点 $V_j$ 去寻找它的前驱结点 $V_{i1} - V_{ik}$ 似乎没有那么直观。

一个比较好的办法是：

  • 在拓扑排序访问到某个结点 $V_i$ 时，不是让它去找前驱结点来更新 $ve[i]$ ，而是使用 $ve[i]$ 去更新其所有后继结点的 $ve$ 值。

通过这个方法，可以让拓扑排序访问到 $V_j$ 的时候，$V_{i1} - V_{ik}$一定都已经用来更新过$ve[j]$ ，此时的 $ve[j]$ 便是正确值，就可以用它去更新 $V_j$ 的所有后继结点的 $ve$ 值。

这部分的代码下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
stack<int> topOrder;	// 拓扑序列
// 拓扑排序，顺便求ve数组
bool topologicalSort() {
    queue<int> q;
    for(int i = 0; i < n; i++) {
        if(inDegree[i] == 0) {
            q.push(i);
        }
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        topOrder.push(u);	// 将u加入拓扑序列
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v;	// 获得u的第i号后继结点v
            inDegree[v]--;
            if(inDegree[v] == 0) {
                q.push(v);
            }
            // 用ve[u]来更新u的所有后继结点v
            if(ve[u] + G[u][i].w > ve[v]) {
                ve[v] = ve[u] + G[u][i].w;
            }
        }
    }
    if(topOder.size() == n)	return true;
    esle 	return false;
}
（2）求解 vl

如下图所示，从事件 $V_j$ 出发通过相应的活动 $a_{r1} - a_{rk}$ 可以到达 k 个事件 $V_{i1} - V_{ik}$ ，活动的边权为 $length[r1] - length[rk]$ 。

image-20210310101606113

对于当前事件 $V_i$ ，必须保证 $V_{j1} - V_{jk}$ 的最迟发生时间 $vl[j1] - vl[jk]$ 能被满足 。

假设已经计算好了所有后继事件 $V_{j1} - V_{jk}$ 的最迟发生时间 $vl[j1] - vl[jk]$ ，那么事件 $V_j$ 的最迟发生时间就是 $min(vl[jp] - length[rp])$ ，数学描述如下：

image-20210310102600515

和 $ve$ 数组类似，想要获得 $vl[i]$ 的值，必须保证 $vl[j1] - vl[jk]$ 都已得到，即在访问某个结点时要保证它的后继结点都已经访问完毕，这个要求与 $ve$ 正好相反，而这个可以通过逆拓扑序列来实现。

实际上，我们上面在求解 $ve$ 时使用栈来存储拓扑序列，那么只需要按顺序出栈即可得到逆拓扑序列。

这部分的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fill(vl, vl + n, ve[n-1]);	// vl数组初始化，初始值为终点的ve值

// 直接使用topOrder的出栈序列，求解vl数组
while(!topOrder.empty()) {
    int u = topOrder.top();	// 栈顶元素为u
    topOrder.pop();
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i].v;	// u的后继结点v
        // 用u的所有后继结点v的vl值来更新vl[u]
        if(vl[v] - G[u][i].w < vl[u]) {
            vl[u] = vl[v] - G[u][i].w;
        }
    }
}
（3）求解关键活动

下面给出上面过程的步骤总结，即 “先求点，再夹边” ：

image-20210310104005527

主体部分代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//关键路径，不是有向无环图返回-1.否则返回关键路径长度
int CriticalPath() {
    memset(ve, 0, sizeof(ve));	// ve数组初始化
    if(topologicalSort() == false) {
        return -1;		// 不是有向无环图返回-1
    }
    fill(vl, vl + n, ve[n - 1]);	// vl数组初始化，初始值为汇点的ve值
    
    // 直接使用topOrder的出栈序列，求解vl数组
    while(!topOrder.empty()) {
        int u = topOrder.top();	// 栈顶元素为u
        topOrder.pop();
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v;	// u的后继结点v
            // 用u的所有后继结点v的vl值来更新vl[u]
            if(vl[v] - G[u][i].w < vl[u]) {
                vl[u] = vl[v] - G[u][i].w;
            }
        }
    }
    
    // 遍历邻接表的所有边，计算活动的最早开始时间e和最迟开始时间l
    for(int u = 0; u < n; u++) {
        for(int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v, w = G[u][i].w;
            // 活动的最早开始时间e和最迟开始时间l
            int e = ve[u], l = vl[v] - w;
            // 如果 e==l，说明活动u->v是关键活动
            if(e == l) {
                printf("%d->%d", u, v);		// 输出关键活动
            }
        }
    }
    return ve[n - 1];	// 返回关键路径长度
}

  • 如果事先不知道汇点编号，取 $ve$ 数组的最大值即可。原因在于，$ve$ 的含义是事件的最早开始时间，因此所有事件中 ve 最大的一定是最后一个（或多个）事件，也就是汇点。

  • 如果要完整输出所有关键路径，就需要把关键活动存下来，可以用新建一个邻接表来存储，最后再DFS一下获取所有关键路径。