一、图论
1.最小生成树
- 对于带权连通图G （每条边上的权均为大于零的实数），可能有多棵不同生成树。
- 每棵生成树的所有边的权值之和可能不同。
- 其中权值之和最小的生成树称为图的最小生成树。
(1) Prim算法
Prim算法实现的是找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。
(2) Kruskal算法
Kruskal算法与Prim算法的不同之处在于，Kruskal在找最小生成树结点之前，需要对所有权重边做从小到大排序。将排序好的权重边依次加入到最小生成树中，如果加入时产生回路就跳过这条边，加入下一条边。当所有结点都加入到最小生成树中之后，就找出了最小生成树。
Kruskal算法在效率上要比Prim算法快，因为Kruskal只需要对权重边做一次排序，而Prim算法则需要做多次排序。尽管Prim算法每次做的算法涉及的权重边不一定会涵盖连通图中的所有边，但是随着所使用的排序算法的效率的提高，Kruskal算法和Prim算法之间的差异将会清晰的显性出来。
- prim:该算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图
- kruskal:需要对图的边进行访问，所以克鲁斯卡尔算法的时间复杂度只和边又关系，可以证明其时间复杂度为O（eloge）。适合稀疏图
2.最短路径
考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边 的权值之和定义为该路径的路径长度或称带权路径长度。
从源点到终点可能不止一条路径，把路径长度最短的那条路径 称为最短路径。
(1) Dijkstra算法
算法思想是按路径长度递增的次序一步一步并入来求取，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径问题。
设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v, …, vk，就将vk加入集合S中，并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。
(2) Floyd算法
Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。
对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。
3.拓扑排序
设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列v1， v2，…，vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件： 若<i，j>是图中的边（或从顶点i → j有一条路径）: 在一个有向图中找一个拓扑序列的过程称为拓扑排序。
举个例子，课程安排问题，学习某门课程有时候需要先学习其他课程，如，要学习高数二，就必须先将高数一学完，因此课程学习就必须将高数一安排在高数二前面学习。
4.关键路径
(1)AOE网
-
用一个带权有向图（DAG）描述工程的预计进度。
-
顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的 时间（比如天数）。
-
图中入度为0的顶点表示工程的开始事件（如开工仪式），出度为0的 顶点表示工程结束事件。
AOE网（Activity On Edge）
(2)关键路径
从AOE网中源点到汇点的最长路径，具有最大长度的路径叫 关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
5.二分图
简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说，把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。
最大匹配：
在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数.如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配。
最优匹配：
最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。
最小覆盖：
分为最小顶点覆盖和最小路径覆盖：
①最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的最大匹配数；
②最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数= V - 二分图的最大匹配数；
最大独立子集：
最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集= V -二分图的最大匹配数。
(1)匈牙利算法
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路
由增广路的性质，增广路中的匹配边总是比未匹配边多一条，所以如果我们放弃一条增广路中的匹配边，选取未匹配边作为匹配边，则匹配的数量就会增加。匈牙利算法就是在不断寻找增广路，如果找不到增广路，就说明达到了最大匹配。
它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
6.并查集
并查集是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
并查集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
可以将森林合并成一颗树。
一般分为：初始化、查找、合并三步，在查找的时候可以进行路径压缩，即让所有子节点连接在根节点上。
7.最大团问题
就是在一个无向图中找出一个点数最多的完全图。
完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
8.欧拉路径
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径。
如果一个回路是欧拉路径，则称为欧拉回路。
如果一个回路是欧拉路径，则称为欧拉回路。
9.弦图
对于一个无向图，若该图的任意一个长度大于3的环中存在一条边连接这个环上不相邻的两点，则此图称作弦图。
10.最小环问题
最小环是指在一个图中，有n个节点构成的边权和最小的环。
从一个点出发,经过一条简单路径回到起点成为环。图的最小环就是所有环中长度最小的。
11.无向图最小割
无向图的割：就是去掉一些边，使得原图不连通，最小割就是要去掉边的数量最小。
二、算法
1.背包问题
(1) 01背包
有N件物品和一个容量为V的背包。每种物品只有一个。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
(2) 完全背包
有N件物品和一个容量为V的背包。每种物品都有无限个。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
(3) 多重背包
有N中物品和一个容量为V的背包。第i中物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。