第二章 初出茅庐——初级篇：数据结构与图论

本章涉及的两个主题都与结构化有着莫大联系。

加工并存储数据的数据结构

作者给出的定义非常贴切：
数据结构是存储数据的方式，按照不同的方式存储数据，可以对数据做不同的高效操作。
下面按照二叉搜索树、满二叉堆和并查集的顺序对各结构和相关习题进行介绍，由于我数据结构掌握地相对好一些，就不做较为初级的科普了

二叉搜索树

“二叉树”是大学课程中继“链表”后会学习的第二个数据结构，它和链表都是一类递归的结构，即节点本身包含节点的指针：

struct node {
	int val;
	node *lch, *rch;
};

另外二叉树与图结构中的树不一样，它有利于高效地进行查找；为了防止随着特殊数据的插入导致结构“链化”，查找效率降低，在此基础上还衍生出了各类自平衡二叉树结构：红黑树、Splay树、Treap树和替罪羊树等等；这些结构能通过旋转或者其他骚操作让二叉树的查找插入删除维持在\(O(logn)\)的复杂度内

书中给出的就是普通二叉树实现一个无重复元素的集合的例子，重点放在insert、find和remove操作的实现上；

1. 查找操作：从根节点开始对比当前节点的值\(val\)和要查找的值\(x\)，\(x < val\)时向当前节点的\(lch\)查找，\(x > val\)时向当前节点的\(rch\)查找；可用循环或递归实现，重复以上操作直到遇到一个节点的\(val = x\)，或转移到一个\(NULL\)为止；
2. 插入操作：与查找操作类似，只不过我们需要额外维护当前位置的父节点，在找到\(x\)在树中所处的位置(一个不存在的虚拟节点)后，新建一个节点存入值\(x\)，并在回溯的时候添加到其父节点上；
3. 删除操作：删除的前提是\(x\)存在，因此删除操作包含了查找操作；当把对应位置的节点\(p\)删除后，根据剩下结构需要分类讨论：1)如果\(p\)没有儿子(即\(p\)是个叶子结点)则直接返回；2)如果\(p\)只有一个儿子，则把这个儿子提到\(p\)的位置；3)如果\(p\)有两个儿子，则剩下三部分，我们需要找到一个节点\(o\)满足大于左子树所有节点的值，小于右子树所有节点的值；这个值只有两个，分别是左子树的最大值和右子树的最小值，这两个值对应的一定是叶子节点，因此摘除后不需要另考虑连接的逻辑，将这个节点提到对应p的位置即可；

bool find(node *p, int x) {
	if(p == NULL) return false;
	else if(x == p->val) return true;
	else if(x < p->val) return find(p->lch, x);
	else return find(p->rch, x);
}

node* insert(node *p, int x) {
	if(p == NULL) {
		node *q = new node;
		q->val = x;
		q->lch = q->rch = NULL;
		return q;
	}
	**if(p->val == x) return p;**
	else if(x < p->val) p->lch = insert(p->lch, x);
	else p->rch = insert(p->rch, x);
	return p;
}

node* remove(node *p, int x) {
	if(p == NULL) return NULL;
	else if(x < p->val) p->lch = remove(p->lch, x);
	else if(x > p->val) p->rch = remove(p->rch, x);
	else if(p->lch == NULL) {
		node *q = p->rch;
		delete p;
		return q;
	} else if(p->lch->rch == NULL) {
		node *q = p->lch;
		q->rch = p->rch;
		delete p;
		return q;
	} else {
		node *q;
		for(q = p->lch; q->rch->rch != NULL; q = q->rch);
		node *r = q->rch;
		q->rch = r->lch;
		r->lch = p->lch;
		r->rch = p->rch;
		delete p;
		return r;
	}
	return p;
}

这种写法在remove的时候就要root = remove(root)了，insert同理
这是C++中的写法，如果将insert中加粗的那行去掉就可以支持插入重复元素了：

node* insert(node *p, int x) {
	if(p == NULL) {
		node *q = new node;
		q->val = x;
		q->lch = q->rch = NULL;
		return q;
	}
	if(x < p->val) p->lch = insert(p->lch, x);
	else p->rch = insert(p->rch, x);
	return p;
}

如果按照\((2, 2, 3, 2)\)的顺序插入元素，会有如下结构：
\(p.val = 2, p.rch.val = 2, p.rch.rch.val = 3, p.rch.rch.lch.val = 2\)
2这个值在树结构上不连续，但是没有关系，每个节点仍然满足\(p.lch.val \leq p.val \leq p.rch.val\)，可以发现这个条件在插入还是删除过程中总成立，因此中序遍历一定会生成一个单调非增序列(任何一个节点左边不会存在比它大的值，右边不会存在比它小的值，所以序列单调非增)，故这棵树还是有序的

猜测C++当中的也是通过相同的方法支持重复元素，只不过是基于平衡二叉树实现的

满二叉堆和优先队列

满二叉堆可以看作一个特殊的二叉树，只不过这个二叉树的节点是从上到下、从左到右紧凑排列的，这样紧凑的结构就可以通过数组或vector来实现；

我们先来分析下满二叉树的节点id满足什么特性：

1. 第\(k\)层有\(2^{k-1}\)个节点
2. 前\(k\)层有\(2^k-1\)个节点
3. (根节点为1)第\(k\)层的第\(x\)个节点的编号为\(2^{k-1}-1+x\)，它对应在第\(k+1\)层的两个子节点编号分别为\(2^k-1+2x-1\)和\(2^k-1+2x\)，故节点\(x\)的两个子节点编号分别为\(2x\)和\(2x+1\)
4. (根节点为0)第\(k\)层的第\(x\)个节点的编号为\(2^{k-1}-2+x\)，它对应在第\(k+1\)层的两个子节点编号分别为\(2^k-3+2x\)和\(2^k-2+2x\)，故节点\(x\)的两个子节点编号分别为\(2x+1\)和\(2x+2\)
   id的选择推荐用3.当中的方式，这样任意节点\(x\)的父节点id为\(x/2\)

