一:图的分类 1:无向图         即两个顶点之间没有明确的指向关系,只有一条边相连,例如,A顶点和B顶点之间可以表示为 <A, B> 也可以表示为<B, A>,如下所示                     &nbs…

2016年5月25日 0条评论 0点热度 阅读全文

十大算法之Dijkstra算法:   最短路径是图论算法中的经典问题。图分为有向图、无向图,路径权值有正值、负值,针对不同的情况需要分别选用不同的算法。在维基上面给出了各种不同的场景应用不同的算法的基本原则:最短路问题。 针对无向图,正权值路径,采取Dijkstra算法。 如上图,是求a到b的最短路径,这里并不限定b节点,修改为到任意节点的路径,问题是完全一样的。 首先需要记录每个点到原点的距离,这个距离会在每一轮遍历的过程中刷新。每一个节点到原点的最短路径是其上一个节点(前驱节点)到原点的最短路径加上前…

2015年8月1日 0条评论 0点热度 阅读全文

十大算法之线性查找:   介绍: BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,依然能达到o(n)的时间复杂 度,五位算法作者做了精妙的处理。 时间复杂度 O(N)   算法步骤:   1. 将n个元素每5个一组,分成n/5(上界)组。 2. 取出每一组的中位数,任意排序方法,比如插入排序。 3.&n…

2015年7月29日 0条评论 0点热度 阅读全文