【数据结构】数据结构大汇总 {数据结构的分类总结：定义和特性、实现方式、操作与复杂度、适用场景、相关算法、应用实例}

一、线性结构

1.1 顺序表

1. 定义和特性：顺序表是一种线性表的存储结构，它采用一段地址连续的存储单元依次存储线性表中的元素。顺序表具有随机访问的特性，即可以通过元素的下标直接访问元素。

2. 实现方式：顺序表可以通过数组来实现，数组的下标即为顺序表中元素的位置。实现方式简单高效，支持常数时间的随机访问。

3. 操作与复杂度：顺序表支持基本的插入、删除、查找等操作。其中，随机访问的时间复杂度为O(1)，顺序查找的时间复杂度为O(n)，插入和删除操作的时间复杂度为O(n)。顺序表的空间复杂度为O(n)。

4. 适用场景：顺序表适用于元素个数固定或变化不大的情况，以及需要经常进行随机访问而不太频繁插入和删除操作时效果较好。由于对内存的连续性要求，对于较大的动态数据集合，可能需要频繁扩展内存并进行数据移动，会影响性能。

5. 相关算法：顺序表的算法包括顺序查找、二分查找等，这些算法可以利用顺序表的特性进行实现，提高查找效率。

6. 应用实例：顺序表广泛应用于程序开发中，例如在一些编程语言中的数组就是采用顺序表的方式实现的。在内存中，数组也是一种顺序表的典型表示方式。

【数据结构和算法】顺序表（动态顺序表、头插、尾插、任意位置插入、头删、尾删、任意位置删除、遍历查找、二分查找）_顺序表头部插入-CSDN博客

1.2 链表

1. 定义和特性：链表是一种线性表的存储结构，它由一系列节点组成，每个节点包含数据元素和指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表等不同类型。链表的特点是不要求内存空间连续，可以动态地分配和回收内存，因此适用于频繁插入和删除的场景。

2. 实现方式：链表通过节点之间的指针来实现元素之间的连接。每个节点包含一个数据元素和一个指向下一个节点的指针（双向链表还包含指向前一个节点的指针）。链表的实现方式相对灵活，可以随时动态改变链表的结构。

3. 操作与复杂度：链表支持基本的插入、删除、查找等操作。插入和删除操作的时间复杂度为O(1)，查找操作的时间复杂度为O(n)。链表的空间复杂度为O(n)，每个节点需要额外的存储空间来存储指针。

4. 适用场景：链表适用于频繁插入和删除操作的场景，以及对内存空间要求不连续的场景。在实际应用中，例如在实现队列、栈、哈希表等数据结构时，常常会使用链表来实现。

5. 相关算法：链表的相关算法包括反转链表、合并两个有序链表、检测链表是否有环等。这些算法都是基于链表特性的实现，对于某些问题提供了较为高效的解决方案。

6. 应用实例：链表广泛应用于计算机科学中，例如在操作系统中的进程调度、在数据库中的存储结构、在图形学中的多边形表示等都有链表的影子。此外，许多编程语言的标准库中也包含了链表的实现。

【数据结构和算法】链表（顺序表 VS 链表、8种链表结构、单链表、双向链表）-CSDN博客

【数据结构和算法】单链表（无头单向非循环链表、单链表的增、删、查、改等基本操作、单链表的图形表示、带哨兵位的单链表）_带哨兵的单链表的示意图-CSDN博客

【数据结构和算法】双向链表（带头双向循环链表、“增、删、查、改”基本操作）_循环双链表的插入删除-CSDN博客

1.3 栈 & 队列

1. 定义和特性：

   • 栈（Stack）是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入（入栈）和删除（出栈）操作。

   • 队列（Queue）是一种先进先出（FIFO）的数据结构，允许在队列的一端插入元素（入队），另一端删除元素（出队）。

2. 实现方式：

   • 栈可以使用数组或链表来实现。数组实现的栈称为顺序栈，链表实现的栈称为链式栈。

   • 队列同样可以使用数组或链表来实现。数组实现的队列称为顺序队列（循环队列），链表实现的队列称为链式队列。