二叉堆的性质：
堆的结构是满二叉树的结构，但必须满足每个节点的值都\(\leq\)其两个子节点的值(如果存在)，这种堆叫做小根堆；大根堆要求\(\geq\)；
二叉堆的这个性质，会保证从根节点到任意叶子结点的路径都存在\(\leq, \leq, \leq ...\)的关系，因此根节点的值为全局最小值；
堆需要支持push和pop两类操作，并且操作前后上述性质保持不变

1. push：将新值追加到数组末尾，沿着父节点向根爬，当$val(x) < \(val(x.par)\)时交换它和父节点的值，直到条件不满足或已到达根节点为止；
2. pop：将数组第一个元素弹出，并将末尾节点(数组最后一个)的值复制到根节点，删除末尾节点；随后由根节点开始，比较当前节点与其两个儿子(如果存在)的值，将三者最小值交换到当前位置，直到自己是三者最小值或到达叶子结点为止；

int heap[MAX_N], sz = 0;
void push(int x) {
	heap[++sz] = x;
	int o = sz;
	while(o > 1) {
		if(heap[o] < heap[o/2]) swap(heap[o], heap[o/2]);
		else break;
	}
}

int pop() {
	int ret = heap[1];
	heap[1] = heap[sz--];
	int o = 1;
	while(o*2 <= sz) {
		int x = o*2, y = o*2+1;
		if(y <= sz && heap[y] < heap[x]) x = y;
		if(heap[x] >= heap[o]) break;
		swap(heap[x], heap[o]);
		o = x;
	}
	return ret;
}

书中用的是以0为根节点，并且避免使用了swap函数，常数更小一些；
在C++的STL中优先队列结构就是一个堆实现，因此大多情况下不需要手写堆，另外支持自定义比较函数，但需要注意的是operator >在优先队列看来是优先级高，堆顶保存的是优先级最高的元素

然后是两道应用题目：

1. Expedition(POJ 2431)
   有个卡车要走长度为\(L\)的路程，启程时有\(P\)单位的汽油，每走1单位的距离消耗1单位汽油，路上有\(N\)个加油站，分别位于距离起点的\(A_i\)处，最多可以给卡车加\(B_i\)单位汽油，问卡车如果能到达终点，最少需要在多少个加油站加油，无法到达输出-1；其中\(1 \leq L, P \leq 1000000, 1 \leq N \leq 10000,1 \leq A_i < L, 1 \leq B_i \leq 100\)
   考虑选择的第一个加油站，应该是走完\(P\)之前遇到的加油站中\(B_i\)最大的那个，然后可以继续向前走\(B_i\)，又可能会碰到新的加油站，每次没油的时候可以选择遇到过的所有加油站中\(B_i\)最大的那个来加油，用作者话说“在到达加油站\(i\)时，就获得了一次在之后任何时候都可以加\(B_i单位汽油的权利\)”；因此，我们需要一个优先队列来维护当前遇到过的所有加油站的最大\(B_i\)；总时间复杂度\(O(NlogN)\)
2. Fence Repair(PKU 3253)
   那道类似哈夫曼树的问题，解法是每次选择全局两个最小的短板拼接成一个较长的，然后问题规模\(n\)收敛到\(n-1\)，不停重复这个过程；
   所以可以使用优先队列维护全局最小值，每次pop两个最短的板子，把拼接后的push到队列中即可；总时间复杂度\(O(NlogN)\)

并查集

并查集是用来维护\(n\)个集合的合并和查询的数据结构，我们可以查询每个元素位于哪个集合，并且将不同的两个集合合并起来：
\(n\)个元素最开始属于各自的集合：

int par[maxn];
void init(int n) {
	for(int i = 1; i <= n; i++) par[i] = i;
}

其中最简单的路径压缩并查集的实现如下：

int findset(int x) {
	return par[x] = (x == par[x])? x: findset(par[x]);
}

我们沿着一条链递归地走到尽头，并最终把根节点的id赋值给每一个路径上的元素；路径上所有点都直接与根节点相连，高度均变为1；其他与这条链有连接的分支，对应的高度也都会减少；
合并的过程非常简单：

void unite(int x, int y) {
	x = findset(x);
	y = findset(y);
	par[y] = x; // x与y相等也没有关系
}

复杂度的部分很奇妙，找一个近似的角度去理解就好：假设我们路径压缩的时候是将路径上的所有节点合并成了同一个(事实上几乎等同于这个效果)，每次合并两个集合的时候涉及到2次findset和1次unite，unite时只会最多增加1条边，而每条边最多被访问1次就会消失(近似层面，事实上没有消失，只是换了个根，但是更扁平了)，假设一共涉及到\(n\)个集合的合并和查询，我们的总操作数就是\(O(n)\)级别的，因此均摊下来，单次操作是\(O(1)\)级别的

并查集的另外一种实现方式是在引入了节点高度int rank[maxn];的概念，并查集是一个树形结构，每次合并后应该让树的高度尽可能低；

int par[maxn];
int rank[maxn];
void init(int n) {
	for(int i = 1; i <= n; i++) {
		par[i] = i;
		rank[i] = 0;
	}
}
int findset(int x) {
	while(x != par[x]) x = par[x];
	return x;
}
void unite(int x, int y) {
	x = findset(x);
	y = findset(y);
	if(rank[x] < rank[y]) par[x] = y;
	else if(rank[x] > rank[y]) par[y] = x;
	else {
		par[y] = x;
		rank[x]++;
	}
}

从上述代码可以分析出：

1. 一个集合的rank实际上是集合根节点的rank，其余节点的rank不重要；
2. findset的复杂度为\(O(logn)\)，我们证明合并\(n\)个集合能得到的最高树高是\(O(logn)\)的：当两个集合的高度不同时，合并后不会产生更高的树；换句话说，我们想让树高每增加，必须合并两个相同高度的树才行；
   设\(S_k\)为生成高度为\(k\)的树需要用到的最少节点，有\(S_k = 2S_{k-1}, S_0 = 1\)，解递归式后得：\(S_k = 2^k\)
   因此\(n\)个节点能构成的最高树为\(O(logn)\)层；故findset和unite的复杂度为\(O(logn)\)

