Estom的博客

图算法-Dijkstra算法 目录 图算法-Dijkstra算法 图算法-Floyd算法 图算法-Bellman-Ford算法 图算法-Prim算法 图算法-Kruskal算法 参考文献https://www.cnblogs.com/ggzhangxiaochao/p/9070873.html 1 问题描述 Kruskal算法是一种用来寻找最小生成树的算法，由Joseph Kruskal在1956年发表。 用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。 当点少，但是关系复杂的时候，使用prim算法，进行点的贪心。 当点多，但是关系很稀疏的时候，使用kruskal算法那，进行边的贪心 2 算法原理 记Graph中有v个顶点，e个边 新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边 将原图Graph中所有e个边按权值从小到大排序 循环：从权值最小的边开始遍历每条边。if这条边连接的两个节点于图Graphnew中不...

图算法-Floyd算法 目录 图算法-Dijkstra算法 图算法-Floyd算法 图算法-Bellman-Ford算法 图算法-Prim算法 图算法-Kruskal算法 参考文献 https://www.jianshu.com/p/f73c7a6f5a53 https://blog.csdn.net/jeffleo/article/details/53349825 1 问题分析 Floyd算法是一个经典的动态规划算法，它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点最短路径的算法 ,算法目标是寻找从点i到点j的最短路径。 2 算法原理 Floyd算法的基本思想：可以将问题分解: 第一、先找出最短的距离 第二、然后在考虑如何找出对应的行进路线。 以后再整理一下文字内容 3 算法过程 顶点名称和下标的对应 A B C D E F G 0 1 2 3 4 5 6 弗洛伊德算法定义了两个二维矩阵 矩阵D记录顶点间的最小路...

图算法-Prim算法 目录 图算法-Dijkstra算法 图算法-Floyd算法 图算法-Bellman-Ford算法 图算法-Prim算法 图算法-Kruskal算法 参考文献 https://www.cnblogs.com/ggzhangxiaochao/p/9070873.html 1 问题分析 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。 主要思想是基于顶点的贪心思想。 2 算法原理 输入：一个加权连通图，其中顶点集合为V，边集合为E； 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 重复下列操作，直到Vnew = V： 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任...

蛮力法0 蛮力法概述 蛮力法是一种简单直接地解决问题的方法，常常直接 基于问题的描述和所涉及的概念定义。 1 查找算法2 搜索算法——广度优先搜索3 搜索算法——深度优先搜索4 排序算法——简单排序5 排序算法——线性排序6 线性时间选择算法7 字符串算法——匹配算法8 字符串算法——其他算法9 位运算算法

查找算法 阅读目录 顺序查找 二分查找 插值查找 斐波那契查找 树表查找 分块查找 哈希查找 0 概述 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。 本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。 插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。 查找算法，一般适用于线性结构。 搜索算法，一般适用于树和图。 查找定义 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 查找算法分类： 静态查找和动态查找； 静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。 无序查找和有序查找。 无序查找：被查找数列有序无序均可； 有序查找：被查找数列必须为有序数列。 平均查找长度（Average Search Length，ASL） 需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。 对于...

深度优先搜索1 概述定义 深度优先搜索（DFS：Depth-First Search）是一种图搜索策略，其将搜索限制到 2 种操作： 访问图中的一个节点； 访问该节点的子节点； 过程 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点 v 的所有边都已被探寻过后，搜索将回溯到发现顶点 v 有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。实际上深度优先搜索最初的探究也是为了解决迷宫问题。 对图的深度优先搜索与对树（Tree）的深度优先遍历（Depth First Traversal）是类似的，区别在于图中可能存在环，所以可能会遍历到已经遍历的节点。 例子 例如，下面的图中，从顶点 2 开始遍历，当遍历到顶点 0 时，子顶点为 1 和 2，而顶点 2 已经遍历过，如果不做标记，遍历过程将陷入死循环。所以，在 DFS 的算法实现中需要对顶点是否访问过做标记。 上图的 DFS 遍历结果为 2, 0, 1, 3。 实现 DFS 算法可以通过不同方式来实现： 递归方式 非递归方式：栈（Stack）数据结构...

广度优先搜索1 概述特点 广度优先搜索（BFS：Breadth-First Search）是一种树和图搜索策略，其将搜索限制到 2 种操作： 访问图中的一个节点； 访问该节点的邻居节点； 过程 广度优先搜索（BFS）由 Edward F. Moore 在 1950 年发表，起初被用于在迷宫中寻找最短路径。在 Prim 最小生成树算法和 Dijkstra 单源最短路径算法中，都采用了与广度优先搜索类似的思想。 对图的广度优先搜索与对树（Tree）的广度优先遍历（Breadth First Traversal）是类似的，区别在于图中可能存在环，所以可能会遍历到已经遍历的节点。BFD 算法首先会发现和源顶点 s 距离边数为 k 的所有顶点，然后才会发现和 s 距离边数为 k+1 的其他顶点。 例子 例如，下面的图中，从顶点 2 开始遍历，当遍历到顶点 0 时，邻接的顶点为 1 和 2，而顶点 2 已经遍历过，如果不做标记，遍历过程将陷入死循环。所以，在 BFS 的算法实现中需要对顶点是否访问过做标记。 上图的 BFS 遍历结果为 [ 2, 0, 3, 1 ]。 实...

排序算法0 比较排序算法分类比较排序（Comparison Sort）通过对数组中的元素进行比较来实现排序。 比较排序算法（Comparison Sorts） Category Name Best Average Worst Memory Stability  插入排序  （Insertion Sorts）    插入排序 （Insertion Sort） n n2 n2 1 Stable  希尔排序 （Shell Sort） n n log2 n n log2 n 1 Not Stable  交换排序 （Exchange Sorts ）        快速排序 （Quick Sort）  n log n n log n n2 log n Not Stable  冒泡排序 （Bubble Sort） n ...

线性时间选择算法1 问题概述 在一个由 n 个元素组成的集合中，第 i 个顺序统计量（order statistic）是该集合中第 i 小的元素。也就是说，最小值是第 1 个顺序统计量（i = 1），最大值是第 n 个顺序统计量（i = n）。 中位数（median）是它所在集合的中点元素。当 n 为奇数时，中位数是唯一的，出现在 i = (n + 1)/2 处。当 n 为偶数时，存在两个中位数，下中位数 i = n/2 和上中位数 i = n/2 + 1 处。因此，不考虑 n 的奇偶性，中位数总是出现在 i = (n+1)/2 的中位数处。本文中所用的中位数总是指下中位数。 选择最大值和最小值 选择中位数或任意位置值 1 选择最大值和最小值算法原理对于确定最大值和最小值的问题，n-1 次比较是最优的。 对于同时获取最大值和最小值，至多需要 3(n/2) 次比较就足以同时找到。如果 n 是奇数，那么总共需要 3(n/2) 次比较。如果 n 是偶数，则可先做一次...