数据结构学习笔记（01背包问题/图问题）

01背包问题:在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求如何安排能带走最多价值的物品？

动态规划解决背包问题：

设f(i,W)表示，从前i件物品中挑选一些，放进一个空间为W的背包中能获得的最大总价值。

那么如果第i件物品也在最优解中，那么f(i,W)=f(i-1,W-Wi)+Pi，因为从最优解中吧i去掉，前面选中的物品肯定能使一个空间为W-Wi的背包价值最大化，不然它们也不会出现在最优解中。

而如果第i件物品不在最优解中，那么f(i,W)=f(i-1,W)，第i件物品没有占用空间。

通过比较上面两个表达式的大小可以决定第i个物品是不是在最优解中。这就形成了一个递归。

但是如果W<Wi，也就是这个背包装不下第i个物品了，自然只能是f(i,W)=f(i-1,W)。

递归的终止条件是i=1.第一件物品如果能装下，价值就是Pi,装不下就是0.

有许多计算过程重复，可以把重复的f(i,w)保存下来降低复杂度。

图：

图可以用邻接表法表示。每个点拥有一个数组，记录了和它相邻的点。

图也可以用矩阵法表示，横纵是各个点，如果这两个点是相邻的则矩阵的值为1，否则0。只需要对角线的一半，因为另一半是重复的。横纵相同的点设为0.

广度优先搜索BFS：

选取某一点作为源点开始搜索，每一轮将某个点所有相邻的点搜索完毕(称为将此点探索完毕)，然后从剩下未探索完毕点里选取一个作为下一轮探索的起点(选一个距离最近的，使用队列维护)。

因为每个点只能被发现一次，每个点（除了源）都有确定的父结点，因此广度优先搜索会形成一棵树。（广度优先树）

具体算法：

每个点有除了数据域，有三个字段。第一个是颜色，白色的表示没被发现，灰色的表示已经被发现了但是没有探索完毕(会出现在待探索队列中，或者刚出队，是本轮搜索的起点。)，黑色的表示探索完毕(与其相邻的点全部被发现了)。第二个字段表示点的父亲(P,C相邻，探索P周边的时候第一次发现C使得C由白边灰,则P是C的父亲)。第三个结点表示深度(和源点的距离，儿子结点的深度为父亲结点的深度加一)。从源点开始，对其所有相邻的点进行搜索，每新发现一个点就涂成灰色，并且加入待探索队列中。如果某点周边探索完毕，此点就被涂成黑色，然后从队列中取出一个来进行下一轮搜索，直到所有结点变黑，队列中也变空，则整个图搜索完毕。

深度优先搜索：

从源点开始搜索，如果其存在未被发现(白色)的相邻点，就涂成灰色，并以那个点为起点继续往深处探索(递归)。如果某个点的所有邻点都被发现并且依次递归探索过了，那么把此点涂成黑色(形成了一棵树，此结点是树的根节点。)。如果地图中还存在白色的点，那么设为源点开始新一轮搜索（又形成一棵树）。因此深度优先搜索形成一个森林。

深度优先搜索会维护一个全局的时间戳变量，每次新发现一个点并开始一次递归搜索的时候时间戳自增一次。每个点会记录两个时间戳，一个是它被发现的时刻，一个是它被探索完毕的时刻（所有邻点都变黑）

最小生成树：能连通所有点，并且使得各边权值和最小的树.

构造最小生成树使用贪心算法（贪心算法：每一步都采取对当前状况最有利的选择）。假设有一个边的集合A，是一棵最小生成树的一个子集。如果每次都能找到一条边来加入A(称为安全边)，并且保证A依旧是某个最小生成树的子集，那么最终就能构造出最小生成树。

寻找安全边的依据：A是某最小生成树的子集，S是图中的一个割集且S不妨害A（S没有割到A的边），那么S中权值最小的一条边可以安全的加入A中而保持A的性质。

Kruskal算法:

并查集是一种维护集合关系的数据结构，能够快速的判断一个元素是否在某个集合中(或者两个元素是否在同一个集合中)，以及将两个集合合并起来。

Kruskal算法首先将每个点都生成一棵树(一个并查集合)，然后按照权值由小到大遍历各边（安全边）。如果某边两点属于不同的并查集则合并两个集合，直到最后形成一棵树，也就是最小生成树。

Prim算法:

把一个点作为树的跟结点，从剩下的点里，每次选取一个离树最近的点连入树中，最终形成最小生成树(最近的意思是说，把这个点连接到树上的某个点，连线的权值最小。通常使用用斐波那契堆实现的最小优先队列来维护剩余的点)

具体算法：每个点有一个d字段表示和树的最小距离，初始时根结点的d设为0，其余结点的设为无穷大。每个结点还有一个p字段表示其父。准备一个以d为依据的最小优先队列将图中各点放入。

每次从最小优先队列中取出一个点S并进行如下操作：

