学校专业建设备案网站,建网站的公司价格,商家入驻的商城平台,怎样在工商局网站做公示目录 一、计算机数据结构基本概念理解#xff1a;1. 数组基本概念优缺点以及如何改进常用的操作底层实现还有哪些容易问到的问题#xff1a;关于数组的一些衍生数据结构和算法问题 2. 链表基本概念#xff1a;链表的节点是什么#xff1f;每个节点包含哪些信息#xff1f;… 目录 一、计算机数据结构基本概念理解1. 数组基本概念优缺点以及如何改进常用的操作底层实现还有哪些容易问到的问题关于数组的一些衍生数据结构和算法问题 2. 链表基本概念链表的节点是什么每个节点包含哪些信息常用操作链表的底层实现优缺点链表与其他数据结构的区别插入和删除操作的时间复杂度单链表和双链表循环列表应用场景有可能的其他问题 3. 栈 (Stack)基本概念常用操作底层实现优缺点可能问的问题栈的应用场景栈与其他数据结构的比较使用栈时可能会遇到的一些问题 4. 队列 (Queue)基本概念常用操作及时间复杂度底层实现优缺点面试中可能会遇到的问题 5. 树 (Tree)基本概念常用操作和时间复杂度底层实现原理优缺点可能会问到的问题 6. 图 (Graph) 今日任职要求 深刻理解计算机数据结构和算法设计熟悉C/C/Python等编程语言有良好的编程功底。 一、计算机数据结构
基本概念理解
面试官可能会问及你对数据结构的基本概念的理解例如数组、链表、栈、队列、树、图等。
1. 数组
基本概念
数组是一种线性数据结构由相同类型的元素按顺序排列而成通过索引来访问每个元素。在内存中数组的元素是连续存储的。
优缺点以及如何改进
优点随机访问效率高时间复杂度为O(1) 。空间效率高占用内存是连续的不会存在额外的存储空间的浪费。缺点大小固定无法动态扩展或缩小。插入和删除操作低效时间复杂度为O(n)。如果申请了一大段空间结果只有几个元素那么会浪费内存空间。如何改进 使用动态数组动态的调整数组的大小底层使用了一个固定大小的数组但是可以根据需要动态扩展数组。使用链表可以高效的进行插入和删除操作但是在访问效率上不如数组。预分配内存如果知道数组可能的最大大小可以在创建数组时预分配足够的内存空间避免频繁的动态扩展操作从而减少内存空间的浪费。使用STL标准库容器C 标准库提供了丰富的容器如 vector 或 list 等它们在数组的基础上进行了封装并提供了更加灵活和高效的操作可以根据需求选择合适的容器来使用。
常用的操作
由于方便表示时间复杂度下面省略了“” 例O(1- O1 访问元素O1 插入在尾部插入O1在中间或者是开头插入On 删除中间或开头元素On删除尾部元素O1
底层实现
在底层数组的元素在内存中是连续存储的通过索引可以直接计算出元素的内存地址因此可以实现快速的随机访问。
还有哪些容易问到的问题
如何定义和声明数组
静态数组在编译时就确定了数组的大小大小不可以改变。
// 声明一个包含5个整数的数组
int arr[5];// 初始化并声明一个包含5个整数的数组
int arr[5] {1, 2, 3, 4, 5};动态数组可以在运行时确定数组的大小大小可变。
// 使用 new 关键字动态分配一个包含5个整数的数组
int *arr new int[5];// 初始化并使用 new 关键字动态分配一个包含5个整数的数组
int *arr new int[5]{1, 2, 3, 4, 5};// 删除动态分配的数组
delete[] arr;静态数组在声明的时候可以不指定数组的大小吗? 静态数组在声明的时候必须指定数组的大小。这是因为在编译时编译器需要知道数组的大小以便为其分配内存空间。因此静态数组的大小必须是一个常量表达式。 如果想在声明数组时不指定大小可以使用动态数组或者使用 C 标准库提供的容器类如 vector。这些容器类可以在运行时动态地调整大小而不需要在编译时就指定大小。 数组的特点是什么 数组在内存中是连续存储的具有连续存储的空间数组大小在声明时确定元素都是相同的数据类型随机访问高效的内存访问因为是连续存储所以可以利用局部性原理通过缓存预取和预读取技术来提高内存的访问效率不支持动态增删操作简单高效。 如何访问数组中的元素时间复杂度是多少 要访问数组中的元素可以通过索引来直接访问。索引是一个整数值用于指示数组中的特定元素的位置。数组的第一个元素通常具有索引 0第二个元素具有索引 1以此类推。
int array[5] {10, 20, 30, 40, 50};
int element array[2]; // 访问索引为2的元素即数组中的第三个元素其值为30时间复杂度为O1即常数时间复杂度。
如何在数组中插入和删除元素对时间复杂度的影响是什么
插入元素 在末尾插入元素 如果数组未满直接在数组末尾插入新元素即可时间复杂度为 O(1)。 如果数组已满则需要进行扩容操作将原数组的元素复制到新的更大的数组中并在末尾插入新元素时间复杂度为 O(n)。 在中间或开头插入元素 需要先将插入位置后面的元素向后移动腾出空间插入新元素时间复杂度为 O(n)。
删除元素 删除末尾元素 直接删除末尾元素时间复杂度为 O(1)。 删除中间或开头元素 需要将删除位置后面的元素向前移动填补删除位置时间复杂度为 O(n)。 时间复杂度的影响 在数组中插入或删除元素通常需要移动其他元素移动的元素数量与数组中元素的个数和插入/删除位置有关因此时间复杂度为 O(n)。特别地如果在末尾插入或删除元素时间复杂度为 O(1)因为不需要移动其他元素。
多维数组
定义和访问多维数组 多维数组是指数组的元素也是数组的数组即数组的每个元素都是一个数组。在 C 中可以使用以下语法来定义和访问多维数组
// 定义一个二维数组
int arr[3][3] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
// 访问多维数组中的元素
int element arr[1][2]; // 访问第二行第三列的元素其值为 6在内存中的存储 多维数组在内存中是按行存储的即连续的内存块中存储每行的元素。例如对于二维数组 arr[3][3] 内存中的存储结构如下
1 2 3 4 5 6 7 8 9
//计算元素的地址
//可以使用数组的索引来计算元素的地址。对于二维数组元素的地址可以通过以下公式计算
//地址 首地址 行号 × 列数 列号数组与指针
数组名与指针的区别和关系 数组名是数组的首地址指向数组的第一个元素。 指针是一个变量存储另一个变量的地址。数组名作为指针使用 数组名可以像指针一样进行运算和操作如取地址、解引用等。将数组传递给函数 数组名作为函数参数传递时传递的是数组的首地址。 也可以将指针作为函数参数传递来实现对数组的操作。
数组的应用场景
适合使用数组的情况【简记需要用到数组特点和优点的地方如随机访问】 需要按顺序存储大量相同类型的数据时。 需要频繁随机访问元素。应用场景举例 存储学生的成绩列表。 存储图像的像素数据。【多维数组】常见算法和数据结构中的应用 在排序算法中如快速排序和归并排序中使用数组存储数据。 在图的邻接矩阵表示中使用二维数组存储顶点之间的关系。
数组的扩展和改进
动态数组 使用动态内存分配来实现数组的动态扩展如 std::vector。时间复杂度 动态数组的插入和删除操作的时间复杂度为 O(n)。动态扩容和收缩 动态数组会根据需要自动进行扩容当元素数量达到容量上限时会重新分配更大的内存空间并将原来的元素复制过去。 注意在扩容和收缩过程中可能会有额外的内存分配和数据复制开销。找到最大值、最小值、平均值等 遍历数组找到最大值、最小值并累加计算平均值。排序算法的实现 实现常见的排序算法如冒泡排序、快速排序等。数组与其他数据结构的比较 与链表的比较 数组适合于随机访问和占用连续内存的场景而链表适合于频繁插入和删除操作的场景。 与哈希表的比较 数组适合于需要快速访问的场景而哈希表适合于需要高效查找的场景且具有动态调整大小的能力。
关于数组的一些衍生数据结构和算法问题
数据结构
动态数组 实现动态扩容的数组可以根据需要动态增加或减少大小例如 C 中的 std::vectorvector 在需要时会动态地分配内存并复制元素以支持动态调整大小。多维数组 在一维数组的基础上扩展可以表示多维空间的数组例如二维数组、三维数组等。稀疏数组 存储大部分元素为默认值的数组只存储非默认值的元素及其索引通常使用压缩存储方式来节省空间例如 int arr[M][N]其中 M 和 N 分别表示多维数组的行数和列数。常见的稀疏矩阵的常见存储格式COOCoordinate List、CSRCompressed Sparse Row、CSCCompressed Sparse Column。 - COO COO 格式使用三个数组来表示稀疏矩阵行坐标数组、列坐标数组和数值数组。 - CSR CSR 格式使用三个数组来表示稀疏矩阵值数组、列索引数组和行偏移数组。 - CSC CSC 格式与 CSR 格式类似但是存储方式略有不同。它使用三个数组来表示稀疏矩阵值数组、行索引数组和列偏移数组。循环数组 通过循环利用数组空间实现的队列或者栈例如实现循环队列、循环缓冲区等。循环数组通常使用头指针和尾指针来标识队列或栈的头部和尾部位置通过取模运算来实现环形循环。
算法
搜索算法 线性搜索 逐个遍历数组元素进行搜索。最好首位O1最坏在尾部On平均情况On。优点是简单适用于小型数据集或未排序的数组缺点是时间复杂度高、需要遍历所有元素。使用场景数据量小不需要频繁搜索的情况数组未排序或无法利用其特定属性进行高效搜索的情况仅需要搜索一次或搜索次数不多的情况。二分搜索 仅适用于有序数组通过对数组进行分割来快速定位目标元素。
算法步骤
1. 初始化左指针 left 和右指针 right分别指向数组或列表的起始位置和结束位置。
2. 在每一次循环中计算中间位置 mid (left right) / 2。
3. 如果目标元素等于中间元素则返回中间元素的索引。
4. 如果目标元素小于中间元素则将右指针移动到中间元素的左侧right mid - 1。
5. 如果目标元素大于中间元素则将左指针移动到中间元素的右侧left mid 1。
6. 继续以上步骤直到找到目标元素或左指针大于右指针。排序算法见常考算法篇~ 冒泡排序、插入排序、选择排序 基于比较的简单排序算法。 快速排序、归并排序、堆排序 基于分治思想的高效排序算法。 计数排序、桶排序、基数排序 非比较排序算法适用于特定范围的整数。查找算法见常考算法篇~ 线性查找 逐个遍历数组元素进行查找。 二分查找 仅适用于有序数组通过对数组进行分割来快速定位目标元素。旋转和翻转
数组旋转 将数组中的元素进行向左或向右循环移动。旋转操作的步长可以是任意的正整数。 向左旋转 将数组中的元素向左循环移动 k 步即将数组中的元素依次向左移动 k 位移出数组的元素重新放回到数组的末尾。向右旋转 将数组中的元素向右循环移动 k 步即将数组中的元素依次向右移动 k 位移出数组的元素重新放回到数组的开头。 数组翻转 将数组中的元素顺序颠倒。两个指针一前一后互相交换。
子数组问题 最大子数组和 寻找数组中和最大的连续子数组。 乘积最大子数组 寻找数组中乘积最大的连续子数组。数组操作 数组元素去重 移除数组中的重复元素。 数组元素移除 移除数组中指定的元素。其他算法 数组交集、并集、差集 操作两个数组之间的交集、并集和差集。 数组分割 将数组划分为不同的部分或区间。 2. 链表
基本概念
链表Linked List是一种常见的数据结构由一系列节点组成每个节点包含两部分信息数据和指向下一个节点的指针。链表中的节点不必在内存中相邻这使得链表具有动态性可以方便地进行插入和删除操作。
链表的节点是什么每个节点包含哪些信息
链表的节点是链表中的基本单元每个节点包含两部分信息
数据Data存储节点的值或者其他信息。指针Pointer指向下一个节点的指针通常称为 Next 指针。
常用操作
插入节点 在头部插入O(1) 在尾部插入O(n)需要遍历整个链表找到尾节点 在中间插入O(n)需要找到插入位置删除节点 删除头节点O(1) 删除尾节点O(n)需要遍历整个链表找到尾节点的前一个节点 删除指定节点O(n)需要找到指定节点的前一个节点查找节点 根据索引查找节点O(n)需要从头节点开始遍历链表直到找到对应索引的节点 根据数值查找节点O(n)需要从头节点开始遍历链表直到找到对应数值的节点 反转链表O(n)需要遍历整个链表逐个修改节点的指针指向
链表的底层实现
链表的底层实现通过节点之间的指针来连接节点。每个节点包含两部分信息数据和指向下一个节点的指针。通过指针可以在链表中任意位置进行插入和删除操作。
优缺点
优点 插入和删除操作高效时间复杂度不受链表大小影响。 链表长度可以动态变化不受固定内存大小的限制。缺点 访问元素的效率较低需要从头指针开始遍历整个链表。 占用的内存空间较大因为每个节点都需要额外的指针存储。改进方法 双向链表在节点中增加一个指向前一个节点的指针可以提高在尾部删除节点的效率。 循环链表尾节点指向头节点形成一个环状结构可以简化链表操作的逻辑。 跳表在链表的基础上增加多级索引提高查找效率适用于有序链表的情况。 LRU缓存算法Least Recently Used (LRU) 缓存算法中使用双向链表来维护最近访问的数据可以通过链表的插入和删除操作来实现缓存的淘汰策略。
链表与其他数据结构的区别
链表与数组的区别 数组是一种静态数据结构其元素在内存中是连续存储的大小固定而链表是一种动态数据结构其节点在内存中不一定连续可以动态增长或缩小。 数组支持随机访问可以通过索引直接访问任何元素时间复杂度为 O1而链表只能顺序访问访问任何节点的时间复杂度为 On。 在插入和删除操作方面数组需要移动元素以维持连续性时间复杂度为 O(n)而链表只需要修改指针时间复杂度为 O1。
插入和删除操作的时间复杂度
在链表头部插入或删除节点的时间复杂度为 O1因为只需要修改头指针。在链表中间或尾部插入或删除节点的时间复杂度为 On因为需要遍历链表找到插入或删除位置的前一个节点。
单链表和双链表
单链表Singly Linked List是一种链表数据结构每个节点包含一个数据元素和一个指向下一个节点的指针。单链表中的节点只有一个指针指向下一个节点因此只能从头节点开始顺序访问。双链表Doubly Linked List是一种链表数据结构每个节点包含一个数据元素、一个指向下一个节点的指针和一个指向前一个节点的指针。双链表中的节点有两个指针分别指向前一个节点和后一个节点因此可以从头节点或尾节点开始双向遍历。单链表和双链表的区别 指针个数 单链表的节点只包含一个指向下一个节点的指针而双链表的节点包含两个指针分别指向前一个节点和后一个节点。 遍历方向 单链表只能从头节点开始顺序遍历无法逆向遍历而双链表可以从头节点或尾节点开始双向遍历。 空间复杂度 双链表的每个节点需要额外存储一个指向前一个节点的指针因此相比单链表双链表的空间复杂度更高。 操作灵活性 双链表相比单链表在某些情况下具有更高的操作灵活性例如在删除节点时双链表可以更高效地删除中间节点。单链表和双链表的常见操作区别 在单链表中插入和删除操作需要遍历找到插入或删除位置的前一个节点而在双链表中由于每个节点都有指向前一个节点的指针插入和删除操作的效率更高。 在双链表中可以双向遍历链表而在单链表中只能从头单向顺序遍历。
循环列表
循环链表Circular Linked List是一种链表数据结构与普通链表不同的是循环链表的尾节点指向头节点形成一个环状结构。换句话说循环链表的尾节点的后继指针指向头节点。循环链表的特点 环状结构 循环链表的尾节点指向头节点形成一个环状结构。 没有固定的头尾节点 由于环状结构的存在没有固定的头尾节点概念可以从任意节点开始遍历整个链表。 循环遍历 由于环状结构可以通过尾节点的后继指针循环遍历整个链表而无需额外维护指向头节点的指针。判断链表是否存在环的常用方法是使用快慢指针双指针技巧。具体步骤如下 使用两个指针一个慢指针slow和一个快指针fast。 初始时两个指针都指向链表的头节点。 慢指针每次移动一步快指针每次移动两步直到快指针到达链表的末尾或者两个指针相遇。 如果快指针到达链表末尾则链表中不存在环如果两个指针相遇则链表中存在环。判断链表是否有环的解决方法包括 哈希表 遍历链表将每个节点的地址存储在哈希表中如果某个节点的地址已经存在于哈希表中则链表中存在环。 快慢指针法 使用快慢指针技巧判断链表是否存在环具体见上述步骤。 使用快慢指针法的时间复杂度为 O(n)其中 n 是链表的长度。该方法只需要遍历一次链表且空间复杂度为 O1不需要额外的存储空间。因此使用快慢指针法是判断链表是否存在环的常用方法。
应用场景
链表在哪些实际场景中被广泛应用能举例说明吗 链表在实际场景中被广泛应用特别是在需要频繁进行插入和删除操作且数据量动态变化的情况下。以下是链表的一些常见应用场景 嵌入式系统和操作系统 链表常用于管理系统资源如进程控制块PCB链表、空闲内存块链表等。 图形图像处理 在图形图像处理中链表可以用来存储多边形的顶点信息。 文本编辑器 文本编辑器中的撤销Undo和重做Redo功能通常使用链表来实现历史记录。 浏览器历史记录 浏览器的历史记录可以使用链表来实现每次访问一个新页面都可以将其加入到链表的头部当历史记录超过一定大小时删除尾部节点。 音乐播放器 音乐播放器中的播放列表可以使用链表来管理用户可以随时添加或删除歌曲。链表在实现栈、队列和LRU缓存算法等数据结构和算法中有何应用 栈Stack 栈是一种后进先出LIFO的数据结构链表可以用来实现栈每次插入和删除操作只需在链表的头部进行效率较高。 队列Queue 队列是一种先进先出FIFO的数据结构链表也可以用来实现队列每次插入操作在链表尾部进行删除操作在头部进行。 LRU缓存算法Least Recently Used LRU缓存算法是一种缓存淘汰策略链表可以用来实现LRU缓存每次访问一个数据时将其移到链表的头部当缓存满时删除链表尾部的数据。
有可能的其他问题
链表在内存中是如何存储的它的内存布局是什么样的 链表在内存中是通过节点之间的指针来连接的每个节点包含两部分信息数据和指向下一个节点的指针。链表的内存布局取决于具体的实现方式但通常情况下每个节点在内存中是分散存储的而不是连续存储的。具体来说每个节点的存储空间可能不连续但通过指针的连接可以在逻辑上构成一个完整的链表结构。
Node 1:[Data | Next]-- Node 2:[Data | Next]-- Node 3:[Data | Next]-- ...-- NULL链表的内存布局示意图可能如下所示以单链表为例 如何计算链表中节点的地址
下一个节点地址 addr size具体来说如果是 C/C 中的指针操作可以直接使用指针加法来计算。例如如果 node 是指向当前节点的指针且节点的大小为 sizeof(Node)则下一个节点的地址可以通过 node 1 来计算。
如何反转一个链表反转链表的时间复杂度是多少 要反转一个链表可以使用迭代或递归两种方法
迭代法 使用三个指针分别表示当前节点、其前驱节点和其后继节点在遍历过程中不断修改指针的指向将当前节点的指针指向前驱节点然后依次向后移动指针。最终将头节点指向原链表的尾节点完成链表的反转。递归法 使用递归来反转链表递归函数的参数为当前节点和其后继节点。在递归过程中不断修改节点的指针指向将当前节点的指针指向其前驱节点。递归到最后一个节点时将其设为新的头节点。 反转链表的时间复杂度为 O(n)其中 n 是链表的长度因为需要遍历整个链表来完成反转操作。
如何找到链表的中间节点 要找到链表的中间节点可以使用快慢指针法。具体步骤如下
使用两个指针一个慢指针slow和一个快指针fast初始都指向链表的头节点。每次迭代时慢指针移动一步快指针移动两步直到快指针到达链表的末尾。当快指针到达末尾时慢指针正好指向链表的中间节点。
如何合并两个有序链表 要合并两个有序链表可以使用迭代或递归两种方法
迭代法 使用两个指针分别指向两个链表的头节点比较两个节点的值将较小值的节点添加到结果链表中并向后移动指针。直到其中一个链表遍历完毕将另一个链表的剩余部分直接连接到结果链表的尾部。递归法 递归地比较两个链表的头节点将较小值的节点作为结果链表的头节点并递归地处理剩余部分。直到其中一个链表为空将另一个链表直接连接到结果链表的尾部。合并两个有序链表的时间复杂度为 O(mn)其中 m 和 n 分别是两个链表的长度。
链表与其他数据结构的比较
优点 链表在插入和删除操作时效率高时间复杂度为 O1。 链表可以动态调整大小不需要预先分配固定大小的内存空间。缺点 访问链表中的元素效率较低需要从头节点开始顺序遍历时间复杂度为 On。 链表需要额外的空间存储指针占用的内存空间相对较大。选择使用链表的情况 需要频繁进行插入和删除操作并且不关心元素的随机访问顺序时可以选择使用链表。 需要动态调整大小或者预先无法确定数据量的大小时也适合使用链表。 3. 栈 (Stack)
基本概念
栈Stack是一种基于先进后出LIFOLast In First Out原则的数据结构类似于生活中的一摞盘子只能在栈顶进行插入和删除操作。栈通常包含两个主要操作入栈Push和出栈Pop。
常用操作 入栈Push 将元素压入栈顶。 时间复杂度O(1) 出栈Pop 弹出栈顶元素。 时间复杂度O(1) 查看栈顶元素Top 获取栈顶元素的值不删除。 时间复杂度O(1) 判断栈是否为空IsEmpty 检查栈是否为空。 时间复杂度O(1)
底层实现
栈可以使用数组或链表来实现。使用数组实现的栈通常需要事先确定栈的最大容量当栈满时可能需要进行扩容操作而使用链表实现的栈则不受容量限制可以动态地增长或缩小。
优缺点
优点 操作简单高效入栈和出栈操作的时间复杂度均为 O1。 内存管理方便栈中的元素在内存中是连续存储的因此内存管理较为简单。缺点 容量限制使用数组实现的栈有容量限制可能会导致栈溢出。 不支持随机访问栈只能从栈顶进行操作不支持随机访问栈中的元素。如何改进 动态扩容 如果使用数组实现的栈可以考虑实现动态扩容机制当栈满时自动增加容量。 确定扩容策略一种是按倍数扩容另一种时按固定增量扩容。【按倍数扩容的优点减少内存分配次数、减少元素复制次数、降低空间浪费可能性】。检查栈是否已满进入栈操作前需要检查栈是否已满。动态申请内存空间 当栈空间不足时需要动态申请更大的内存空间来存储栈元素。这可以通过调用内存分配函数如malloc()或realloc()来实现。复制元素 在申请了新的内存空间后需要将原栈中的元素复制到新的内存空间中。这可以通过遍历原栈并将元素逐个复制到新的内存空间中来实现。释放旧内存空间 在完成元素的复制后需要释放原栈所占用的内存空间。这可以通过调用内存释放函数如free()来实现。更新栈的容量 最后需要更新栈的容量为新的内存空间的大小以便后续的入栈操作可以正确判断栈是否已满。 错误处理 在出栈操作时需要考虑栈为空的情况可以通过返回特定值或抛出异常来处理。性能优化 对栈的底层实现进行优化例如使用链表而不是数组避免扩容和拷贝元素的开销。 动态空间管理 链表实现的栈不受固定容量的限制可以动态地调整大小不需要进行扩容操作。由于链表的节点可以根据需要动态地分配内存空间因此不会出现栈满的情况。插入和删除操作高效 链表在插入和删除操作时效率较高不涉及数组的扩容和元素拷贝操作。在链表中插入和删除节点只需要修改相邻节点的指针不需要移动元素因此操作效率较高。节省内存空间 链表实现的栈不需要预先分配固定大小的内存空间不会出现因为容量过大而造成内存空间浪费的情况。每个节点在需要时动态分配内存节省了内存空间。灵活性高 链表实现的栈具有更高的灵活性可以根据实际需求动态地增加或减少节点适应不同大小的数据量。
栈在实际应用中广泛用于处理递归、表达式求值、括号匹配、深度优先搜索等场景。
可能问的问题
栈的特点包括 元素只能从栈顶Top进行插入和删除操作。 最后插入的元素最先删除称为“先进后出”或“后进先出”。 栈通常用于临时存储数据、函数调用、表达式求值等场景。 栈的常见操作及时间复杂度常见操作 入栈Push 将元素压入栈顶。 出栈Pop 弹出栈顶元素。 查看栈顶元素Top 获取栈顶元素的值不删除。 判断栈是否为空IsEmpty 检查栈是否为空。底层实现和内存管理 栈可以用数组或链表来实现。倾向于使用链表实现栈的原因 链表实现的栈不受固定容量的限制可以动态扩容不会出现栈满的情况。 在动态内存分配的情况下链表实现的栈对内存的利用更灵活不会出现内存浪费的情况。使用数组实现的栈可能存在的问题 固定容量的数组实现的栈存在容量限制当栈满时无法继续插入元素可能导致栈溢出。 需要进行额外的内存管理和扩容操作。解决方法 使用动态数组实现栈当栈的容量不足时自动扩容。
栈的应用场景
实际场景 函数调用和递归函数的调用过程和递归调用时使用栈来保存局部变量和函数调用信息。 表达式求值中缀表达式转后缀表达式以及后缀表达式的求值过程可以使用栈来实现。 浏览器的前进和后退功能通过两个栈来实现浏览历史的前进和后退功能。应用场景举例 浏览器的前进和后退功能通过两个栈分别保存用户浏览过的页面实现前进和后退功能。 表达式求值通过栈来处理中缀表达式转换为后缀表达式并计算后缀表达式的值。栈的复杂问题 如何实现一个浏览器的前进和后退功能 使用两个栈分别保存用户浏览过的页面一个栈保存历史页面另一个栈保存前进页面实现前进和后退功能。如何判断一个表达式中的括号是否匹配 使用栈来处理括号的匹配问题遍历表达式遇到左括号入栈遇到右括号则出栈并判断是否与对应的左括号匹配。
栈与其他数据结构的比较
栈和队列的区别 栈是先进后出LIFO队列是先进先出FIFO。 栈的插入和删除操作都在栈顶进行而队列的插入在队尾删除在队头。 栈通常用于回溯、递归、函数调用等场景而队列通常用于任务调度、广度优先搜索等场景。选择使用栈而不是队列的情况 当需要后进先出的特性时应选择使用栈。 在递归调用和回溯算法中通常使用栈来保存状态信息。栈的改进和优化
动态扩容的栈 使用动态数组实现栈当栈满时自动扩容避免栈空间不足的问题。处理栈空间不足的情况 使用数组实现的栈中当栈空间不足时申请更大的空间并将原来的元素复制到新的空间中。
使用栈时可能会遇到的一些问题
栈溢出 使用数组实现的栈在容量固定的情况下当入栈操作过多时可能会导致栈溢出的问题。性能问题 在频繁进行入栈和出栈操作时如果栈的容量不足或者栈的大小频繁变化可能会导致性能下降。内存管理问题 如果栈的容量过大或者栈的大小难以预测可能会浪费大量的内存空间。
为了解决以上这些问题可以考虑对栈进行改进和优化
使用动态扩容的栈 使用动态数组实现栈当栈满时自动扩容避免栈溢出的问题。动态扩容的策略可以是按倍数扩容也可以是按固定增量扩容。引入栈空间管理机制 对于数组实现的栈可以考虑实现一个栈空间管理机制当栈空间不足时自动申请更大的内存空间并将原来的元素复制到新的空间中。这样可以避免栈溢出的问题并提高性能。使用链表实现栈 如果栈的大小难以预测或者需要频繁变化可以考虑使用链表实现栈链表实现的栈不受容量限制可以动态调整大小更加灵活。优化栈的操作 对于频繁进行入栈和出栈操作的场景可以考虑优化栈的操作减少不必要的操作提高性能。 4. 队列 (Queue)
基本概念
队列Queue是一种基于先进先出FIFOFirst In First Out原则的数据结构类似于排队等待服务的场景。队列通常包含两个主要操作入队Enqueue和出队Dequeue。
常用操作及时间复杂度
入队Enqueue 将元素插入队列尾部。 时间复杂度O(1) 出队Dequeue 从队列头部移除元素。 时间复杂度O(1) 查看队头元素Front 获取队列头部元素的值不删除。 时间复杂度O(1) 查看队列是否为空IsEmpty 检查队列是否为空。 时间复杂度O(1)
底层实现
队列可以使用数组或链表来实现。使用数组实现的队列通常需要维护队列的头部和尾部索引以便进行入队和出队操作。而使用链表实现的队列则不受容量限制可以动态地增长或缩小。
优缺点
优点 操作简单高效入队和出队操作的时间复杂度均为 O(1)。 内存管理方便队列中的元素在内存中是连续存储的因此内存管理较为简单。缺点 固定容量限制使用数组实现的队列有固定容量的限制可能会导致队列溢出。 不支持随机访问队列只能从队头和队尾进行操作不支持随机访问队列中的元素。 如何改进动态扩容 如果使用数组实现的队列可以考虑实现动态扩容机制当队列满时自动增加容量。错误处理 在出队操作时需要考虑队列为空的情况可以通过返回特定值或抛出异常来处理。性能优化 对队列的底层实现进行优化例如使用链表而不是数组以避免扩容和拷贝元素的开销。
面试中可能会遇到的问题 什么是队列它的特点是什么 队列Queue是一种基于先进先出FIFOFirst In First Out原则的数据结构。队列类似于日常生活中的排队等待服务的场景新元素从队尾入队从队头出队。 -队列的主要特点包括 元素的插入入队操作只能在队尾进行。 元素的删除出队操作只能在队头进行。 先进入队列的元素先出队列。 队列的常见操作 队列的常见操作包括 入队Enqueue将元素插入队列尾部。 出队Dequeue从队列头部移除元素。 查看队头元素Front获取队列头部元素的值不删除。 判断队列是否为空IsEmpty检查队列是否为空。 入队和出队操作的时间复杂度均为 O(1)。 底层实现和内存管理 队列可以用数组或链表来实现。一般情况下如果队列的大小固定且较小使用数组实现会更高效。而如果队列的大小不确定或者需要频繁地进行插入和删除操作使用链表实现会更灵活。 队列的应用场景 队列在实际场景中被广泛应用例如
系统任务调度任务按照提交的顺序进行执行。网络数据传输网络数据包按照先后顺序传输。打印任务队列打印任务按照先后顺序进入打印队列。广度优先搜索BFS在图的遍历中BFS 通常使用队列来实现。 队列的复杂问题 如何实现一个生产者-消费者模型 生产者将产品放入队列消费者从队列中取出产品进行消费使用互斥锁或信号量等机制保证生产者和消费者之间的同步和互斥。 如何实现一个循环队列 使用数组实现队列时可以通过循环利用数组空间来实现循环队列。需要维护队列的头尾指针并在出队时移动头指针入队时移动尾指针以循环利用数组空间。 队列与其他数据结构的比较 队列和栈的区别
队列是先进先出FIFO的数据结构而栈是后进先出LIFO的数据结构。队列的插入和删除操作分别在队尾和队头进行而栈的插入和删除操作都在栈顶进行。
在什么情况下选择使用队列而不是栈 当需要按照先进先出的顺序处理元素时应该选择使用队列。 当需要实现广度优先搜索BFS等算法时通常需要使用队列。队列的改进和优化
动态扩容的队列 使用动态数组实现队列当队列满时自动增加容量避免队列溢出的问题。处理队列空间不足的情况 当队列空间不足时可以申请更大的内存空间并将元素复制到新的空间中同时释放旧的内存空间。
5. 树 (Tree)
基本概念
树Tree是一种重要的非线性数据结构由若干个节点Node组成这些节点通过边Edge相连而构成。树的一个特点是每个节点都有零个或多个子节点而且有且只有一个根节点Root其余节点都有唯一的父节点。 根节点Root 树的顶端节点没有父节点。 父节点Parent 有子节点的节点。 子节点Child 某节点的直接后继节点。 叶子节点Leaf 没有子节点的节点。 子树Subtree 树中的任意节点及其所有后代节点构成的子集。 深度Depth 从根节点到当前节点的唯一路径的边数。 高度Height 树中任意节点的最大深度。 节点度Degree 节点拥有的子树的个数。 二叉树Binary Tree 每个节点最多有两个子节点的树。
常用操作和时间复杂度
搜索Search 在树中查找特定节点或值。 时间复杂度最坏情况下为 O(n)n 为树中节点数。 插入Insertion 向树中插入新节点。 时间复杂度平均情况下为 O(log n)n 为树中节点数。 删除Deletion 从树中删除节点。 时间复杂度平均情况下为 O(log n)n 为树中节点数。 遍历Traversal 遍历树中的所有节点。 时间复杂度通常为 O(n)n 为树中节点数。
底层实现原理
树的底层实现通常采用节点Node和指针的结构来表示。每个节点包含数据和指向其子节点的指针。树的根节点可以通过一个指针来访问其他节点则通过指向它们的父节点的指针或者它们的子节点的指针进行访问。
优缺点
优点 提供了一种分层存储数据的方式便于组织和管理数据。 可以实现高效的搜索、插入和删除操作。 适用于表示具有层次结构的数据。缺点 树的操作可能会比较复杂实现起来需要考虑更多的边界情况。 部分操作的时间复杂度可能较高尤其是在树的平衡性受到破坏时。如何改进 平衡树Balanced Tree 通过旋转操作来保持树的平衡使得树的高度保持在一个较低的水平提高操作效率。 AVL树 一种最早被发明的自平衡二叉搜索树通过在插入和删除操作后进行旋转来保持平衡。红黑树Red-Black Tree 一种更加复杂但是实现简单的自平衡二叉搜索树通过对节点进行染色和旋转来保持平衡。 多路搜索树Multiway Search Tree 改进节点的度使每个节点可以拥有多于两个的子节点提高树的分支度降低树的高度。 B树B-tree 一种自平衡的搜索树通常用于数据库和文件系统中能够高效地处理大量数据的插入、删除和搜索操作。B树B tree 在B树的基础上进行了改进更适用于文件系统和数据库索引的实现。 优先级搜索树Priority Search Tree 适用于特定的搜索场景如区间搜索等通过特殊的数据结构和操作来实现高效的搜索。 线段树Segment Tree 一种用于处理动态区间查询的数据结构可以高效地支持区间查询、更新等操作。树状数组Fenwick Tree 一种支持动态单点更新和区间查询的数据结构常用于解决前缀和、逆序对等问题。
树是一种非常灵活且广泛应用的数据结构对其进行改进可以根据具体的应用场景和需求来选择不同的优化方法。
可能会问到的问题
分类二叉树完全二叉树满二叉树二叉排序树平衡二叉树红黑树B树B树B*树 二叉树 有限个结点的集合这个集合或者是空集或者是由一个根结点和两株互不相交的二叉树组成其中一株叫根的做左子树另一棵叫做根的右子树。 完全二叉树 除最后一层外每一层上的结点数均达到最大值在最后一层上只缺少右边的若干结点 二叉树是每个节点最多有两个子树的树结构每个节点最多两个子树 二叉树的性质 性质1在二叉树中第 i 层的结点数最多为2^(i-1)i ≥ 1 性质2高度为k的二叉树其结点总数最多为2^k1 k ≥ 1 性质3对任意的非空二叉树 T 如果叶结点的个数为 n0而其度为 2 的结点数为 n2则n0 n2 1 满二叉树深度为k且有2^k 1个结点的二叉树称为满二叉树 完全二叉树深度为 k 的有n个结点的二叉树当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应称之为完全二叉树。除最后一层外每一层上的节点数均达到最大值在最后一层上只缺少右边的若干结点 性质4具有 n 个结点的完全二叉树的深度为 log2n 1 注意 仅有前序和后序遍历不能确定一个二叉树必须有中序遍历的结果。 红黑树 红黑树是一种自平衡的二叉搜索树它保持着良好的平衡性使得插入、删除和搜索等操作的时间复杂度保持在较低的水平。红黑树的底层实现涉及到节点的设计、颜色的管理以及平衡操作的实现等方面。 红黑树节点设计 红黑树的节点通常包含以下信息 关键字Key用于搜索和比较的值。 数据Value存储的实际数据。 左子节点指针Left Child Pointer指向左子节点的指针。 右子节点指针Right Child Pointer指向右子节点的指针。 父节点指针Parent Pointer指向父节点的指针。 颜色Color标识节点的颜色通常为红色或黑色。红黑树的性质 每个节点要么是红色要么是黑色。 根节点是黑色的。 每个叶子节点NIL节点是黑色的。 如果一个节点是红色的则它的子节点必须是黑色的。 从任意节点到其每个叶子节点的所有简单路径都包含相同数量的黑色节点。平衡操作 红黑树通过旋转操作来保持平衡主要有两种旋转操作 左旋转Left Rotation将当前节点向左旋转以其右子节点为新的根节点。 右旋转Right Rotation将当前节点向右旋转以其左子节点为新的根节点。 插入操作 在插入新节点时红黑树需要执行一系列操作来保持平衡主要分为以下几步 将新节点插入到二叉搜索树中的合适位置并将其颜色设置为红色。 根据红黑树的性质可能需要进行一系列的调整操作包括变色和旋转操作以确保树的平衡性。删除操作 在删除节点时红黑树也需要执行一系列操作来保持平衡主要分为以下几步 如果待删除节点是叶子节点或者只有一个子节点直接删除该节点即可。 如果待删除节点有两个子节点找到其后继节点或前驱节点来替代该节点然后删除后继节点或前驱节点。 根据红黑树的性质可能需要进行一系列的调整操作包括变色和旋转操作以确保树的平衡性。 多路优先搜索树 B树B-tree底层实现 B树是一种自平衡的多路搜索树其底层实现主要包括以下几个方面 节点结构 B树的节点通常包含多个关键字和子节点每个节点的关键字按照升序排列子节点指针用于指向子树。 分裂和合并 当节点中的关键字数量超过一定阈值时需要进行节点的分裂操作当节点中的关键字数量低于一定阈值时可能需要进行节点的合并操作。 插入和删除 插入操作需要先找到合适的位置并插入关键字然后可能需要进行节点分裂操作删除操作需要先找到要删除的关键字并进行删除然后可能需要进行节点合并操作。 搜索 在搜索操作中从根节点开始逐层向下搜索根据关键字的大小确定搜索方向直到找到目标节点或者确定目标节点不存在。 B树B tree底层实现 B树是在B树的基础上进行了改进的数据结构其底层实现与B树类似但有以下不同点 节点结构 B树的非叶子节点只包含索引信息不存储关键字对应的值而叶子节点则存储所有的关键字及其对应的值。 叶子节点连接 叶子节点之间通过指针连接成链表方便范围查询和顺序遍历。 范围查询 由于叶子节点之间有序连接因此可以更高效地进行范围查询操作。 性能优化 B树的叶子节点通常更大包含更多的关键字这样可以减少磁盘I/O次数提高搜索效率。 注意的问题 在实现B树和B树时需要注意以下问题 节点分裂和合并的策略 分裂和合并操作的策略对于树的性能有重要影响需要选择合适的策略以保持树的平衡。 并发访问和锁机制 在多线程或多进程环境下需要考虑并发访问的情况并使用合适的锁机制来保护数据的一致性。 持久化存储 在数据库中使用B树和B树时需要考虑数据的持久化存储和恢复机制以确保数据的安全性和可靠性。 优化和性能调优 根据具体的应用场景和需求需要不断优化和调优B树和B树的实现以提高其性能和效率。 常考的问题 B树和B树的区别和联系是什么 B树和B树是常用于实现数据库索引的数据结构它们在设计和应用上有一些区别和联系。 区别 节点结构 B树的非叶子节点存储的是关键字和指向子节点的指针同时也可能存储关键字对应的值。 B树的非叶子节点只存储关键字和指向子节点的指针不存储关键字对应的值所有的值都存储在叶子节点中。 叶子节点 B树的叶子节点可能包含关键字对应的值也可能不包含这取决于具体的实现。 B树的叶子节点包含所有的关键字和对应的值并且通过指针连接成链表。 范围查询 B树的叶子节点包含部分关键字和对应的值因此可以在叶子节点中进行范围查询。 B树的叶子节点包含所有的关键字和对应的值并且通过链表连接因此可以更高效地进行范围查询。插入和删除 B树的插入和删除操作可能需要对非叶子节点进行调整因为非叶子节点中也可能包含关键字。 B树的插入和删除操作只涉及到叶子节点因此可以更高效地执行。存储效率 B树的叶子节点通常更大因为包含了所有的关键字和值这样可以减少磁盘I/O次数提高存储效率。 B树的节点包含部分关键字和值可能导致存储效率较低。 B树和B树的插入和删除操作是如何实现的 B树的插入操作 查找插入位置 从根节点开始按照关键字的大小逐级向下查找插入位置直到找到叶子节点。 插入关键字 在叶子节点中插入新的关键字并调整节点中关键字的顺序使得节点保持有序。 节点分裂 如果插入后叶子节点中的关键字数量超过了阈值则进行节点分裂操作将节点分裂成两个节点并将中间关键字上移。 向上调整 依次向上调整父节点使得父节点中的关键字数量符合B树的定义并可能触发进一步的节点分裂操作。B树的删除操作 查找待删除关键字 从根节点开始按照关键字的大小逐级向下查找待删除关键字所在的叶子节点。 删除关键字 在叶子节点中删除待删除关键字并调整节点中关键字的顺序使得节点保持有序。 节点合并 如果删除后叶子节点中的关键字数量低于了阈值则进行节点合并操作将节点合并成一个节点并将父节点中的关键字下移。 向上调整 依次向上调整父节点使得父节点中的关键字数量符合B树的定义并可能触发进一步的节点合并操作。B树的插入操作 B树的插入操作与B树类似但是插入操作只涉及到叶子节点不需要对非叶子节点进行调整。插入操作主要包括查找插入位置、插入关键字、节点分裂和向上调整。B树的删除操作 B树的删除操作也与B树类似但是删除操作只涉及到叶子节点不需要对非叶子节点进行调整。删除操作主要包括查找待删除关键字、删除关键字、节点合并和向上调整。 B树相比于B树有哪些优点 更适合范围查询、更适合顺序访问、更少的磁盘I/O更高的存储效率、更稳定的性能。B树和B树在数据库索引中的应用场景是什么 B树的应用场景 单点查询 B树适用于单点查询即通过唯一的关键字进行查询可以快速定位到目标数据。 随机访问 对于需要随机访问的场景B树可以快速定位到指定位置的数据。 低延迟写入 B树对于插入和删除操作的性能相对较好适用于需要频繁更新数据的场景。B树的应用场景 范围查询 B树适用于范围查询即查询某个范围内的数据因为B树的叶子节点之间通过链表连接可以高效地进行范围查询。 顺序访问 对于需要按照关键字顺序访问数据的场景B树具有更好的性能因为叶子节点之间通过链表连接可以高效地进行顺序访问。 高效存储 B树的叶子节点通常更大包含了所有的关键字和对应的值可以减少磁盘I/O次数提高数据查询的效率适用于大规模数据存储和查询的场景。 B树和B树的搜索性能如何 B树的搜索性能 单点查询 对于单点查询即根据唯一的关键字进行查询B树的搜索性能非常高时间复杂度为O(log n)其中n为树的高度。 随机访问 对于需要随机访问的场景B树也具有较高的搜索性能因为B树的节点通常具有多个子节点可以快速定位到目标数据。B树的搜索性能 单点查询 B树的单点查询性能与B树相似时间复杂度为O(log n)其中n为树的高度。 范围查询 对于范围查询即查询某个范围内的数据B树的搜索性能更优因为B树的叶子节点之间通过链表连接可以快速定位到范围内的所有数据。 顺序访问 对于需要按照关键字顺序访问数据的场景B树具有更好的搜索性能因为叶子节点之间通过链表连接可以高效地进行顺序访问。 B树和B树的节点分裂和合并策略是怎样的 节点分裂 当一个节点中的关键字数量超过了阈值时需要进行节点分裂操作。 分裂操作将节点中的关键字分成两部分中间关键字上移至父节点形成两个新的节点。 分裂后的两个节点中各自包含了一部分关键字并且子节点的指针也相应调整。节点合并 当一个节点中的关键字数量低于了阈值时可能需要进行节点合并操作。 合并操作将节点和其相邻的兄弟节点合并成一个节点其中包含了原来两个节点中的所有关键字。 合并后的节点中父节点中的关键字相应下移至合并后的节点中并且子节点的指针也相应调整。B树的节点分裂和合并策略 B树的节点分裂和合并策略与B树类似但有一些特殊之处仅涉及叶子节点 在B树中节点分裂和合并操作仅涉及到叶子节点而非叶子节点仅包含关键字和指向子节点的指针不包含实际数据。仅在叶子节点中移动关键字 在B树中关键字的插入、删除和移动只在叶子节点中进行非叶子节点仅用于路由不存储实际数据。节点合并时不删除关键字 在B树中节点合并时不会删除关键字而是将相邻的叶子节点合并成一个节点其中包含了所有的关键字这样可以减少节点合并的开销。
B树和B树的节点分裂和合并策略都是确保树保持平衡的重要操作分裂操作用于处理节点中关键字过多的情况而合并操作用于处理节点中关键字过少的情况以确保树的平衡性和性能稳定性。 优先级搜索树 线段树Segment Tree 一种用于处理动态区间查询的数据结构可以高效地支持区间查询、更新等操作。 线段树Segment Tree是一种树形数据结构主要用于处理一维区间或线段的相关查询和更新操作。它可以高效地支持区间查询如区间最小值、区间最大值、区间和等和区间更新如单点更新、区间增加等操作。 应用场景 区间查询 线段树广泛应用于需要进行区间查询的场景如求解一段连续时间内的最大、最小、和等指标求解区间内的第k小值等。 区间更新 线段树也适用于需要进行区间更新的场景如对一段连续时间内的数据进行修改、增加等操作。 动态规划 线段树在解决动态规划问题中也有应用如求解最长上升子序列、最大子段和等问题。 底层实现 线段树通常采用递归或迭代方式构建具体实现如下 节点结构 线段树的每个节点通常包含左右子节点指针、区间范围、以及相应的统计信息如最小值、最大值、区间和等。 构建过程 通过递归或迭代方式从根节点开始构建线段树每次将当前区间一分为二递归构建左右子树直到区间长度为1。 查询操作 查询操作从根节点开始递归向下根据查询的区间范围和节点的区间范围进行相应的处理直到找到与查询区间相交的节点然后将结果合并返回。 更新操作 更新操作也从根节点开始递归向下根据更新的位置和节点的区间范围进行相应的处理直到找到更新位置所在的叶子节点然后更新相关的统计信息然后依次向上更新父节点的统计信息。 性能分析 线段树的构建复杂度为O(n)其中n为区间长度。线段树的查询和更新操作的时间复杂度为O(log n)其中n为区间长度。线段树占用的空间复杂度为O(n)。 线段树是一种高效的数据结构适用于处理区间查询和更新操作的场景具有较好的时间和空间性能。 树状数组也叫二叉索引树Fenwick Tree 一种支持动态单点更新和区间查询的数据结构常用于解决前缀和、逆序对等问题。 树状数组Fenwick Tree也称为二叉索引树Binary Indexed TreeBIT是一种用于高效处理动态数据集的数据结构。树状数组主要用于高效计算数列的前缀和并支持单点更新和区间查询等操作。 应用场景 前缀和计算 树状数组可以高效地计算数列的前缀和对于需要频繁查询数列某个区间的和的场景非常有用比如统计数组中某个区间的元素个数或求解区间和等。 单点更新 树状数组支持单点更新操作即对数组中某个位置的元素进行修改同时能够快速更新受影响的前缀和。 区间查询 虽然树状数组主要用于前缀和计算但也可以支持一些区间查询操作比如区间最值查询等。 底层实现 树状数组的底层实现基于树状结构但是采用了一种巧妙的存储方式使得操作效率大幅提高。具体来说树状数组使用了一个辅助数组来存储部分前缀和其中数组的索引值表示了某种“跳跃”的关系通过这种方式可以实现高效的前缀和计算。 构建 树状数组的构建是一个预处理过程可以在O(nlogn)的时间复杂度内完成其中n是数组的大小。 更新操作 对于更新操作树状数组会修改对应的元素并同时更新受影响的前缀和时间复杂度为O(logn)。 查询操作 对于查询操作树状数组可以在O(logn)的时间复杂度内计算出指定区间的前缀和。
6. 图 (Graph)
基本概念图是由节点顶点和边组成的一种非线性数据结构用于表示对象之间的关系。图可以是有向的或者无向的边可以有权重。 常用操作 遍历O(V E)V 为顶点数E 为边数 插入顶点O(1) 插入边O(1) 底层实现图的底层实现可以有多种方式常见的包括邻接矩阵和邻接表。邻接矩阵使用二维数组表示顶点之间的连接关系而邻接表使用链表或者数组来表示每个顶点的邻居节点。
深度优先搜索Depth-First SearchDFS 从图中的某个节点出发沿着路径一直向下搜索直到不能再继续为止然后回退到上一个节点继续搜索其他路径。DFS常用于图的遍历、连通性检测和寻找路径等问题。广度优先搜索Breadth-First SearchBFS 从图中的某个节点出发先访问其所有的邻居节点然后依次访问邻居节点的邻居节点依次类推直到所有节点都被访问过为止。BFS常用于图的遍历、最短路径和连通性检测等问题。最短路径算法 最短路径算法用于找出图中两个节点之间的最短路径。常见的最短路径算法包括4. 迪杰斯特拉算法Dijkstra、贝尔曼-福特算法Bellman-Ford和Floyd-Warshall算法。最小生成树算法 最小生成树算法用于在图中找到一棵包含所有节点且边权值之和最小的树。常用的最小生成树算法包括普里姆算法Prim和克鲁斯卡尔算法Kruskal。拓扑排序 拓扑排序用于对有向无环图DAG进行排序使得所有的顶点按照一定的顺序排列满足图中任意一条边的起始顶点在排序结果中都排在终点顶点之前。强连通分量算法 强连通分量算法用于将图中的节点划分成强连通分量即图中任意两个节点都可以互相到达。常用的强连通分量算法包括Tarjan算法和Kosaraju算法。网络流算法 网络流算法用于解决网络流问题例如最大流问题和最小割问题。常用的网络流算法包括Ford-Fulkerson算法和Edmonds-Karp算法。图的匹配算法 图的匹配算法用于找出图中的最大匹配或最大独立集合。常用的图的匹配算法包括匈牙利算法和Edmonds’ Blossom算法。 cout“未完待续……”endl;
