DraonAbyss

算法设计与分析

C++(3) CodeForces(23) LeetCode(3) 函数语言程序设计(40) 安全编程(1) 密码学基础(17) 无线网络安全(5) 笔记(16) 编译原理与技术(16) 网络安全数学基础(3) 计算机逻辑基础(8) 题解(37)

/ 注册

全部文章 / 算法设计与分析（共22篇）

第24.1章单源最短路径·Bellman-Ford算法来自专栏

Patrick教授希望找到一条从菲尼克斯(Phoenix)到印第安纳波利斯(Indianapolis)的最短路径。给定一幅美国的道路交通图，上面标有所有相邻城市之间的距离，Patrick教授怎样才能找出这样一条最短的路径呢? 一种可能的办法当然是，先将从菲尼克斯到印第安纳波利斯的所有路径都找出来，将...

2021-12-18

0 791

第25.1章所有结点对的最短路径问题.最短路径和矩阵乘法来自专栏

25.1 最短路径和矩阵乘法

2021-12-18

0 423

第22.3章基本的图算法.深度优先搜索来自专栏

22.3 深度优先搜索深度优先搜索所使用的策略就像其名字所隐含的:只要可能，就在图中尽量“深入”。深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点(v是经过该结点才被发现的)，来搜索该前驱结点的出...

2021-12-17

0 734

第22.2章基本的图算法.广度优先搜索来自专栏

22.2 广度优先搜索广度优先搜索发现前驱父节点 BFS(G,s) for each vertx u ∈ G.V - {s} u.color = WHITE u.d = ∞ u.Π = NIL s.color = GRAY s.d = 0 s.Π = NIL Q ...

2021-12-17

0 507

第22.1章基本的图算法.图的表示来自专栏

本章将介绍图的表示和图的搜索。图的搜索指的是系统化地跟随图中的边来访问图中的每个结点。图搜索算法可以用来发现图的结构。许多的图算法在一开始都会先通过搜索来获得图的结构，其他的一些图算法则是对基本的搜索加以优化。可以说，图的搜系技巧是整个图算法领域的核心。 22.1节对图的两种最常见的计算机表示法进...

2021-12-17

0 454

第26.2章最大流.Ford-Fulkerson方法来自专栏

26.2 Ford-Fulkerson方法本节讨论用来解决最大流问题的Ford-Fulkerson方法。之所以称其为“方法”而不是“算法”，是因为它包含了几种运行时间各不相同的具体实现。Ford-Fulkerson方法依赖于三种重要思想，它们与许多的流算法和问题有关，如残存网络、增广路径和切割。这...

2021-12-16

2 1924

第26.1章最大流.流网络来自专栏

正如可以通过将道路交通图模型化为有向图来找到从一个城市到另一个城市之间的最短路径，我们也可以将一个有向图看做是一个“流网络”并使用它来回答关于物料流动方面的问题。设想一种物料从产生它的源结点经过一个系统，流向消耗该物料的汇点这样一个过程。源结点以某种稳定的速率生成物料，汇点则以同样的速率消耗物料。从...

2021-12-15

1 871

第22.4章基本的图算法.拓扑排序来自专栏

22.4 拓扑排序拓扑排序本节阐述如何使用深度优先搜索来对有向无环图进行拓扑排序。对于一个有向无环图G=(V,E)来说，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件:如果图G包含边(u，v)，则结点u在拓扑排序中处于结点v的前面(如果图G包含环路，则不可能排出一个线性次序)。可以将...

2021-11-26

0 955

第7章快速排序来自专栏

7.1 快速排序的描述分解：数组 A[p..r]被划分为两个(可能为空)子数组 A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都小于等于 A[q]，而A[q]也小于等于A[q+1..r]中的每个元素。其中，计算下标q也是划分过程的一部分。解决：通过递归调用快速排序，...

2021-11-18

0 606

第3章函数的增长来自专栏

3.1 渐进记号渐进记号 Θ, O, o, Ω, ω Θ记号渐进紧确界 = O记号渐进上界 ≤ Ω记号渐进下界 ≥ o记号非渐进紧确的上界＜ ω记号非渐进紧确的下界＞比较各种函数传递性自反性对称性转置对称性类比两个函数f与g的渐进比较和两个实数a与b的...

2021-11-15

0 548