并查集有一道非常经典的题目叫：食物链(POJ 1182)
共有\(N\)只动物，每只动物都属于A, B, C其中一种，A吃B，B吃C，C吃A，现给出\(M\)条信息，分为两类：

• \(x\)和\(y\)属于同一类物种
• \(x\)吃\(y\)

如果某条信息与之前的条件有冲突则认为它是错误的，没有则认为是正确的(显然第一条信息永远是正确的)，问一共有多少条错误的信息

提供两种不同的解法：

1. 这道题我记不清是当初就没理解还是直接给秒了，再做的时候发现好难啊，而且作者的解法我也觉得不好理解。但好在还是想到原先的做法了：
   我们把已知的同一类物种维护成一个集合，并且对每个集合额外维护前后两个集合，分别代表当前集合可以吃掉的集合，和可以吃掉当前集合的集合，最开始每个动物的前后两个集合都是空集
   然后我们就会发现这两类操作实际上并没有什么区别，第一类是试图合并\((A_1, A_2, A_3)\)和\((B_1, B_2, B_3)\)，第二类是试图合并\((A_1, A_2, A_3)\)和\((B_3, B_1, B_2)\)，因为\(A_2\)既然吃\(B_2\)，说明\(A_2\)和\(B_1\)是同一类；考虑集合(\(x_1, x_2, x_3\))和(\(y_1, y_2, y_3\))可以合并的条件，只需要判断\(x_1\)不与\(y_2\)或\(y_3\)是一个集合即可；因为如果\(x_2=y_3\)，说明\((x_1, x_2, x_3)=(y_2, y_3, y_1)\)，一定有\(x_1=y_2\)；
2. 作者的方法是直接通过对条件建模：\(i-x\)表示“\(i属于种类x\)”，这样就有共计\(3n\)个条件；同一个集合当中的条件是同时成立的；不同集合中会存在一些条件互斥，例如\(i\)-\(A\), \(i\)-\(B\), \(i\)-\(C\)是互斥的；两个互斥的条件不能发生合并
   对于第一种操作，我们需要合并\(i\)-\(A\)和\(j\)-\(A\), \(i\)-\(B\)和\(j\)-\(B\), \(i\)-\(C\)和\(j\)-\(C\)，由于其中\(i\)-\(A\)和\(i\)-\(B\), \(i\)-\(C\)互斥，因此如果有\(i\)-\(A\)和\(j\)-\(B\)是同一个集合或\(i\)-\(A\)和\(j\)-\(C\)是同一个集合，则无法发生合并；
   例如\(i\)-\(A\)和\(j\)-\(B\)是同一个集合，由于互斥的3组条件总是同时发生合并，因此有\((i\)-\(A\), \(i\)-\(B\), \(i\)-\(C) = (j\)-\(B\), \(j\)-\(C\), \(j\)-\(A)\)，\(i\)-\(A\)与\(j\)-\(A\)合并等同于\(i\)-\(A\)与\(i\)-\(C\)合并，两个互斥的条件显然无法合并；
   对于第二种操作，需要合并的是\((i\)-\(A\), \(i\)-\(B\), \(i\)-\(C) = (j\)-\(B\), \(j\)-\(C\), \(j\)-\(A)\)，分析方法与上述相同；
   作者并没有提到，互斥才是理解条件冲突的关键，起初构造出了\(3n\)个条件，包含了\(3n\)对互斥关系，每次操作都要合并3个条件，只要不发生互斥就可以合并成功，反之则存在互斥冲突，对应一条错误的信息；

特别值得一提的时，并查集这种再简单不过的数据结构，却经常出现在高段位的题目当中，透过这道题目(可用并查集表示条件同时成立)可见一斑，尽管这种结构在低段位中出现的并不多，应该引起足够重视

它们其实都是“图”

接下来的内容就是图论中比较简单的部分了，除了基础概念外，只涉及到“最短路”和“最小生成树”两类算法；

图的相关概念和性质

图是由顶点(或叫“节点”)集合\(V\)(vertex)和边集合\(E\)(edge)构成的用来表达事物之间关系的结构，记为\(G=(V, E)\)；连接两个点\(u, v\)之间的边用\(e=(u, v)\)表示

图的类别

• 边没有指向性的图：无向图(例子：朋友关系图)
• 边具有指向性的图：有向图(例子：流程图、数值关系图-一种\(DAG\)：顶点代表数值，若\(A > B\)，则有一条\(A\)到\(B\)的有向边)
• 有些边有指向性，有些边没有指向性的图：混合图(和网络流有关)
• 边带有权值的图：带权图(最短路问题相关)

无向图术语

• 节点相邻：两个节点之间存在一条边
• 路径：相邻节点的序列
• 圈：起点和终点重合的路径
• 连通图：任意两点之间都有路径连接的图
• 度：顶点连接的边数
• 树：没有圈的连通图
• 森林：没有圈的非连通图
• 有根树：指定一个节点作为根的树(往往把根提到最上面，其他节点按照与根之间的距离逐层往下排，其他节点与根之间的边数为该节点的深度；相邻节点之间深度低的是深度高的父亲，也可以看作是给边加了方向)
• 无根树：没有指定根节点的树

1. 结论：一棵树的边数恰好是节点数-1
   证明：由定义，树是不带环的连通图；当\(n=1\)时，边树为0显然成立；当\(n>1\)时，由于不存在环，一定存在度为1的节点；找到度为1的节点并删除该节点和连边，剩余部分仍然为一个不带环的连通图；递归下去，当被删剩1个节点时，边数为0，共删去\(n-1\)个节点和\(n-1\)条边，这是图中的所有边，因此边数为\(n-1\)

