骑士周游问题基本介绍（1）骑士周游问题也被称为马踏棋盘算法 （2）将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。 实现思路骑士周游问题(马踏棋盘问题)实际上是图的深度优先搜索(DFS)的应用。 （1）创建棋盘chessBoard，是一个二维数组。 （2）将当前位置设置为已经访问，然后根

Floyd算法弗洛伊德(Floyd)算法介绍（1）和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 （2）弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径。 （3）迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。 （4）弗洛伊德

迪杰斯特拉(Dijkstra)算法基本介绍迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 实现思路设置出发顶点为v，顶点集合V{v1,v2,vi…}，v到V中各顶点的距离构成距离集合Dis，Dis{d1,d2,di…}]，Dis集合记录着v到图中各顶点的距离(到自身可以看

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）树也只能有一个直接前驱也就是