3. 操作与复杂度：

   • 栈的基本操作包括入栈和出栈操作。入栈和出栈的时间复杂度均为O(1)。

   • 队列的基本操作包括入队和出队操作。入队和出队的时间复杂度均为O(1)。

4. 适用场景：

   • 栈适用于需要后进先出的场景，例如函数的调用栈、表达式求值、括号匹配等。

   • 队列适用于需要先进先出的场景，例如任务调度、消息传递等。

5. 相关算法：

   • 栈的相关算法包括中缀表达式转后缀表达式、非递归函数的实现、深度优先搜索等。

   • 队列的相关算法包括广度优先搜索、实现缓存、任务调度等。

6. 应用实例：

   • 栈的应用场景包括浏览器的历史记录、编辑器的撤销操作、系统调用的存储等。

   • 队列的应用场景包括消息队列、生产者消费者模式、打印任务队列等。

【数据结构和算法】栈和队列_-CSDN博客

1.4 双端队列

1. 定义和特性：在C++ STL（Standard Template Library）中，deque（双端队列）是一种动态数组，类似于 vector，但它允许在队列的任意一端进行插入和删除操作。deque可以根据需要动态增长和收缩。

2. 实现方式：deque在内部使用了一片连续的存储空间，并使用分段连续内存块的方式来实现。每个内存块中包含多个元素，并且内存块之间通过指针进行链接，形成一个链式结构。这种实现方式使得在队头和队尾进行插入和删除操作的时间复杂度都是O(1)。

3. 操作与复杂度：deque支持的基本操作包括在队头插入元素（push_front）、在队尾插入元素（push_back）、在队头删除元素（pop_front）、在队尾删除元素（pop_back）、获取队头元素（front）和获取队尾元素（back）等。这些操作的时间复杂度都是O(1)。

4. 适用场景：deque适用于需要在队列的两端高效地进行插入和删除操作的场景。与vector相比，deque在队头插入和删除元素的性能更好。例如，在需要频繁地在队头和队尾进行插入和删除操作的情况下，使用deque可以提高效率。

5. 相关算法：deque可以与其他算法结合使用，例如排序算法、搜索算法等。在排序算法中，可以使用deque作为临时存储空间，进行归并排序等操作。在搜索算法中，可以使用deque作为搜索路径的存储结构。

6. 应用实例：deque在实际应用中有广泛的应用，例如实现栈和队列、实现滑动窗口等。在实现栈和队列时，可以使用deque作为底层数据结构，实现在队头和队尾进行插入和删除操作。在滑动窗口算法中，可以使用deque来存储窗口中的元素，并进行插入和删除操作，以便高效地计算窗口内的特定结果。

【STL】stack & queue & priority_queue {栈，队列，优先级队列的介绍及使用；仿函数/函数对象；容器适配器，双端队列deque}_容器link、队列、栈、优先队列、bitset的使用方法-CSDN博客

---

二、树形结构

2.1 堆

1. 定义和特性：堆（Heap）是一种特殊的树形数据结构，它满足堆属性：对于堆中任意节点i的值都要大于等于（或小于等于）其子树中每个节点的值。根据堆属性的不同，堆可以分为最大堆（每个节点的值大于等于其子节点的值）和最小堆（每个节点的值小于等于其子节点的值）。

2. 实现方式：堆通常使用数组来实现，将父节点和子节点的关系映射到数组的索引上。这种实现方式可以较为高效地进行插入和删除操作，并且能够满足堆的性质。

3. 操作与复杂度：堆主要支持插入元素、删除元素、查找堆顶元素等操作。插入和删除的时间复杂度为O(log n)，其中n为堆中元素的个数。查找堆顶元素的时间复杂度为O(1)。

4. 适用场景：堆适用于需要快速找到最大值或最小值的场景，例如优先级队列、堆排序、定时器事件等。

5. 相关算法：堆的相关算法包括向下调整建堆O(n)、堆排序O(nlogn)、Top k 问题（寻找前k大或前k小的元素）等。

6. 应用实例：堆广泛应用于计算机科学中，例如操作系统的进程调度、网络通信的数据包传输、图算法中的Dijkstra算法等都可能用到堆结构。