2. 结论：边数等于节点数-1的连通图是一棵树
   证明：如果存在一个\(k \geq 1\)个节点构成的环(包括自环)，则环上一定有\(k\)条边；则其余\(n-k\)个节点要想与该换构成连通图，至少另需要\(n-k\)条边；因此共需要\(\geq n\)条边才能构成一个带环连通图，所以由\(n-1\)条边构成的连通图不带环，故该图是一棵树

有向图术语

• 前驱/后继：如果存在一条从\(i\)到\(j\)的有向边\(e=(i, j)\)，\(i\)为\(j\)的“前驱”，\(j\)为\(i\)的“后继”
• 出度：以节点\(v\)为起点的边的集合记作\(\delta_+(v)\)，\(|\delta_+(v)|\)为出度
• 入度：以节点\(v\)为终点的边的集合记作\(\delta_-(v)\)，\(|\delta_-(v)|\)为入度
• DAG：Directed Acyclic Graph，有向无环图。例如：如果\(n\)能够整除\(m\)，则从\(n\)向\(m\)连一条有向边，则这样的图为一个DAG(因为不存在大数指向小数的边，因此不会存在回环)
• 拓扑序：对于DAG，给节点\(i\)分配一个序号\(v_i\)，使得对任意有向边\(i\)到\(j\)都有\(v_i < v_j\)，这样的编号叫做拓扑序

1. 结论：有向带环图不存在拓扑序
   证明：设任意有向环上的节点编号为\(x_1, x_2, ..., x_k\)，显然不存在\(v_{x1} < v_{x2} < ... < v_{xk} < v_{x1}\)
2. 结论：有向无环图一定存在\(|\delta_-(i)| = 0\)(入度为0)的点\(i\)
   证明：挑选任意一个点\(i\)，如果该点满足\(|\delta_-(i)| = 0\)，则命题成立；否则沿着一条指向\(i\)的边走向它的前驱，由于不存在有向环，因此有限步后一定能到达一个\(|\delta_-(i)| = 0\)的点
3. 结论：DAG一定存在拓扑序
   证明：由于不存在环，我们找到点\(|\delta_-(i)| = 0\)(入度为0)的点\(i\)，可以发现将点\(i\)和所有\(\delta_+(i)\)删去，如果剩下的图还存在节点，则一定存在一个点满足入度为0，否则由结论2得该图的子图为带环图，因此原图为带环图；故剩下的图仍为DAG
   可以发现按照上述顺序不停地寻找\(|\delta_-(i)| = 0\)(入度为0)的点\(i\)，随后将点\(i\)和所有\(\delta_+(i)\)删去，找点的顺序就为一个拓扑序
   因此对任意节点，所有指向它的边的起点的序号都比它小(因为在处理该节点时所有指向它的节点都被删除掉了)，所有由它指向的其他点的序号都比它的序号大(因为在删除该届点前不会处理其他点)
4. 结论：如果将图中所有点按照拓扑序从小到大排列，则所有边都是从左指向右的(这样的编号方式使得一些DAG问题可以用DP解决，将图转换为了序列，并且状态的转移方向是一致的)
   证明：由定义显然成立

图的表示法

这部分比较基础，直接列一下重点

1. 表示图有3种方式：“邻接矩阵”、“邻接表”和“链式前向星”，其中“链式前向星”只有卡内存比较死的时候才使用；
2. “邻接矩阵”：开二维数组来存图，\(g[i][j]\)代表\(i\)连向\(j\)的边
3. “邻接表”：多用vector实现，作者提供了一种很优美的实现方法
4. “链式前向星”：实现稍微复杂一些，自己维护next节点，但速度快
5. 对于无权图来说，可以使用\(g[i][j] = 1\)代表存在\(e=(i, j)\)，用\(g[i][j] = 0\)代表不存在这样的边
6. 对于带权图来说，可以用\(g[i][j]\)代表\(i\)到\(j\)连边的权值，如果边不存在，可使用\(-1\)或者\(INF\)来代替，其中\(INF\)可以避免求最短路时的特判
7. 无向图总有\(g[i][j] = g[j][i]\)
8. 当输入包含重边和子环的时候，无权图可使用\(g[i][j]\)表示计数，带权图可使用“求最大/最小值”等方法等价转化；必须保存所有边的情况使用“邻接表”
9. “邻接矩阵”比“邻接表”多的一个功能是可以在\(O(1)\)判断是否有\(e=(i, j)\)

作者提供的两种“邻接表写法”：
第一种：

struct edge {int to, cost; };
vector G[MAX_V];

第二种：

struct vertex {
	vector<*vertex> edge;
	/*
	 * 定点的属性
	 */
};
int main() {
	int V, E;
	scanf("%d%d", &V, &E);
	for(int i = 0; i < E; i++) {
		int s, t; scanf("%d%d", &s, &t);
		G[s].push_back(&G[t]);
		// G[t].push_back(&G[s]);
	}
}

链式前向星的一种写法：

struct {int to, next, cost;} edge[MAX_E];
void addedge(int i, int j) {
	int x = eid++;
	int y = eid++;
	edge[x].to = j;
	edge[x].next = G[i];
	G[i] = x;
	edge[y].to = i;
	edge[y].next = G[j];
	G[j] = y;
}

这么做的好处是，设eid = 0;，有\(y = x \oplus 1\)

图的搜索

图的搜索有\(dfs\)和\(bfs\)两种。
其中\(bfs\)的过程是：

1. 选择一个节点，进入队列并标记
2. 从队列中取出头一个节点，将它周围没有被标记过的点塞入队列并标记
3. 重复2，直到队列为空

可以看到一个节点一定只进出队列一次，进队列的时候打标记，防止重复入队(比如同一层的2个节点连接同1个节点的情况)，出队列的时候处理该节点相关逻辑

其中\(dfs\)的过程是：

1. 从一个节点开始进入\(dfs\)函数并标记
2. 遍历相邻的所有未被标记的点，使其进入\(dfs\)并标记

