普里姆算法应用场景-修路问题 胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通， 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里， 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短? 正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少。 最小生成树修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 N个顶点，一定有N-1条边 包含全部顶点 N-1条边都在图中 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法 普里姆算法基本介绍普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图。 普利姆的算法如下: 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 若从顶点u开始构 ...

贪心算法基本介绍 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果 贪心算法最佳应用-集合覆盖假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区 都可以接收到信号。 广播台 覆盖地区 K1 “北京”, “上海”, “天津” K2 “广州”, “北京”, “深圳” K3 “成都”, “上海”, “杭州” K4 “上海”, “天津” K5 “杭州”, “大连” 思路分析如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现，列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ -1 个，假设每秒可以计算10个子集，则 广播台数目 子集总数 需要时间 5 32 3.2秒 10 1024 102.4秒 32 4294967296 13.6年 100 1.26x100³º ...

朴素匹配算法基本介绍朴素匹配算法也叫**暴力匹配算法(Brute Force)**，有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？ 如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有： 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符； 如果失配（即S[i]! = P[j]），令i = i - j + 1，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。 思路图解 代码实现12345678910111213141516171819202122232425262728293031323334package com.nanzx.kmp;public class ViolenceMatch { public static void main(String[] args) { String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好"; Stri ...

动态规划b站上一个up主关于动态规划的教学，有助于理解动态规划的主要思想 基本介绍 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 ) 动态规划可以通过填表的方式来逐步推进，得到最优解 动态规划算法最佳实践-背包问题背包问题：有一个背包，容量为4磅 ， 现有如下物品： 物品 重量 价格 吉他(G) 1 1500 音响(S) 4 3000 电脑(L) 3 2000 要求： 目标为装入的背包的总价值最大，并且重量不超出装入的物品不能重复 背包问题思路分析 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是：每种 ...

分治算法(Divide-and-Conquer(P))基本介绍 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)…… 分治算法可以求解的一些经典问题：二分搜索大整数乘法棋盘覆盖合并排序快速排序线性时间选择最接近点对问题循环赛日程表汉诺塔 基本步骤分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题解决：若子问题规模较小而且容易被解决则直接解，否则递归地解各个子问题合并：将各个子问题的解合并为原问题的解 算法设计模式 if |P|≤ n0 then return(ADHOC(P))//将P分解为较小的子问题 P1 ,P2 ,…,Pkfor i←1 to kdo yi ← Divide-and-Conquer(Pi) 递归解决PiT ← MERGE(y1,y2 ...

图基本概念图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中的数据元素，我们则称之为顶点（Vertex）。 图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。 **无向边(Edge)**：若顶点V1到V2之间的边没有方向，则称这条边为无向边。（V1,V2）=（V2,V1）。 **无向图(Undirected graphs)**：图中任意两个顶点之间的边都是无向边。 有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称**弧(Arc)**。用<V1,V2>表示，V1为弧尾(Tail)，V2为弧头(Head)。<V1，V2> ≠ <V2，V1>。 **有向图(Directed graphs)**：图中任意两个顶点之间的边都是有向边。 注意：无向边用“（）”，而有向边用“< >”表示。 权（Weight）：与图的边或弧相关的数。 网（ ...

平衡二叉树基本介绍 平衡二叉树：也叫平衡二叉搜索树（Self-balancing binary search tree），又被称为AVL树， 可以保证查询效率较高。特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 一棵AVL树有如下必要条件： 条件一：它必须是二叉排序树。 条件二：每个节点的左子树和右子树的高度差至多为1。 AVL树的平衡调整左旋转： 问题：当插入8 时，rightHeight() - leftHeight() > 1 成立，此时，不再是一颗avl树了. 怎么处理–进行左旋转： 创建一个新的节点 newNode ，值等于当前根节点的值 把新节点的左子树设置了当前节点的左子树 newNode.left = left 把新节点的右子树设置为当前节点的右子树的左子树 newNode.right = right.left; 把当前节点的值换为右子节点的值 value = right.value; 把 ...

二叉排序树(BST)基本介绍二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点 构造一棵二又排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。 二叉排序树的创建和遍历123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990package com.nanzx.binary ...

哈夫曼树基本概念在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 树的路径长度就是从树根到每一结点的路径长度之和。 若将树中结点赋予一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。WPL最小的就是赫夫曼树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。 哈夫曼树的创建思路分析： 每个数据都是一个节点 ，从小到大进行排序, 每个节点可以看成是一颗最简单的二叉树。 取出节点权值最小的两颗二叉树 。组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 。 再将这颗新的二叉树，以根节点的权值大小再次排序， 不断重复2-3的步骤，直到数列中，所有的数据都被处理，只剩下一个节点时就得到一颗赫 ...