【数据结构和算法】树和二叉树（树的概念及结构、二叉树概念及结构）_二叉树和树的结构-CSDN博客

【数据结构与算法】二叉树的顺序结构—堆（堆的基本实现，TopK问题，堆排序）-CSDN博客

2.2 AVL树

1. 定义和特性：AVL树是一种自平衡二叉搜索树，它满足平衡因子的限制：对于AVL树的任意节点，其左子树高度与右子树高度之差的绝对值不超过1。通过维持平衡因子的要求，AVL树能够保持树的高度较小，以提高查找等操作的效率。

2. 实现方式：AVL树的实现方式与普通的二叉搜索树类似，每个节点包含一个关键字和左右子节点的指针。当进行插入或删除操作时，需要通过对节点进行旋转和调整，使树保持平衡。

3. 操作与复杂度：AVL树支持插入、删除、查找等基本操作，这些操作的时间复杂度为O(log n)，其中n为树中节点的数量。由于AVL树的平衡性质，对于平衡的AVL树，查找操作的平均时间复杂度为O(log n)。

4. 适用场景：AVL树适用于需要频繁执行插入、删除和查找操作，并且对查询性能要求较高的场景。例如，在数据库的索引结构、编译器中的符号表、字典等应用中常使用AVL树以提高查询效率。

5. 相关算法：AVL树的相关算法包括插入操作、删除操作、平衡操作等。这些算法通过对树的旋转、调整和重平衡等操作来维持树的平衡性。

6. 应用实例：AVL树在计算机科学中有广泛的应用，例如在数据库系统中用于索引，以提高查询和排序的效率。此外，在编程语言的标准库中，也常常包含AVL树的实现。

【数据结构和算法】二叉树的链式结构（二叉树的创建、销毁；二叉树的前中后序遍历；求二叉树的高度；求二叉树节点、叶子节点、第K层节点的个数；查找二叉树节点；判断是否是完全二叉树）-CSDN博客

【高阶数据结构】二叉搜索树 {概念；实现：核心结构，增删查，默认成员函数；应用：K模型和KV模型；性能分析；相关练习}-CSDN博客

【高阶数据结构】AVL树 {概念及实现；节点的定义；插入并调整平衡因子；旋转操作：左单旋，右单旋，左右双旋，右左双旋；AVL树的验证及性能分析}-CSDN博客

2.3 红黑树

1. 定义和特性：红黑树是一种自平衡的二叉搜索树，它在满足二叉搜索树的性质的同时，引入了颜色标记和一些额外的规则来保持树的平衡。红黑树具有以下特性：

   • 每个节点都有一个颜色，可以是红色或黑色。
   • 根节点是黑色的。
   • 所有NIL结点都是黑色的。（NIL节点即空结点，空树也是红黑树）
   • 如果一个节点是红色的，则它的两个子节点都是黑色的。
   • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2. 实现方式：红黑树的实现方式基于二叉搜索树的基本结构，同时引入颜色标记和旋转操作，以确保树始终保持平衡。在插入或删除节点时，需要对树进行调整，通过变换节点的颜色和进行旋转来维持红黑树的性质。

3. 操作与复杂度：红黑树支持插入、删除、查找等基本操作，这些操作的最坏情况下的时间复杂度为O(log n)，其中n为树中节点的数量。由于红黑树的平衡性质，查找操作的平均时间复杂度也为O(log n)。

4. 适用场景：红黑树适用于需要频繁执行插入、删除和查找操作，并且对平衡性能要求较高的场景。例如在STL中的map和set容器的实现中，通常会采用红黑树作为底层数据结构。

5. 相关算法：红黑树的相关算法包括插入节点、删除节点、旋转操作、颜色翻转等。这些算法通过对节点进行旋转和颜色变换来维护红黑树的平衡性。

6. 应用实例：红黑树在计算机科学中有广泛的应用，如在数据库系统中用于索引、在编程语言的标准库中用于实现map、set等容器等。

【高阶数据结构】红黑树 {概念及性质；红黑树的结构；带头结点的红黑树；红黑树的实现；红黑树插入操作详细解释；红黑树的验证}_红黑树抽象数据结构-CSDN博客