1.将S加入树中(通过其父，队列中第一个取出的是d为0的根节点，无父)

2.遍历和S相邻的结点，如果某个邻结点C在队列中且SC的权值比C的d字段要小，则将d字段降低为此权值(自然在队列中的顺序得到提升)，然后将C的父设为S。

单源最短路径:求从某源点出发，到图中各点的最短路径(各边权值不同)

最短估计路径和松弛:给每个点一个属性d，表示这个点距离源点的估计值，使得实际的最短路径权值不会超过这个值.

对点u和v进行松弛，是有可能降低v点的路径估计值的操作（d值）。如果d(v)>d(u)+uv，那么就将d(v)改为d(u)+uv，且将v的父设为u。意思是，u对v说，大哥啊，你原来的路太长了，改从我这经过吧！

对于从S到某一点v的最短路径，从s开始一路松弛下去，最终v的d值一定等于最短路径的权值。Dijkstra算法依据此条性质求最短路径。

Dijkstra算法:（要求图中不存在负权边）

使用一个以d为依据的最小优先队列来维护未求得最短路径的各点(初始时，源点的d值为零,其余点的d值为无穷大)。每次从最小优先队列取出一点，并对其相邻的点依次进行松弛操作，以期降低估计值。这样下次从队列中取出的点就是剩余估计值最小的那个点，最小优先队列可以保证对于某一条最短路径而言，各点事依据估计值依次松弛下去的，最终估计值就是最短路径的权值，并通过松弛得到的父子关系确定路径。本质也是一种贪心策略。

最大流解决最大二分匹配问题:

流网络：

一个有向图，拥有一对源点s和汇点v,图中每点都出现在s到v的一条路径中。对每一点而言，净流入为零（类似基尔霍夫电流定律）,每边有个容量值(类似于线路的最大电流)，实际流量（类似于电流）不能超过容量。

残留网络，增广路径和最大流的Ford-Fulkerson方法：

一个流网络的残留网络的每边的权值等于容量-实际流量，反应了一个流量网络还剩余的运载能力。残留网络中如果存在从源点到汇点的路径，则成为增光路径。顺着此路径增加沿路的流即可增加整个网络的流。反复寻找增广路径并沿路增加，如果最终找不到增广路径了，说明已经找到了网络的最大流。这个寻找最大流的方法就是Ford-Fulkerson方法。如果各路径的容量是有理数，此方法一定可以找到最大流。如果各路径是整数，复杂度则相对较低（每次增广至少增加一个整数单位）

Edmonds-Karp算法：

对Ford-Fulkerson方法的改进，每次在残留网络中寻找增广路径时，是寻找一个源点到汇点的最短路径。

Floyd-Warshall算法求两点间最短路径:

此算法通过动态规划的方式，递归求得图中任意两点间的最短路径。设某个图中前k个顶点的集合为Ak，若从i到j有若干这样的路径：i到k之间的中间点必须从集合Ak中选取。那么用d(i,j,k)来表示这些路径中最短的一条。显然当k为图的顶点树的时候，d(i,j,k)就是i和j之间的最短路径。

对于d(i,j,k),假如第k个点不i到j之间的中间点，那么d(i,j,k)=d(i,j,k-1),因为第k个点不影响路径；如果第k个点是i到j的中间点，那么路径分成两半，每一半都是对应两个端点间的最短路径，因此d(i,j,k)=d(i,k,k)+d(k,j,k)。因此d(i,k,k)+d(k,j,k)和d(i,j,k-1)谁比较小，决定了第k个点是否在i到j的最短路径上，形成递归。

递归的终止条件是k=0,此时没有中间点（空集）,i和j直接相连，d(i,j,0)=W(i,j)，也就是ij线的距离。

另外当k为i或j本身时，k必然不在中间点上，此时d(i,j,k)=d(i,j,k-1)

最大二分匹配：

二分图：一个所有回路长度均为偶数的无向图，这样的图能够将顶点分为两部分，每部分内部各顶点间均不相连。

匹配：一个匹配是一个图的一组边的集合，图的每个顶点之多连接匹配中的一条边，如果没有就是这个点未被匹配到。一个匹配相当于将图中的若干顶点两两一对相连。

最大二分匹配：假设一个二分图，顶点分为左，右两侧。每侧顶点内部互不相连。左侧每个顶点表示一个人，右侧每个顶点表示一份工作。二分图中每个连接人-工作的边表示这个人有能力做这项工作。每项工作最多只需要一个人，每个人最多只能完成一项工作，如何分配工作(匹配)才能人尽其用呢？这就是一个求二分图中最大匹配的问题。

最大流解决最大二分匹配问题：

在左侧顶点的左边加入源点，右侧顶点的右边加入汇点，连接源点-左侧各点-右侧各点-汇点的各边赋予1的容量，于是就构造出了一个流网络。由于各边容量均为1，那么使得此流网络形成最大流的方案，也就是原二分图的最大匹配了。