1. 迪杰斯特拉(Dijkstra)算法: 1. 定义概览 Dijkstra(迪杰斯特拉) 算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。 主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。 问题描...

拓扑排序 1. 什么是拓扑排序: 在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件： 每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有...

转载自: [勿在浮沙筑高台] 连通图：在无向图中，若任意两个顶点$v_{i}$与$v_{j}$都有路径相通，则称该无向图为连通图。 强连通图：在有向图中，若任意两个顶点$v_{i}$与$v_{j}都有路径相通，则称该有向图为强连通图。 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树：一个连通图的生成树...

图的深度优先遍历(DFS) 深度优先搜索（depth-first search）是对先序遍历（preorder traversal）的推广。我们从某个顶点 v 开始处理 v，然后递归地遍历所有与 v 邻接的顶点。 实现思想： 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去，当节点 v 的所有边都已被探寻过，探索将回溯到发现节点 v...

概念: 图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。 无边图：若顶点$V_{i}$到$V_{j}$之间的边没有方向，则称这条边为无项边(Edge), 用序偶对$(V_{i},V_{j})$标示。 对于下图无向图G1来说，G1=(V1, {E1})，其中顶点集合V1={A,B,C,D}; 边...

介绍: 红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对数时间内完成查找的数据结构。这个时候，红黑树站了出来。 红黑树是在普通二叉树上，对每个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质: 每个节点或者是...

转载自:B-树的详解 - CSDN博客 B 树: 1.背景 磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候...

背景: AVL(Adelson-Velskii和Landis发明者的首字母)树 是带有平衡条件的二叉查找树。 二叉查找树的性能分析： 在一颗左右子树高度平衡情况下，最优的时间复杂度为$O(log_{2}{n})$，这与这半查找相同； 在一个只有右子树的二叉树中，最差的时间复杂度会脱变为线性查找$O(n)$。 由于二叉查找树存在以上问题，所以AVL树通过旋转使自身始...

二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为 $key[x]$。 如果y是x的左子树中的一个结点，则 $key[y] <= key[x]$; 如果y是x的右子树的一个结点，则 $key[y] >= key[x]$。 说明: 若任意节点的左子树不空，则左子树上所有结点...

概念： 二叉树的遍历分为以下三种: 先序遍历：遍历顺序规则为【根左右】 中序遍历：遍历顺序规则为【左根右】 后序遍历：遍历顺序规则为【左右根】 举个例子，看下图: 先序遍历：ABCDEFGHK 中序遍历：BDCAEHGKF 后序遍历：DCBHKGFEA 编程实现方式: 三种方法中，递归最为简单，栈次之，循环最为麻烦。递归的深度如果太大则会导致栈溢出；栈的方式需要额外的...

定义: 1. 节点的类型: 在非空二叉树中，第i层的结点总数最大为$2^{i}-1,i\ge1$（满树情况） 深度为h的二叉树最多有 $2^h-1, h\ge1$ 个结点，最少有$h$个结点 对于任意一棵二叉树，设其总结点数为$N$，如果其叶结点(度为0的结点）数为$N_0$，而度数为2的结点总数为$N_2$，则$N_0=N_2+1$，度为1的结点数$N_1=N-N_0-N...

转载自 : 树的三种存储结构 - CSDN博客 定义 树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。 在任意一棵非空树中: 有且仅有一个特定的称为根(Root)的结点; 当n>1时，其余结点可分为m(m>O)个互不相交的有限集$T_1,T2,…,T_m$，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)，如图...

线性表是一种典型的线性结构。 线性表的顺序实现 顺序表是线性表的顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素. 顺序表具备如下两个基本特征： 顺序表中的所有元素所占的存储空间是连续的； 顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的。 假设顺序表的每个元素需占用$K$个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则顺...

栈: 栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶(TOP)，另一端为栈底(BOTTOM)。 当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素，从而也是最先被移除(出栈)的元素；栈底元素总是最先被插入的元素，从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构 栈的基本运算有三种：入栈、出栈与读栈顶，时间复杂度都是O(...

串的存储表示和实现: 串是一种特殊的线性表,其存储表示和线性表类似但又不完全相同。串的存储方式取决于将要对串所进行的操作. 串在计算机中有3种表示方式: 定长顺序存储方式: 将串定义成字符数组,利用串名可以直接访问串值。用这种表示方式,串的存 储空间在编译时确定,其大小不能改变。 堆分配存储方式: 仍然用一组地址连续的存储单 元来依次存储串中的字符序列...

简要