2.4 哈夫曼树

1. 定义和特性：哈夫曼树是一种特殊的二叉树，它是一种最优二叉树，用于编码和解码一组字符。哈夫曼树的特性是：权值越大的节点离根节点越近，而权值越小的节点离根节点越远。这种特性保证了哈夫曼树的前缀码性质，使得编码和解码过程简单高效。

2. 实现方式：哈夫曼树通常通过贪心算法构建。构建过程中，首先创建一个只包含单个字符节点的森林，然后选择两个权值最小的节点合并为一个新的节点，并把新节点的权值设为两个被合并节点的权值之和。重复此过程，直到森林中只剩下一个树，即为哈夫曼树。

3. 操作与复杂度：哈夫曼树的主要操作是构建和编解码。构建哈夫曼树的时间复杂度为O(nlogn)（使用优先级队列选取最小权重的节点），其中n为字符集的大小。编解码的时间复杂度为O(m)（取决于字符在哈夫曼树中的深度），其中m为待编解码的字符串长度。

4. 适用场景：哈夫曼树适用于需要对一组字符进行编码和解码的场景。例如在数据压缩算法中，哈夫曼树被广泛应用于无损压缩，将出现频率高的字符使用较短的编码表示，从而减小文件的大小。

5. 相关算法：哈夫曼树的相关算法包括构建算法（如贪心算法）、编码算法和解码算法。构建算法通过合并节点来构建哈夫曼树，编码算法将字符映射到哈夫曼树上的路径，解码算法通过遍历哈夫曼树来还原字符。

6. 应用实例：哈夫曼树在计算机科学中有广泛的应用。例如，在数据压缩算法中，如ZIP和GZIP等，使用哈夫曼树进行编码和解码以减小文件的大小。此外，在通信领域中，哈夫曼树也被用于数据传输的压缩和解压缩。

终于把哈夫曼树搞明白了(一)_哈夫曼树的引入_哔哩哔哩_bilibili

终于把哈夫曼树搞明白了(二)_什么是哈夫曼树？_哔哩哔哩_bilibili

终于把哈夫曼树搞明白了(三)_如何构造哈夫曼树?_哔哩哔哩_bilibili

终于把哈夫曼树搞明白了(四)_哈夫曼树的应用_哈夫曼编码_哔哩哔哩_bilibili

2.5 B树系列

B树

B+树

B*树

1. 定义和特性：

   • B树：B树是一种自平衡的多路搜索树，其节点可以包含多个子节点。根节点至少有1个键，2个孩子；每个分支节点都包含k-1个键和k个孩子，其中 ceil(m/2) ≤ k ≤ m（ceil是向上取整函数）；所有的叶子节点都在同一层；节点中的键按升序排列，节点当中k-1个键正好是k个孩子包含的元素的值域划分
   • B+树：B+树是在B树基础上做了改进的一种多路搜索树。分支节点的子树指针与关键字个数相同；B+树的分支节点只存储key不存储value，分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层；分支节点中的关键字其实是对应子树中的最小值；所有叶子节点按照键的升序连接起来形成一个有序链表，方便范围查询和遍历。
   • B*树：B*树是在B+树基础上做了改进的一种多路搜索树。B*树对于非叶子节点的分裂不像B+树那样简单地将一半分裂给新节点，将中间键提升到上层节点（最少m/2）。而是在插入过程中如果当前节点满了，就将一部分数据移动到兄弟结点中，如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各移动1/3的数据到新结点（最少2/3m)，以充分利用节点的空间，减少树的深度。

2. 实现方式：B树、B+树和B*树的实现方式相似，基于多路搜索树的结构，节点中的键值对有序排列，并且保持树的平衡性质。在插入或删除节点时，需要对树进行调整，通过节点的分裂或合并来维持树的平衡。

3. 操作与复杂度：这三种树结构的操作包括插入、删除、查找等，具有相似的时间复杂度。对于一棵节点为N，度为M的B树，查找和插入需要最少log{M}N次 ~ 最多log{M/2}N + 1次比较（M/2向上取整）。由于B+树和B*树叶子节点之间建立了有序链表，所以范围查询更加高效。