可以发现每个节点只进入调用并且被标记一次，因此两种方法的时间复杂度均为\(O(V + E)\)

对于连通图(无向图术语)，一遍\(bfs\)或\(dfs\)可以访问到所有节点，并且每个节点只访问一次
证明非常容易，反证法即可：找一个没有被访问的节点\(i\)与被访问过的节点\(j\)相邻，则对\(bfs\)来说，\(j\)一定使\(i\)进队；队\(dfs\)来说，\(j\)一定会遍历到\(i\)

考虑一个二分图问题，给出一个无向图，能否存在一个染色方法使得所有黑点周围均为白点，所有白点周围均为黑点
这是一个图着色问题，二分图即“最小着色数”为2的图，一个图是二分图，意味着可以将这个图分为2个集合，集合内的点不存在连边，连边只会存在于集合之间
解决的方法\(bfs\)和\(dfs\)都可以，区别在于\(bfs\)是一圈黑一圈白地逐层染色；\(dfs\)则是一条链到底，链上黑白交错地染色，任意一个点发生冲突都意味着无法构成二分图
如果整个染色过程完好结束，就的到了一个合法的染色方案
特别对于\(dfs\)而言，实际上我们经历了对所有节点都满足周围是异色节点的判断，因为任意一个节点，进入这个节点意味着与前一个节点一定是异色的，而这个节点也一定经历了遍历相邻节点的过程，如果遍历到某个节点时，该节点没有被访问，则一定会赋予该节点异色节点；如果已经被访问，我们也都做了检测；所以结果一定合法

最短路

最短路算法是非常初级和基础的一类算法，耳熟能详的有SPFA、dijkstra和floyd共3类算法，书中介绍了Bellman-Ford算法、dijkstra+堆优化和floyd算法3种；
虽然常见，但是清楚地理解其原理、性质、局限性和实现细节并不是那么容易的，只停留在套板子层面上容易在应用时出错，并且不好应对其变形，所以好好总结是很有必要的

关于负环：

1. 无向图中只要存在负边就一定存在负环；
2. 有向图中判断存在负环有专门的方法，例如通过Bellman-Ford算法的循环计数，如果循环次数超过\(n-1\)，就代表存在负环

Bellman-Ford算法

Bellman-Ford算法是一类基础的单源最短路算法，其原理基于以下事实：
定义\(d[i]\)为起点\(s\)到节点\(i\)的最短路径长度，则有：
\(d[i] = min\{d[j] + cost(j, i) | e=(j, i) \in E\}\)
如果给定的是一个DAG，则我们可以按照拓扑序的顺序使用DP求出所有\(d[i]\)，因为序号大的节点只依赖序号比它小的节点，这构成了最优子结构的条件；即对于拓扑序\(i < j\)，我们一定是可以先确定\(d[i]\)，后确定\(d[j]\)的；
对于无向无环图就更简单了，转化成以\(s\)为根节点的有根树，通过树形DP来解决(能这么解决的依据是：不存在负边，这样最短路一定不包含重复路经)；

DP要求问题具备“最优子结构”性质，即先确定一部分状态的结果，再由这些状态去计算新的状态的结果；已经确定结果的状态后续是不能发生变化的，否则由他计算出来的状态可能都会是错的；显然DAG和树都满足“最优子结构”

问题出现在当图包含环的时候，考虑如下场景：
存在路径\(i \rightarrow j\)和路径\(j \rightarrow i\)不存在公共边，在这类情况下，不能通过DP来求解，因为计算\(d[i]\)需要(间接)用到\(d[j]\)，计算\(d[j]\)又(间接)需要\(d[i]\)，\(s \rightarrow i\)和\(s \rightarrow j\)这两个问题之间不存在包含关系；
(这里我联想到，通过“强连通缩点”来将图化作一个树，再结合树形DP的方法来解的题目，或许正是需要让不具备“最优子结构”的部分收敛成一个点)

因此Bellman-Ford算法不是DP，它最开始设\(dp[i] = INF, dp[s] = 0\)(\(INF\)方便使用\(min\)计算)，在不存在“负环”的情况下，通过最多\(V-1\)次“松弛”操作，求得所有点的最短路；

struct edge { int from, to, cost; };
edge es[MAX_E];

int d[MAX_V];
int V, E;

bool shortest_path(int s) {
	for(int i = 0; i < V; i++) d[i] = INF;
	d[s] = 0;
	for(int i = 0; i < V; i++) {
		for(int j = 0; j < E; j++) {
			edge e = es[j];
			if(d[e.from] != INF && d[e.from] + e.cost < d[e.to]) { // 这里必须有d[e.from] != INF，不然存在大量负边的时候可能引发从一个INF出发得到了一个看似合理的值
				d[e.to] = d[e.from] + e.cost;
				if(i == V-1) return false;
			}
		}
	}
	return true;
}

这里需要证明一个结论：当“松弛”操作执行超过\(V-1\)轮后，仍存在某节点\(i\)的最短路值\(d[i]\)得到更新，则说明图中包含源点可达的负环；否则，图中不包含源点可达的负环
实际上证明这个结论需要证明如下两个命题：

1. 如果不含(源点可达的)负环，则最多需要松弛\(V-1\)轮即可得到所有节点的最短路值
2. 如果包含(源点可达的)负环，则每次松弛都会存在节点得到更小的最短路值

下面证明这两个命题，对于“源点可达”这个条件，可以只考虑从源点出发能到达的点所构成的子图即可，其他无法到达的点及相关连边直接删掉；

关于第一个命题的证明：
对于源点能到达的任意点\(i\)的最短路径\(path(s, i)\)，路径值为\(d[i]\)，一定存在一个不包含重复节点的到\(i\)的路径\(path'(s, i)\)值为\(d'[i] = d[i]\)；
如果\(path(s, i)\)不包含重复节点则显然成立；否则包含环，由于环非负，因此去掉所有环后得到的路径\(d'[i] \leq d[i]\)，又由定义\(d[i]\)已为最小值，因此\(d'[i] = d[i]\)；
因此\(s\)可到达的任意点的最短路径值，都存在一个不包含重复节点即包含不超过\(V-1\)条边的路径，每次松弛至少能够沿着该路径更新到下一个节点的\(d[i]\)，因此最多执行\(V-1\)此即可求得任意节点的最短路径值

