算法专题:拓扑排序

拓扑排序(Topological Sorting)是图论中一个比较重要的概念。它主要用来解决下面这类问题: 给定一个 AOV 网(Activity On Vertex Network), $ A\rightarrow B $ 表示活动 $ A $ 必须在活动 $ B $ 之前完成。请给出一个合理的活动顺序。 当然,AOV 网中不可能出现环,因为出现了环就无法拓扑排序。因此可以用拓扑排序来判断图中是否存在环。 关于拓扑排序,我们来看一下下面这张图片: Toplogical Sorting 我们可以用队列来实现这个算法,具体改进的过程如下: 记录每个点的入度; 将入度为 0 的顶点加入队列; 依次对入度为 0 的点进行删边操作,同...

2013年11月3日 · 2 分钟 · 838 字 · Kai Wang

算法专题:多源最短路径 - Floyd-Warshall Algorithm

这次我们来讨论一下关于多源最短路径 APSP(All-Pairs Shortest Paths)。即求出给定的图 $ G=\left ( V,E \right ) $ 中任意两对顶点 $ V_{i},V_{j} $ 之间的最短路径。我们根据下面这幅图来理解一下这个概念: 多源最短路径 对于这一问题,比较有效的算法是 Floyd-Warshall Algorithm,简称 Floyd。它是基于动态规划的一种最短路径的算法。 我们用 $ f^{k}\left ( i,j \right ) $ 来表示从顶点 $ i $ 到顶点 $ j $ 不经过索引比 $ k $ 大的点的最短路径。这样一来,我们就可以根据 $ f^{k-1}\left ( i,j \right ) $ 推出 $ f^{k}\left ( i,j \right ) $ 。 假设我们目前已知 $ f^{k-1}\left ( i,j \right ) $ ,要推出 $ f^{k}\left ( i,j \right ) $ ,无外...

2013年11月3日 · 2 分钟 · 738 字 · Kai Wang

算法专题:单源最短路径 - SPFA

SPFA 是 Shortest Path Fast Algorithm 的缩写,它是之前介绍的 Bellman-Ford Algorithm 的一种队列实现,减少了不必要的冗余计算。 算法的基本步骤如下: 初始化队列和标记数组,将源点入队。 每次取队首元素,对其发出的所有边进行松弛。并将松弛过的且不在队列中的顶点加入到队列中。 重复第二步直至队列为空。 若要判断负环,则当某个顶点松弛超过V次,即存在负环。 对于SPFA还是比较容易理解的,它的复杂度为 $O\left(kE\right)$。 代码如下: #include <iostream> #include <memory.h> #include <vector> #include <queue> using namespace std; const int MAX = 10240; bool pQueue[MAX]; int N, M, pDist[MAX], pCnt[MAX]; // pCnt[]记录顶点i松弛的次数 vector<pair<int, int> > pMap[MAX]; queue<int> Q; void SPFA(int s); int main() { cin >> N >> M;...

2013年11月3日 · 2 分钟 · 518 字 · Kai Wang

算法专题:单源最短路径 – Bellman-Ford Algorithm

上一篇文章介绍了一下 Dijkstra Algorithm,但是它仅局限于处理非负权值的图。若图中出现负边,Dijkstra Algorithm 就会出现错误。这时候就需要使用其他的算法来求解单源最短路径。 Ballman-Ford 是一个非常实用的算法,它是由美国数学家 Richard Ballman 和 Lester Ford 发明的。Ballman-Ford 算法的基本流程如下: 初始化 $ pDist\left [ \right ] $ 数组。 检查每一条边,如果源点到该条边的起点有通路,则更新原点到该条边的终点的最短路径。循环 $ V $ 次即可得到结果。 如若要检测是否存在负环,则再检查每一条边,若可以松弛,则有负环。 我们来看一张图片具体体会一下 Bellman-Ford Alg...

2013年11月3日 · 2 分钟 · 591 字 · Kai Wang

算法专题:单源最短路径 – Dijkstra Algorithm

这个星期开始复习最短路的一些算法。 单源最短路径(Single Source Shortest Paths),简称 SSSP。这是图论中非常重要的一类算法。解决这一问题有多种算法,今天先来介绍一下 Dijkstra Algorithm。 首先介绍一下单源最短路径的概念,通俗的讲,就是给定一个源点 $ s $ (即起点),求这个源点到其他各个顶点的最短路径。最短路径,通俗的来讲,我们称使得顶点 $ V_{i} $ 到顶点 $ V_{j} $ 所经过的路径的权值之和最小的一条路径,称为从顶点 $ V_{i} $ 到顶点 $ V_{j} $ 的最短路径。 单源最短路径 上面这幅图标出了从源点 $ s $ 到各个顶点的最短路径,大家可以根...