4. 适用场景：B树（系列）是一种适合外查找的树，他通过提高节点度数、增加关键字个数，来压缩高度、减少查找次数，从而达到减少磁盘I/O操作的目的

5. 相关算法：B树、B+树和B*树的相关算法包括插入、删除、节点分裂和合并等。这些算法通过调整节点的结构来保持树的平衡，并提高树的性能。

6. 应用实例：B树、B+树和B*树在数据库系统、文件系统和操作系统等领域中有广泛的应用。

【高阶数据结构】B树 {B树的概念；B树的实现：节点设计，查找，插入，遍历，删除；B树的性能分析；B+树和B*树；B树的应用}-CSDN博客

2.6 并查集

1. 定义和特性：并查集是一种数据结构，用于管理元素的分组和连接性。并查集中的每个元素都被视为一个节点，可以根据节点间的连接关系将它们分为若干个不相交的集合。并查集具有以下特性：

   • 支持两种操作：查找（find）和合并（union）。
   • 查找操作用于确定元素所属的集合，即找到元素的根节点。
   • 合并操作用于将两个集合合并成一个集合，即将其中一个集合的根节点指向另一个集合的根节点。

2. 实现方式：并查集通常使用数组或树结构来实现。使用数组实现时，可以通过记录每个元素的根节点来表示集合的连接关系。使用树结构实现时，可以使用树的根节点表示集合，并按需连接不相交的集合。

3. 操作与复杂度：并查集支持查找操作和合并操作，这两种操作的时间复杂度都可以达到接近O(1)的水平。这是因为在合并时，可以通过路径压缩和按秩合并等技术来尽量降低树的深度，从而提高查找和合并操作的效率。

4. 适用场景：并查集适用于需要快速判断元素之间连接性的场景，比如在图论中用于判断图的连通性、Kruskal算法中用于最小生成树的构建、集合合并的问题等。

5. 相关算法：并查集的相关算法包括查找操作、合并操作、路径压缩和按秩合并等。这些算法可以有效提高并查集的查询和合并性能。

6. 应用实例：并查集在各种离散数学问题、图论问题和算法设计中有广泛的应用，如Kruskal算法、社交网络中的好友关系判断等。

【高阶数据结构】并查集 {并查集原理；并查集优化；并查集实现；并查集应用}_并查集，10w个人组成的多少个朋友圈-CSDN博客

---

三、哈希结构

3.1 哈希表

1. 定义和特性：哈希表是一种数据结构，通过计算哈希函数，将键映射到存储桶中。它具有快速的查找、插入和删除操作，并且在理想情况下具有常数时间复杂度。哈希表由键值对组成，每个键唯一对应一个值。

2. 实现方式：哈希表内部通常由一个数组和对应的哈希函数组成。哈希函数将键映射到数组的特定位置（存储桶）。在哈希冲突时，通常采用链表、平衡树等方式解决。

3. 操作与复杂度：哈希表支持的基本操作包括插入（put）、查找（get）、删除（remove）等。在理想情况下，这些操作的时间复杂度为O(1)，但在存在哈希冲突时，复杂度可能会退化。

4. 适用场景：哈希表适用于需要快速查找、插入和删除操作，并且键值唯一的场景中。它在处理大规模数据中通常具有很高的性能。

5. 相关算法：哈希表与哈希函数相关联，其设计和优化都与哈希函数密切相关。另外，哈希表也与哈希冲突解决算法相关，如拉链法、线性探测法等。

6. 应用实例：哈希表在实际工程中广泛应用。例如，在编程语言中的哈希表数据结构，用于实现关联数组或字典；在数据库系统中的哈希索引，用于加速数据检索等。

【高阶数据结构】哈希表 {哈希函数和哈希冲突；哈希冲突的解决方案：开放定址法，链地址法；红黑树结构 VS 哈希结构}-CSDN博客

3.2 位图

1. 定义和特性：位图是一种数据结构，它由一个二进制位数组或者比特数组组成，每个位（bit）只能存储 0 或 1。位图通常被用来表示大量整数的集合，通过位的状态来表示该整数是否出现在集合中。位图支持高效的位操作（如按位与、按位或、按位异或等），适合用于高效地存储和操作大量的布尔型数据。

