Kruskal算法基本介绍（1）克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。 （2）基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 （3）具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。 算法分析根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了

Prim算法 Prim算法 应用场景 最小生成树 算法介绍 代码实现 应用场景最短路径问题，给定带权无向连通图，选中尽可能少的线路，使各顶点连通，并且使总路程最小。 也就是最小生成树问题。 最小生成树最小生成树(Minimum CostSpanning Tree)，简称MST。 （1）给定一个带权的无向连通图，如何选取一棵生成树，使树上所有边上权的总和为最小，这叫最小生成树。 （2）N个顶点

贪心算法 贪心算法 应用场景 基本介绍 应用实现 代码实现 应用场景集合覆盖 假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信号 广播台 覆盖地区 K1 “北京”,”上海”,”天津” K2 “广州”,”北京”,”深圳” K3 “成都”,”上海”,”杭州” K4 “上海”,”天津” K5 “杭州”,”大

KMP算法暴力匹配算法如果用暴力匹配的思路，并假设现在str1匹配到i位置，子串str2匹配到j位置，则有： （1）如果当前字符匹配成功，即str1[i] == str2[i]，则i++,j++，继续匹配下一个字符 （2）如果失败，即str1[i] != str2[j]，令i=i-(j-1),j=0。相当于每次匹配失败时，i回溯，j被置为0。 （3）用暴力方法解决的话就会有大量的回溯，每次只移动一

动态规划 动态规划 动态规划解决背包问题 基本介绍 思路分析 代码实现 （1）动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。 （2）动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 （3）与分治法不同的是，适合于用动态规划求解的问

分治算法基本介绍分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题….直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换… 分治算法可以求解的一些经典问题： 二分搜索 大整数乘法 棋盘覆盖 合并排序

图 图 图的基本介绍 为什么要有图 图的常用概念 图的表示方式 邻接矩阵 邻接表 构建图 构建图的实现思路 构建图的代码实现 图的遍历 深度优先遍历基本思想 深度优先遍历实现思路 深度优先遍历代码实现 广度优先遍历基本思想 广度优先遍历实现思路 广度优先遍历代码实现 图的基本介绍为什么要有图（1）线性表局限于一个直接前驱和一个直接后继的关系 （2）树也只能有一个直接前驱也就是

多路查找树 多路查找树 二叉树与B树 二叉树的问题分析 多叉树的基本介绍 B树的基本介绍 2-3树基本介绍 2-3树的构建思路 B树、B+树和B*树 B树的介绍 B树的相关概念 B+树的相关概念 B*树的相关概念 二叉树与B树二叉树的问题分析二叉树的操作效率较高，但是也存在问题。 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多（比如1亿），就存在如

平衡二叉树(AVL) 平衡二叉树(AVL) 背景引入 基本介绍 实现思路 代码实现 背景引入二叉排序树可能的问题： 给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST)，并分析问题所在。 BST存在的问题分析： （1）左子树全部为空，从形式上看，更像一个单链表。（2）插入速度没有影响（3）查询速度明显降低（因为需要依次比较），不能发挥BST的优势，因为每次还需要比较左子树

二叉排序树(BST) 二叉排序树(BST) 背景引入 需求分析 解决方案分析 使用数组 使用链式存储（链表） 使用二叉排序树 二叉排序树基本介绍 二叉排序树的创建与排序 二叉排序树的删除 思路分析 代码实现 拓展练习 背景引入需求分析给你一个数列 (7,3,10,12,5,1,9)，要求能够高效的完成对数据的查询和添加 解决方案分析使用数组 数组未排序 优点：直接在数组尾添加，速