algorithm

累计撰写 247 篇文章
累计创建 16 个标签
累计收到 0 条评论

标签搜索

目录CONTENT

以下是 algorithm 相关的文章

2021-04-23
关键路径的定义及其应用场景（AOE网）有时候我们要解决工程完成需要的最短时间问题。我们要对一个流程图计算最短时间，就要分析流程之间的拓扑关系，并且找到当中最关键的流程，这个流程的时间就是最短时间。在前面介绍的 AOV 网的基础上，我们来引入一个新的概念，在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动
- 2021-04-23
- 128
- 0
- 0
2021-04-23
拓扑排序的定义及其应用场景（AOV网）所谓无环图，就是图中没有回路。无环图两个常见的应用就是拓扑排序和关键路径。我们先来看看拓扑排序。在日常生活中，我们通常会把软件开发、生产流程、网络设备互联都当成一个项目工程来对待，所有工程都可以分为若干个子工程（或者称之为「活动」），这些子工程之间往往会有一些条件约束，比如其中某些活动必须在另一些活
- 2021-04-23
- 174
- 0
- 0
2021-04-23
最短路径的实现算法（二）：弗洛伊德算法（Floyd）实现原理弗洛伊德算法的基本思想如下：从任意节点 A 到任意节点 B 的最短路径不外乎两种可能，一种是直接从 A 到 B，一种是从 A 经过若干个节点到 B，所以，我们假设 dist(A,B) 为节点 A 到节点 B 的最短路径的距离，对于每一个节点 K，我们检查 dist(A,K) + dist(K
- 2021-04-23
- 122
- 0
- 0
2021-04-23
最短路径及实现算法（一）：迪杰斯特拉算法（Dijkstra）最短路径在日常生活中，我们经常面临路径选择的问题，比如从杭州到北京，可以选择汽车、火车、飞机，甚至还可以坐公交车（这不是笑话，最近网上就流传一个从杭州回临沂，转了 35 班公交车，行程 660 多公里，历时 7 天的神奇春运回家路），对于不同的选择，意味着不同的路径，不同的路径意味着不同的成本，这个
- 2021-04-23
- 118
- 0
- 0
2021-04-23
最小生成树的实现算法之克鲁斯卡尔算法（Kruskal）实现原理与普里姆算法不同，克鲁斯卡尔算法主要以边为维度，每次从剩下的边中找权重值最小的边来构建最小生成树，具体实现思路如下：将无向图的边按权重大小递增式排序，放到集合中遍历该集合，找出权重最小的边，加入到结果生成树的集合中如果结果生成树出现回路，则放弃这条边重新执行步骤2，直至所有顶点被遍历，最终生
- 2021-04-23
- 130
- 0
- 0
2021-04-23
最小生成树的实现算法之普里姆算法（Prim）算法定义简单来说，普里姆算法从图中某个顶点开始，将其作为一棵树的根节点，然后这棵树会逐步长大，一直长大到覆盖图中的每一个顶点为止，每一步都会从剩下的与当前操作节点相邻的顶点中找到一条权重最小的边加入到树中，当算法终止时，这棵树就是一棵最小生成树。下面是图示过程：从 V1 开始，从与其相邻的顶点中找到
- 2021-04-23
- 126
- 0
- 0
2021-04-23
最小生成树的定义和应用场景以无向图为例，如果图的任意两个顶点之间都是想通的，这个图就是连通图。一个连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，和足以构成一棵树的 n-1 条边，如下图所示：图1是一个连通图，图2是该连通图的生成树，反过来说，如果一棵树大于 n-1 条边，则必然构成环。前面我们也提到，带权
- 2021-04-23
- 123
- 0
- 0
2021-04-23
图的遍历（下）—— 广度优先搜索广度优先搜索定义广度优先搜索（Breadth First Search），简称 BFS，我们以在家里房间里找钥匙为例来对比说明深度优先搜索和广度优先搜索，深度优先搜索好比我们从某个房间（顶点）开始，先把一个房间的所有角落找遍，再从下一个相邻房间开始继续找，依次类推，但这有时候并不是最佳方案，我们可以
- 2021-04-23
- 125
- 0
- 0
2021-04-23
图的遍历（上）—— 深度优先搜索图的遍历和树的遍历类似，最直接的理解就是，在图中某个顶点出发，访遍图中其余顶点，并且其中每个顶点仅被访问一次，这个过程就是图的遍历。图的遍历主要有两种方式，一种是深度优先搜索，一种是广度优先搜索。我们先来看深度优先搜索。深度优先搜索定义深度优先搜索（Depth First Search），简称 DF
- 2021-04-23
- 148
- 0
- 0
2021-04-22
压缩算法的基础（下）：赫夫曼编码及其应用赫夫曼树是为了解决远距离通信（主要是电报）数据传输的最优问题。比如，我们需要在网络上传输 BADCADEEFD 字符串序列给其他人，每个字符占一个字节，如果要压缩的话可以通过二进制编码的方式进行传输，这个字符串包含了 6 个字符：ABCDEF，我们可以用对应的二进制表示如下：字符ABCDEF进制00
- 2021-04-22
- 118
- 0
- 0

1
2
3