2. 实现方式：位图可以被实现为一个数组，其中每个元素都是一个字节，而每个字节又包含8个位。对于很大的位图，可以使用多个数组进行分段存储。位图通常不仅仅用于表示整数的集合，还可以用于标记某个特定值是否存在。

3. 操作与复杂度：位图支持的基本操作包括设置某一位为 1，清除某一位为 0，或者测试某一位的状态等。因为位图的底层数据结构是二进制数组，所以这些基本操作可以在常数时间内完成。

4. 适用场景：位图通常在需要高效地表示大规模的布尔型数据集合时使用。举例来说，它可以应用于网络流量分析、数据库索引、压缩算法、密码学等领域。

5. 相关算法：位图与位运算相关紧密，通过位运算可以高效地对位图进行操作。这包括与、或、非、异或等操作。另外，位图所涉及的算法还包括位图的压缩算法、位图的搜索算法等。

6. 应用实例：位图在实际工程中有多种应用。例如，在搜索引擎中，位图被用来表示网页的索引；在数据库系统中，位图索引可以用来加速查询操作；在计算机网络中，位图可以用于IP地址的查找。

【高阶数据结构】哈希的其他应用 {位图的介绍及实现，位图的组合应用；布隆过滤器的介绍及实现，布隆过滤器的应用；哈希切分}-CSDN博客

3.3 布隆过滤器

1. 定义和特性：布隆过滤器是一种空间高效的数据结构，用于判断一个元素是否属于一个集合。它由一个位数组和多个哈希函数组成。插入元素时，将元素经过多个哈希函数映射到位数组上；查询元素时，通过同样的哈希函数映射到位数组上，如果所有对应位都为1，则可能存在该元素，如果有一个为0则一定不存在。因此布隆过滤器可能存在一定的误判率。

2. 实现方式：布隆过滤器通常使用一个位数组表示，同时使用多个哈希函数来映射元素到位数组上。当插入元素时，对应的位被标记为1；当查询元素时，检查对应的位，如果所有位都为1，则可能存在该元素。

3. 操作与复杂度：布隆过滤器支持的基本操作包括插入元素和查询元素。插入和查询的时间复杂度都是O(k)，其中k为哈希函数的个数。布隆过滤器的空间复杂度与位数组的大小有关，但通常情况下是与预期容量和误判率相关的。

4. 适用场景：布隆过滤器适合用于处理大量数据集合的成员关系查询，并且可以容忍一定的误判率。它在缓存、数据库查询、垃圾邮件过滤等领域有广泛的应用。

5. 相关算法：布隆过滤器涉及的算法主要是哈希函数的选择和位数组的操作。另外，还有一些改进的布隆过滤器，如Counting Bloom Filter和Scalable Bloom Filter等。

6. 应用实例：布隆过滤器在实际工程中有多种应用。例如，网络路由器使用布隆过滤器来快速决定一个给定IP地址是否合法；在分布式系统中，布隆过滤器可以用于降低分布式缓存中的缓存穿透问题。

【高阶数据结构】哈希的其他应用 {位图的介绍及实现，位图的组合应用；布隆过滤器的介绍及实现，布隆过滤器的应用；哈希切分}-CSDN博客

---

四、图形结构

4.1 概括总结

1. 定义和特性：图是一种由节点（顶点）和节点之间的连接（边）组成的数据结构。图可以表示各种关系和网络结构，比如社交网络、道路网络等。图可以是有向的（边有方向）或无向的（边没有方向），可以是带权的（边有权值）或无权的（边没有权值）。

2. 实现方式：图可以用多种方式来实现，常见的方式有邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中数组的行和列代表图中的节点，矩阵中的元素表示节点之间的连接关系；邻接表是使用链表或数组来表示每个节点的邻居节点。

3. 操作与复杂度：图支持的基本操作包括添加节点和边、删除节点和边、查找节点和边等。图的操作复杂度取决于具体的实现方式和操作类型。