关于第二个命题的证明：
对于任意一个负环，我们任从一个节点\(i\)开始(假设这是负环上第一被更新的节点)，在没有外界输入的条件下，一定能够沿着负环更新一圈(因为其他点均有\(d[j] = INF\))，回到点\(i\)后会发现\(d[i]\)这个值更小了，因此再走一圈仍会使环上其他点更新为更小的值；
但是有可能从环外某点更新到环内某个点\(j\)，使得\(d[j] < INF\)，可以发现如果从\(d[i]\)更新到的\(d[j]\)更小则没有影响，如果外界输入更新的\(d[j]\)更小，则让\(j\)接过接力棒，从\(j\)沿着环更新即可；
严谨的证明如下：
即，由于负环可达，当负环上还存在\(d[i] = INF\)时，本轮松弛一定存在节点被更新；
考虑负环上所有节点均有\(d[i] < INF\)：
本轮“松弛”中，如果负环上的某个点会被外界更新，显然存在节点更新为更小值；
如果负环上的所有点都不会被外界更新，此时总能找到负环上的一个节点，从它出发沿着环能够更新下一个节点为更小值；否则设负环规模为\(k\)，环上节点不妨设为\(0\)到\(k-1\)，有\(d[0] + cost(0, 1) \geq d[1], d[1] + cost(1, 2) \geq d[2], ..., d[k-1] + cost(k-1, 0) \geq d[0]\)，由不等式有\(d[j] + \sum_{i=0}^k cost((j+i) \% k, (j+i+1) \% k)) \geq d[j+1] + \sum_{i=1}^k cost((j+i) \% k, (j+i+1) \% k)) \geq d[j]\)，因此\(\sum_{i=0}^k cost(i, (i+1) \% k)) \geq 0\)，与该环是一个负环矛盾

因此我们完整地证明了算法的正确性

刚才只关注了源点\(s\)能够到达的节点，这得益于删除了所有无法到达的节点及其连边，如果想到找到图中是否存在负环(比如并不是一个单源最短路问题)，也可以使用类似的方法进行判断，只不过我们要初始化\(\forall d[i] = 0\)；
证明类似上述过程，需要证明2个结论：

1. 如果不含负环，则最多需要松弛\(V-1\)轮即可得到所有节点的最短路值
2. 如果包含负环，则每次松弛都会存在节点得到更小的最短路值

这次没有源点了，实际上条件变为可以从任意节点出发；
对命题1，可以证明，对\(\forall i\)，能够使得\(d[i]\)取得最小值的节点数最少(避免对路径和为0的环的讨论)的路径，一定不包含重复节点；
对命题2，可以证明，对其中任意一个负环，在任何一轮松弛操作中，负环中至少会有一个节点的最短路径值会发生更新；因为在不会被环外节点更新的情况下，要想环上不发生任何更新，只能存在\(\sum_{i=0}^k cost(i, (i+1) \% k)) \geq 0\)，这与当前环是一个负环矛盾；
可以发现，上述证明并不需要保证\(\forall d[i] = 0\)，因此理论上只要运算过程中不发生溢出，\(d[i]\)的初始值设为什么值是无所谓的，只要最开始就允许从任何节点作为起点开始更新就好

关于负环的讨论还没有结束，通过“数形结合”的方法，可以了解到负环有一个有趣的性质：
长度为\(L\)的负环上一定可以找到一个点\(i\)，对\(\forall 1 \leq k \leq L\)，满足\(\sum_{j=0}^{k-1} cost((i+j) \% k, (i+j+1) \% k) < 0\)
注意这次讨论的是环边求和的值，跟最短路没有什么关系；我们可以任选环上一个点\(i\)做为起点，此时路径和为0，从这个点开始走一圈，每到达一个点求出当前的路径和，把这个图形沿着x轴绘制出来，横坐标代表点的序号，纵坐标为路径和的值(图1)；
走一圈回到的源点后，由于是负环，因此该点的值会在x轴下方
现在找到这个图形的最高点，如果有多个最高点就选取最右侧的那个，以这个点对应的节点\(j\)为起点，按照上述步骤重新绘制图形(图2)会发现，从\(j\)到达的所有其他节点的路径都\(< 0\)(整个图形相当于图1中以\(j\)为分界点的左半部分向下平移了\(\Delta\)后，向右移动了\(L\)个单位)

另一个需要注意的问题的数据范围，需要谨防数据溢出；对于求单源最短路及源点可到达的负环判定时，由于代码对\(INF\)做了特判，因此不会基于一个不可达的点进行更新，但需要注意任何由源点\(s\)可达节点的状态\(d[i]\)，必须在计算过程中\(< INF\)才行；
而对于图整体的负环判定，我们只需要保证在\(V-1\)轮内，任何运算结果不会出现溢出即可；

Dijkstra算法

Dijkstra是一种求单源最短路的贪心算法，它将节点分为已确定最短路的集和\(A\)和未确定最短路的集和\(B\)，每次从与\(A\)中节点相邻的\(B\)中节点中，挑选出距离源点距离最近的一个点，将其加入到\(A\)中；
最开始只有源点\(s \in A\)，其余节点均\(\in B\)

Dijkstra要求图中不包含负边，包含负边的时候算法显然是错的，因为可能从某个新确定最短路的节点连一条很大的负边回到一个早已确定最短路的节点，并且成功将其最短路更新到更小的一个值，这显然不满足“已确定最短路的集和”的定义

