Loading...
最小生成树之前学习的加权图,我们发现它的边关联了一个权重,那么我们就可以根据这个权重解决最小成本问题,但是如何才能找到最小成本对应的顶点和边呢?最小生成树相关算法就可以解决最小生成树定义及相关约定定义:图的生成树是它的一棵含有其所有顶点的无环连通子图,一副加权无向图的最小生成树它的一棵权值(树中所有边的权重之和)最小的生成树约定:只考虑连通图,最小生成树的定义说明它只能存在于连通图中,如果图...
有向图在实际生活中,很多应用相关的图都是有方向性的,最直观的就是网络,可以从A页面通过链接跳转到B页面,那么a和b连接的方向是a->b,此时我们就需要使用有向图来解决这类问题,它和我们之前所学习的无向图,最大的区别就在于连接是具有方向的,在代码的处理上也会有很大的不同有向图的定义及相关术语定义:有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连接着一对有序...
图的入门图的实际应用在现实生活中,有许多应用场景会包含很多点以及点点之间的连接,而这些应用场景我们都可以用即将要学习的图这种数据结构去解决地图:我们生活中经常使用的地图,基本上是由城市以及连接城市的道路组成,如果我们把城市看做是一个一个的点,把道路看做是一条一条的连接,那么地图就是我们将要学习的图这种数据结构电路图:下面是一个我们生活中经常见到的集成电路板,它其实就是由一个又一个触点组成的,...
B-树前面我们已经学习了二叉查找树,2-3树以及它的实现红黑树,2-3树中,一个节点最多能有两个key,它的实现在红黑树中是用对链接染色的方式去表达这两个key,接下来我们学习另外一种树形结构B树,这种数据结构中,一个节点允许多于两个key的存在B树是一种树状数据结构,它能够存储数据,对其进行排序并允许以$O(logn)$的时间复杂度进行查找,顺序读取,插入和删除等操作B树的特性B树中允许一...
平衡树之前我们学习过二叉查找树,发现它的查询效率比单纯的链表和数组的查询效率要高很多,大部分情况下,确实是这样的,但不幸的是,在最坏情况下,二叉查找树的性能还是很糟糕的例如我们依次往二叉树中插入$9,8,7,6,5,4,3,2,1$这$9$个数据,那么最终构造出来的树是长成下面这个样子我们可以发现,如果我们要查找$1$这个元素,查找的效率依旧会很低,效率低的原因就是在于这个树并不平衡,全部是...