4. 适用场景：图是用于表示和解决各种复杂关系和网络问题的重要数据结构。它在网络分析、推荐系统、路径规划等领域有广泛的应用。

5. 相关算法：图涉及的算法包括最短路径算法（如Dijkstra算法、Bellman-Ford算法）、最小生成树算法（如Prim算法、Kruskal算法）、图遍历算法（如深度优先搜索和广度优先搜索）等。

6. 应用实例：图在实际工程中有多种应用。例如，在社交网络中，图可以用于表示用户之间的关系；在地图导航系统中，图可以用于表示道路网络和计算最短路径。

【高阶数据结构】图 {图的基本概念；图的存储结构：邻接矩阵，邻接表；图的遍历：BFS，DFS}-CSDN博客

4.2 图遍历算法

图遍历算法是用于在图结构中访问和处理所有节点的算法。常见的图遍历算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

1. 深度优先搜索（DFS）:

   • DFS是一种用于图遍历的算法，它从起始节点开始，一直沿着路径直到到达最深的节点，然后再回溯到上一个节点，继续探索下一个路径。DFS可以通过递归或者使用栈来实现。
   • 优点：实现简单，适用于寻找连通分量、拓扑排序等任务。
   • 缺点：不一定能得到最短路径，可能会陷入深层次的路径，不适合用于寻找最短路径的问题。

2. 广度优先搜索（BFS）:

   • BFS是一种用于图遍历的算法，它从起始节点开始，首先访问其所有相邻节点，然后再依次访问这些相邻节点的邻居节点。BFS可以使用队列来实现。
   • 优点：能够搜索最短路径，适用于寻找最短路径的问题。
   • 缺点：需要额外的空间来存储节点的信息，实现稍微复杂一些。

【高阶数据结构】图 {图的基本概念；图的存储结构：邻接矩阵，邻接表；图的遍历：BFS，DFS}-CSDN博客

4.3 最小生成树算法

最小生成树算法主要有Prim算法和Kruskal算法两种。

1. Prim算法：

   • 从任意一个顶点开始，将其加入生成树中。
   • 选择与生成树相连的最短边，将其连接的顶点加入生成树中。
   • 重复以上步骤，直到所有顶点都已加入生成树为止。

2. Kruskal算法：

   • 将所有边按照权值从小到大进行排序。
   • 依次取出权值最小的边，若该边连接的两个顶点不在同一连通分量中，则将其加入生成树中。
   • 重复以上步骤，直到生成树中包含了所有顶点。

这两种算法都是贪心算法，通过不断选择当前状态下的最优解来构建最小生成树。它们的时间复杂度分别为O(V^2)和O(ElogE)，其中V为顶点数，E为边数。在实际应用中，选取合适的算法取决于图的规模和边的数量等因素。

【高阶数据结构】图 {最小生成树：Kruskal算法，Prim算法；最短路径：Dijkstra算法，Bellman-Ford算法，Floyd算法}-CSDN博客

4.4 最短路径算法

最短路径算法主要有Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法三种。

首先初始化两个数组，一个用来存储源点和任意顶点之间的最短路径的父节点，一个用来存储最短路径的长度。

1. Dijkstra算法（单源）：
   • 从起始顶点开始，将其加入已访问的顶点集合，并初始化起始顶点到其他顶点的距离。
   • 选择与起始顶点直接相连的顶点中距离最短的顶点，将其加入已访问的顶点集合。
   • 更新起始顶点到其他顶点的距离，若经过当前已访问的顶点到其他顶点的距离比原先的距离短，则更新距离。
   • 重复以上步骤，直到所有顶点都已加入已访问的顶点集合。
2. Bellman-Ford算法（单源）：
   • 初始化距离数组，将起始顶点的距离设置为0，其余顶点的距离设置为无穷大。
   • 通过对所有边进行|V|-1次松弛操作，其中|V|为顶点的数量。
   • 检查每条边的两个顶点，如果经过当前边可以获得更短的路径，则更新路径长度。
   • 最后再次遍历所有边，检查是否存在负权回路。