证明方法有两种：
第一种出自罗书当中，是一种很形象的几何口头证明：
由于不存在负边，可以将求解单源最短路的过程看作是现实中的塔米诺骨牌(边权为0意味着两个牌同时倒下)，距离源点最近的骨牌最先倒下，骨牌倒下的时间可以看作最短路的距离；这个过程与Dijkstra的计算过程是一摸一样的，因此从现实意义上Dijkstra的正确性显而易见；

第二种这里给出严格证明，命题为：
设\(A\)为最短路已确定的节点集和，在与\(A\)中节点相邻且\(\notin A\)的节点中，\(d[i]\)最小的节点\(i\)的最短路为\(d[i]\)，其中\(d[i] = min\{d[j] + cost(j, i) | j \in A, i \notin A\}\)(这么描述命题有点别扭，但可以尽可能严谨)
假设存在\(path(s, i) = (p_0, p_1, p_2, ..., p_k, i)\)，使得路径值\(d'[i] = \sum_{j=1}^k cost(p_{j-1}, p_j) < d[i]\)；
当\(\forall p_j \in A\)时，\(d'[i] \geq d[p_k] + cost(p_k, i) \geq d[i]\)，假设不成立；
当\(\exists p_j \notin A\)时，设\(j = min\{j | p_j \notin A, 0 \leq j \leq k\}\)，有\(d'[i] \geq d[p_{j-1}] + cost(p_{j-1}, p_j) \geq d[i]\)，与假设矛盾；

在算法的实现上，我们经常使用“Dijkstra+堆优化”，来避免\(O(E)\)遍历寻找\(d[i] = min\{d[j] + cost(j, i) | j \in A, i \notin A\}\)值最小的节点\(i\)，具体做法是：每把一个新的节点\(i\)加入\(A\)，将其相邻节点\(j\)的\(pair(d[i] + cost(i, j), j), j \notin A\)丢进一个小根堆中维护；
这样每次从堆顶新取到的点\(i \notin A\)就一定是要找的下一个最短路已确定的节点；可以发现每条边只会入一次堆出一次堆，因此可以将\(O(E)\)优化到\(O(logE)\)，总算法复杂度为\(O(ElogE)\)；
需要注意的是堆中信息可能包含重复的\(j\)，第一次取出的\(j\)对应的值一定是最小的，之后的\(j\)直接丢弃即可；
(书中作者说是\(O(ElogV)\)，当\(d[i]\)被更新后才入堆，但是这仍然无法避免同一个节点的信息入堆多次，因此复杂度应该还是\(O(ElogE)\)的)

struct edge { int to, from, cost; };
typedef pair P;

int V;
vector G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
	priority_queue, greater
 > que;
	fill(d, d + V, INF);
	que.push(P{0, s});
	while(!que.empty()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if(d[v] < INF) continue;
		d[v] = p.first;
		for(int i = 0; i < G[v].size(); i++) {
			edge e = G[v][i];
			que.push(P{d[v] + e.cost, e.to});
		}
	}
}

相对作者的写法可读性更强，\(d[i]\)只会在确定最短路的时候被更新一次，相邻\(j\)的最短路我们不在\(d[j]\)上更新，而是直接加入队列，原本每个可能用来更新\(d[j]\)的值都保存在了队列中，会比作者在堆中报错更多节点，但总数也是\(O(E)\)的(算法描述中\(d[i]\)是一个数学变量，而代码中的d[i]有不同含义，请勿与算法实现中的概念混淆！！！)
我们只是采用了一种代码的写法来实现算法而已，原则上我们需要关注的是算法描述，以及代码实现是否正确实现了算法，而不太需要证明自己的代码等价于作者的代码(删掉的部分是因为试图证明代码级别的等价，这属于编程技术而非算法设计的范畴，同样的问题还有\(INF\)的含义，在算法设计范畴中，\(INF\)就是个无限大的值，而在编程技术中，它是一个足够大的值)

Floyd-Warshall算法

Floyd是多源最短路算法，适合处理小规模的密集图，复杂度为\(O(n^3)\)

int d[MAX_V][MAX_V];
int V;
void warshall_floyd() {
	for(int k = 0; k < V; k++) {
		for(int i = 0; i < V; i++) {
			for(int j = 0; j < V; j++) {
				if(d[i][k] < INF && d[k][j] < INF) {
					dp[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
	}
}

floyd的代码看起来非常简单，但理解起来会十分困难，下面会解释原理并给出证明：

首先证明当图中不存在负环时floyd算法的正确性；
floyd的本质实际上是DP，设\(dp[k][i][j]\)为：只使用\(1\)到\(k\)和\(i, j\)节点的情况下，\(i\)到\(j\)的最短路；

• 令\(dp[0][i][i] = 0, dp[0][i][j] = cost(i, j)\)，其他\(dp[0][i][j] = INF代表不存在\)，初始状态\(dp[0][i][j]\)的正确性是显然的；
• 若\(i\)通过\(1, ..., k\)中的点能够到达\(j\)，由于不存在负环，因此\(dp[k][i][j]\)应为只使用\(1\)到\(k\)和\(i, j\)节点的情况下，\(i\)到\(j\)的最短路长度；
  由于\(i\)通过\(1, ..., k\)中的点能够到达\(j\)，且不存在负环，那么一定存在这么一条只使用\(1\)到\(k\)和\(i, j\)节点的最短路径；如果这条路径不过\(k\)点，那么最短路径值为\(dp[k-1][i][j]\)(第\(k-1\)层的正确性已经被证明)；如果路径经过\(k\)点，可以通过\(k-1\)层的两段最短路径计算出来；
• 若\(i\)无法通过\(1, ..., k\)中的点能够到达\(j\)，则\(dp[k][i][j]\)的值应为\(INF\)；
  由于第\(k-1\)层的正确性已经被保证，因此一定不存在一个\(k\)，使得\(dp[k-1][i][k] < INF且dp[k-1][k][j] < INF\)，故\(dp[k][i][j] = INF\)；

因此按照下述方程计算，即可得到第\(k\)层的正确结果；
\(\begin{cases} dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]), dp[k-1][i][k] < INF 且 dp[k-1][k][j] < INF \\ dp[k][i][j] = dp[k-1][i][j], 其他 \end{cases}\)
我们假设前\(k-1\)层的计算结果都是正确的，上述过程通过归纳法很容易证明第\(k\)层的计算结果也是正确的，从而全局计算结果都是正确的；
值得一提的是，可以在最开始令\(dp[0][i][i] = INF\)，不能够从\(i\)“直接到达”\(i\)，\(i\)就只能通过其他路径走一圈，在上述计算过程完成后，\(dp[k][i][i]\)就是包含\(i\)的最小环路径；

由于图中不存在负环，因此\(\forall dp[k][i][j] < INF\)都对应明确的一条最短路径(不确定这是否能算是严格证明)，不存在从\(i\)到\(i\)的\(<0\)的路径，因此\(\forall dp[k][i][i] \geq 0\)；所以\(dp[k-1][i][k] + dp[k-1][k][j]\)可以在\(i = k\)或者\(k = j\)时照常运算，它们不会得到更小的结果；这也使得可以复用数组，不需要担心本层的计算结果再次用于本层的其他计算；最终才有了代码中精炼的DP写法

至此得到了一个结论：当图中不包含负环时，一定有\(\forall dp[i][i] \geq 0\)

为什么要专门强调不包含负环这个前提条件，因为在存在负环的时候上述方程并不是总成立，途径负环的路径不可以被有限若干段路径的累加来计算，因为它永远可以通过走负环变得更小，而我们的计算显然是固定次数的；
例如这样的情况：\(e(1, 3) = 1, e(3, 4) = -1, e(4, 5) = -1, e(5, 3) = -1, e(2, 5) = 1\)，在计算\(dp[4][1][5] = -1， dp[4][5][2] = 0\)，按照floyd的计算过程，\(dp[5][1][2] = -1\)，但是由于包含负环，这个结果应该是无限小；
即，当存在负环时，经过负环的路径不具有明确的最小值可以被有限次计算得出，而当不存在负环的时候一定存在这样一条最短路径；

那么当存在负环时，仍用floyd计算会发生什么事？
通过观察计算过程发现，如果存在某负环，环上所有边的和为\(-\Delta\)，\(i\)是负环上的节点，则计算完成后，一定有\(dp[i][i] \leq -\Delta\)(之所以取\(\leq\)是因为\(i\)可能在其他负环上，但即使不讨论\(dp[i][i] < \Delta\)也无所谓，不影响证明“存在负环时，一定\(\exists dp[i][i] < 0\)这个结论)；
证明的方法也很简单，考虑最后一次生效的\(dp[i][i] = min(dp[i][i], dp[i][k] + dp[k][i])\)，以\(k\)为分界点讨论\(dp[i][k]\)和\(dp[k][i]\)，则需要证明\(dp[i][k] \leq path(i, k), dp[k][i] \leq path(k, i)\)，递归下去会发现最终一定成立；
故，\(\exists dp[i][i] \leq -\Delta < 0\)

至此我们得到了另一个结论：当图中包含负环时，一定有\(\exists dp[i][i] < 0\)

这两个结论加起来，会得到：\(图中包含负环 \iff \exists dp[i][i] < 0\)，我们可以通过是否存在\(dp[i][i] < 0\)来判断负环；

综上所述，无论是否包含负环，\(dp[0][i][j]\)的正确性都是显然的(哪怕存在\(dp[0][i][j] + dp[0][j][i] < 0\)也一样，因为还没有枚举任何“中转点”)；如果不存在只使用\(1\)到\(k\)和\(i, j\)节点的情况下，\(i\)到\(j\)的经过负环的路径，那么计算出来的\(dp[k][i][j]\)也是正确的；如果存在这样的路径，\(dp[k][i][j]\)的真实值应该是无限小，计算得到了一个错误的结果，但是好在存在负环时等价于\(dp[i][i] < 0\)，我们可以根据这个条件来预判；

至此，对floyd的理解应该可以到达80%以上了，下面讨论保存路径的问题；

最短路径保存

对于Bellman-Ford和Dijkstra而言，路径总是单向延伸，只需要保存前驱或后继，最后再通过递归或者循环打印即可；而floyd的最短路径却是每次由两段拼凑成的，这意味着在更新\(dp[i][j]\)值时候需要保存中间节点，最终打印的的时候只能使用递归去打印；
另外，当需要求得最短路的同时打印节点数最少的路径时，应该将节点数作为第二个key来取字典序最小的选择，具体到floyd，应该在\(dp[i][k].first + dp[k][j].first \leq dp[i][j].first 且 dp[i][k].second + dp[k][j].second < dp[i][j].second\)时更新答案；

最小生成树(Minimum Spanning Tree)

一个无向带权连通图，它的生成树是一个包含\(n\)个节点，\(n-1\)条边，并且节点之间两两互通的子图；在这样的生成树中，边权之和最小的叫做最小生成树；
可以发现，一个无向连通图一定存在至少一个生成树，它的dfs树中不包含回边的部分就是一颗生成树；

求最小生成树有Kruskal和Prim算法两种，相对最短路都很好记忆和理解；

Kruskal

算法过程如下：
设我们要构造的最小生成树为\(T\)，最开始\(T\)中只包含一个节点(可以任选一个)，随后每次贪心得选择与\(T\)中节点相连的边权最小的边，将其加入到\(T\)中，\(T-1\)次操作后，得到的就是一颗最小生成树；

假设起初选择的是节点\(v\)，与\(v\)相连的权值最小的边为\(e=(v, u)\)；一定存在一颗最小生成树包含点\(v\)，现在证明一个存在一个最小生成树包含\(e=(v, u)\)；
假设不存在包含\(e=(v, u)\)的最小生成树，我们将

Prim

练习题

证明：一棵树的边数恰好是节点数\(-1\)
证明：边数等于节点数\(-1\)的连通图是一棵树
证明：让一个\(n\)个节点数的图联通最少需要\(n-1\)个边(提示：递归)