2013年11月3日 · 2 分钟 · 868 字 · Kai Wang

算法专题:最小生成树 – Kruskal Algoritm

今天来介绍一下最小生成树的另外一种算法:Kruskal Algorithm。这个算法是基于贪心实现的,算法的大体过程如下: 取权值最小的边,如果加入这条边以后,不会出现环,那么就加入这条边。 重复上述操作,直至加入了 $ N-1 $ 条边。 我们还是先来看一张图片来理解一下这个算法: Kruskal 算法 下面我们来考虑这个算法,最棘手的问题是判断是否构成环,这里我们采用并查集来处理这个问题,它的复杂度是 $ O\left(V*\alpha\left(V\right)\right) $ 。对于每次寻找权值最小的边,复杂度是 $ O\left(E\right) $ 。这样一来,复杂度将高达 $ O\left(V*\alpha\left(V\right)+VE\right) $ ,即 $ O\left(VE\right) $ 。 我们考虑优化,每次寻找权值最小的边,可以...

2013年10月20日 · 2 分钟 · 677 字 · Kai Wang

算法专题:最小生成树 – Prim Algoritm

最近开始准备 NOIP 复赛,发现很多算法已经不会了。只能一个个的捡起来,慢慢复习,顺便做点笔记。 最小生成树(Minimum Spanning Trees),简称 MST。是图论中一个非常重要的概念。解决这个问题有两种算法,今天暂且先来讨论一下 Prim Algorithm。不做特别说明,讨论的都是无向图。 首先介绍一下最小生成树的概念,我们知道,图可以这样定义 $ G=\left(V,E\right) $ ,其中 $ G $ 表示图, $ V $ 表示顶点集合, $ E $ 表示边集合。最小生成树是这样一棵树,它满足 $$ w\left ( T \right )=\min {\left \{ \sum_{\left ( u,v \right )\in T}w\left ( u,v \right ) \right \}} $$ 通俗地讲,就是使得图 $ G $ 连通时,所选取的...

2013年10月19日 · 3 分钟 · 1167 字 · Kai Wang

杂记(20130930)

随便写写,记录一下最近发生的事情。 高中最后一次运动会居然是在停课中度过的。不过比起化学组去省选的那些人还算幸运的,至少也参与了一点,虽然成绩只有一个引体向上。 29号晚自习,我在机房给高二的上课,讲解初赛的选择题。真正感觉到了「后生可畏」的感觉。本来想冲个省队的,但是我们的国赛在明年7月份,那时候我们已经毕业了,所以不能代表江苏省参赛。信息学竞赛就这点不好,各门竞赛大多高三才到炉火纯青的地步,却不给省队资格。虽然我们全国各地的高三选手联名向CCF抗议,但还是无疾而终。挺可惜的,但至少可以拿个省一回...

2013年9月30日 · 2 分钟 · 540 字 · Kai Wang

中秋望月感怀(2013)

在我的印象中,从来没有过真正意义上的赏月。小时候虽然每年都会如约赏月,但那时候年纪尚小,即使望月,也不会有什么特别的感触。 自从高二受了周红娟老师的耳濡目染,再者,加上《唐诗之旅》的熏陶,开始对明月产生了一种别样的情怀。自此以后,每当看到明月,想到的不再时冷冰冰的月球,而是嫦娥玉兔,吴刚伐树。有时候甚至会像李白一样「举杯邀明月,对影成三人」。 前几天住宿的时候,便已经感到了中秋的到来。熄灯后,一束月光打在床上,真如太白所记「床前明月光,疑是地上霜」。 今天晚上看新闻,提到瘦西湖是最佳赏月之地,不禁想起...

2013年9月19日 · 4 分钟 · 1543 字 · Kai Wang

关于复数的一些补充

新版高中教材对复数内容进行了极大的删减,使得我们对于复数的认知还停留在最原始的阶段。殊不知,复数的应用非常广泛。现参考《高中数学·甲种本》以及搜集的一些资料,包括做过的例题,整理一下关于复数的内容。 一、复数的概念 1.1 数的概念的发展 数的概念是从实践中产生和发展起来的。早在原始社会末期,由于记数的需要,人们就建立起自然熟的概念。自然数的全体构成自然数集$\mathbf{N}$。 随着生产和科学的发展,熟的概念也得到了发展。 为了表示各种具有相反意义的量以及满足记数法的要求,人们引进了零和负数,把自然数看作...

2013年8月30日 · 26 分钟 · 12908 字 · Kai Wang