3. Floyd-Warshall算法（多源）：
   • 初始化两个二维数组，一个用来存储任意两个顶点之间的最短路径的父节点，一个用来存储最短路径的长度。
   • 通过三重循环，逐步尝试将中间顶点纳入考虑，即假设中间顶点k是当前考虑的点，则对于任意两个顶点i和j，如果通过顶点k可以使得从i到j的路径长度变短，则更新dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
   • 重复以上操作直到所有顶点都被考虑为中间节点为止。最终得到一个二维数组，其中存储了任意两个顶点之间的最短路径距离。

Dijkstra算法和Bellman-Ford算法适用于单源最短路径问题，它们的时间复杂度分别为O(V^2)和O(V*E)，其中V为顶点数，E为边数，Bellman-Ford算法的性能较Dijkstra算法略差，但是它可以处理带有负权边的图，并且能够检测负权回路。Floyd-Warshall算法适用于多源最短路径问题，它的时间复杂度为O(V^3)，其中V为顶点数。选择合适的算法取决于具体的问题需求和图的规模等因素。

【高阶数据结构】图 {最小生成树：Kruskal算法，Prim算法；最短路径：Dijkstra算法，Bellman-Ford算法，Floyd算法}-CSDN博客

4.5 有向无环图的应用

有向无环图的应用—描述表达式、AOV网、拓扑排序、AOE网、关键路径-CSDN博客

图-拓扑排序_哔哩哔哩_bilibili

图-AOE网和关键路径_哔哩哔哩_bilibili

怎么求关键路径？先求点，再求边

源点和汇点的ve, vl相等，工程的开始和结束不能拖延

求ve：先将所有事件的ve初始化为源点的ve(0)，按照拓扑序从源点求到汇点，其他事件的ve取所有路径活动最早开始时间的最大值（所用时间的最大值），因为要保证所有的活动都完成事件才能发生。

求vl：先将所有事件的vl初始化为汇点的vl(ve)，按照逆拓扑序从汇点求到源点，其他事件的vl取所有路径活动最晚开始时间的最小值（结束时间-所用时间的最大值），因为要保证所有路径活动都有足够的时间完成。

求e：活动的最早开始时间就是开始事件的最早开始时间。

求l：活动的最晚开始时间就是结束事件的最晚开始时间-活动所用时间。

关键活动：e和l相等的活动

关键路径：由关键活动连接而成的路径，耗时最长的路径。关键路径可能不是唯一的。

时间余量：每个活动的最晚开始时间l - 最早开始时间e = 时间余量；表示该活动可以拖延的时间。关键活动的时间余量是0，是不能拖延的活动。

---

五、其他

5.1 跳表

1. 定义和特性：跳表是一种有序的数据结构，是一种空间换时间的设计思想。跳表通过添加多层索引来加速查询操作，使得查询的时间复杂度接近于O(log n)。在一层索引中，每个节点都具有指向同层下一个节点的指针。跳表可以用于替代有序链表和平衡二叉树，它在某些情况下比平衡二叉树的查询操作更快。

2. 实现方式：跳表由一个有序链表组成，同时使用多层索引来加速查询操作。每一层索引都是原始链表的一个子集，且节点之间的链接关系保持有序。通过增加层数，跳表的查询效率逐渐提高。

3. 操作与复杂度：跳表支持的基本操作包括插入、删除和查询。在跳表中插入和删除一个元素的时间复杂度为O(log n)，其中n为跳表中的元素个数。查询操作的时间复杂度也为O(log n)。

4. 适用场景：跳表适用于需要高效的查询操作，并且对添加和删除操作的效率要求相对较低的场景。跳表在Redis等内存数据库中经常被使用来提高查询效率。

5. 相关算法：跳表涉及的算法主要是层级索引的建立和维护。常见的一种算法是跳表的插入算法，它通过随机生成层数来建立索引，使得查询操作的效率更高。

6. 应用实例：跳表在实际工程中有多种应用。例如，在区块链技术中，跳表可以用于实现快速的交易确认；在网络中，跳表可以用于路由表的构建和维护。

【高阶数据结构】跳表 {什么是跳表-skiplist；skiplist的效率如何保证；skiplist的实现；skiplist跟平衡搜索树和哈希表的对比}-CSDN博客