图算法系列之计算图中最短路径在前面两篇中我们通过深度优先搜索可以从图中找出一条通过顶点v到顶点w的路径,但是深度优先搜索与顶点的输入有很大的关系,找出来的路径也不一定是最短的,通常情况下我们很多时候需要找出图中的最短路径,比如:地图功能。这里我们就需要使用到广度优先搜索算法

图算法系列之深度优先搜索(一)在开始实现算法之前,我们依然先来定义搜索的API1. 构造方法提供了一个图对象,以及一个起点s,需要找到与s连通的所有顶点2. marked判断顶点s与v是否相邻3. count返回与顶点s相连的总顶点数

图算法系列之无向图的数据结构图用什么数据结构来表示主要参考两个要求:1. 在开发图的相关算法时,图的表示的数据结构是基础,所以这种数据结构效率的高2. 在实际的过程中图的大小不确定,可能会很大,所以需要预留出足够的空间考虑了这两个要求之后大佬们提出以下三个方法来供选择

基于拉链式和线性探测式散列表实现Map## 散列函数实现散列表的第一步就是需要考虑如何把一个键转换为数组的下标,这时候就需要使用到散列函数,先把键值转换成一个整数然后在使用**除留余数法**计算出数组的下标。**每种类型的键我们都需要一个不同的散列函数。**

硬核图解红黑树并手写实现 性质1. 结点是红色或黑色。(why:为什么节点要区分颜色,红色节点的作用是什么?)* 性质2. 根结点是黑色。(why:为什么根节点必须是黑色)* 性质3. 所有叶子都是黑色。(why)* 性质4. 从每个叶子到根的所有路径上不

基于二叉树实现Map 使用二叉树实现的Map运行的效率取决于树的形状,而树的形状取决于数据输入的顺序;最好的情况下二叉树是平衡的,那么get、put的时间复杂度都是log(N); 但是如果插入的数据是有序的,那么二叉树就会演变成链表,那么get、put的性能将会大大减低;

基于数组或链表实现Map 虽然JAVA中已经提供了很多Map的实现,为了学习并掌握常用的数据结构,本篇主要是通过数组和链表两种方式实现,之后提供二叉树,红黑树,散列表的版本实现。通过自己手写各个版本的Map实现,掌握每种数据结构的优缺点,可以在实际的工作中根据需要选择适合的Map

图解堆排序 堆排序的过程主要有两个阶段:* 把原始数据构造成一个有序堆(构造堆)* 从堆中按照递减顺序取出所有元素就可以得到排序结果(下沉排序),假如我们从构建好的优先级队列中持续调用删除最小(或者最大),把结果输出到另一个数组中,那么就可以把数组的所有元素进行排序

原来实现优先级队列如此简单假如你设计的事件系统中有很多的事件,每个事件都定义了不同的权重值,系统需要优先处理权重较高的事件优先级队列是一种抽象的数据结构,我们依然可以基于前面我们使用到的队列API来修改;需要了解之前的队列的实现可以查看《面试的季节到了,老哥确定不来复习下数据结构吗》