这里介绍 Dijkstra 算法,它是一个应用最为广泛的、名气也是最大的单源最短路径算法Dijkstra 算法有一定的局限性:它所处理的图中不能有负权边「前提:图中不能有负权边」换句话说,如果一张图中,但凡有一条边的权值是负值,那么使用 Dijkstra 算法就可能得到错误的结果不过,在实际生活中所解决的问题,大部分的图是不存在负权边的如:有一个路线图,那么从一点到另外一点的距离肯定是一个正数所以...点击进入阅读全文

Prim算法1.概览普里姆算法Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点英语Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Ro...点击进入阅读全文

一、连通分量和FloodFill算法首先,我们来介绍一个概念:子图(subgraph)。若一个图的顶点集和边集分别是另一图的顶点集的子集和边集的子集,则称该图为另一图的子图。换句话说,从一个图里选出一部分顶点和边,只要确保选择的边对应的两个顶点也都被选择,那么所有选出的顶点和边组成的图就是原图的子图。就像在一个社交网络中,同班同学的帐号之间的关系就组成了整个社交网络的一个子图。接下来,我们介绍一个...点击进入阅读全文

其实并查集顾名思义就是有“合并集合”和“查找集合中的元素”两种操作的关于数据结构的一种算法。

概述

性质

并查集算法不支持分割一个集合。

算法

用集合中的某个元素来代表这个集合,该元素称为集合的代表元。一个集合内的所有元素组织成以代表元为根的树形结构。对于每一个元素 parent[x]指向x在树形结构上的父亲节点。如果x是根节点,则令parent[x] = x。对于查找操作,假设需要确定x所在的的集合,也就是确定集合的代表元。可以沿着parent[x]不断在树形结构中向上移动,直到到达根节点。
判断两个元素是否属于同一集合,只需要看他们的代表元是否相同即可。

路径压缩

为了加快查找速度,查找时将x到根节点路径上的所有点的paren设为根节点,该优化方法称为压缩路径。使用该优化后,平均复杂度可视为Ackerman函数的反函数,实际应用中可粗略认为其是一个常数。

用途

1维护无向图的连通性。支持判断两个点是否在同一连通块内,和。2、判断增加一条边是否会产生环:用在求解最小生成树的Kruskal算法里。

referenc

《ACM国际大学生程序设计竞赛 知识与入门 俞勇主编...点击进入阅读全文

今天我们来学习,学习一个数据结构之前,我们还是先来了解一下这个东西在干什么用的吧。相信大家都知道并用过有一个类优先队列。很多优先队列的内部实现就是堆。此外,堆还可以用来排序,还可以进行一些算法的优化。我们后续有机会再继续介绍。这不是一篇教程,只是根据我对堆的理解,总结一些性质。我们还是使用问答的形式。第一,什么是堆?数据结构中的堆跟平时我们讲的内存的堆还是有点区别的。数据结构中的堆其实是利用完全二叉树的结构来维护一组数据。...点击进入阅读全文

BST树即二叉搜索树1.所有非叶子结点至多拥有两个儿子(Left和Right);2.所有结点存储一个关键字;3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;如

       BST树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报...点击进入阅读全文

我们前面说到玄奘西行,要出网关。既然出了网关,那就是在公网上传输数据,公网往往是不可靠的,因而需要很多的机制去保证传输的可靠性,这里面需要恒心,也即各种重传的策略,还需要有智慧,也就是说,这里面包含着大量的算法

如何做个靠谱的人?

TCP 想成为一个成熟稳重的人,成为一个靠谱的人。那一个人怎么样才算靠谱呢?咱们工作中经常就有这样的场景,比如你交代给下属一个事情以后,下属到底能不能做到,做到什么程度,...
点击进入阅读全文

上一节,我们讲的 UDP,基本上包括了传输层所必须的端口字段。它就像我们小时候一样简单,相信“网之初,性本善,不丢包,不乱序”。后来呢,我们都慢慢长大,了解了社会的残酷,变得复杂而成熟,就像 TCP 协议一样。它之所以这么复杂,那是因为它秉承的是“性恶论”。它天然认为网络环境是恶劣的,丢包、乱序、重传,拥塞都是常有的事情,一言不合就可能送达不了,因而要从算法层面来保证可靠性。

TCP 包头格式

我们先...
点击进入阅读全文

讲完了 IP 层以后,接下来我们开始讲传输层。传输层里比较重要的两个协议,一个是 TCP,一个是 UDP。对于不从事底层开发的人员来讲,或者对于开发应用的人来讲,最常用的就是这两个协议。由于面试的时候,这两个协议经常会被放在一起问,因而我在讲的时候,也会结合着来讲。

TCP 和 UDP 有哪些区别?

一般面试的时候我问这两个协议的区别,大部分人会回答,TCP 是面向连接的,UDP 是面向无连接的。什么...
点击进入阅读全文

俗话说得好,在家千日好,出门一日难。网络包一旦出了网关,就像玄奘西行一样踏上了江湖漂泊的路。上一节我们描述的是一个相对简单的情形。出了网关之后,只有一条路可以走。但是,网络世界复杂得多,一旦出了网关,会面临着很多路由器,有很多条道路可以选。如何选择一个更快速的道路求取真经呢?这里面还有很多门道可以讲。

如何配置路由?

通过上一节的内容,你应该已经知道,路由器就是一台网络设备,它有多张网卡。当一个入口的...
点击进入阅读全文