Prim的算法(Prim's Algorithm)

数据结构是一种以结构和系统方式定义，存储和重新获取数据的方法。 数据结构可以包含不同类型的数据项。

数据结构可用性可能因编程语言而异。 常用的数据结构是列表，数组，堆栈，队列，图形，树等。

算法是一步一步的过程，它定义了一组指令，这些指令按特定顺序执行以获得所需的输出。

问题可以通过多种方式解决。 因此，可以针对给定问题导出许多解决方案算法。 我们分析可用的算法以找到并实现最合适的算法。

通常在两个因素 - 时间和空间上分析算法。 也就是说，算法需要多少execution时间和多少extra space 。

算法的渐近分析，是指定义其运行时性能的数学边界/框架。 使用渐近分析，我们可以很好地得出算法的最佳情况，平均情况和最坏情况。

渐近分析可以提供算法执行时间的三个级别的数学绑定 -

• 最佳情况用Ω（n）表示法表示。
• 最坏的情况用Ο（n）表示法表示。
• 平均情况用Θ（n）表示法表示。

线性数据结构具有顺序排列的数据项。 下一次可以位于下一个存储器地址中。 它以顺序方式存储和访问。 数组和列表是线性数据结构的示例。

通常对任何数据结构执行以下操作 -

• Insertion - 添加数据项

• Deletion - 删除数据项

• Traversal - 访问和/或打印所有数据项

• Searching - 查找特定数据项

• Sorting - 以预定义的顺序排列数据项

有三种常用的方法来开发算法 -

• Greedy Approach - 通过选择下一个最佳选项寻找解决方案

• Divide and Conquer - 将问题延伸到最小可能的子问题并独立解决

• Dynamic Programming - 将问题延伸到最小可能的子问题并将它们结合起来解决

以下给出的问题使用贪心算法方法找到他们的解决方案 -

• Travelling Salesman Problem
• Prim的最小生成树算法
• Kruskal的最小生成树算法
• Dijkstra的最小生成树算法
• 图 - 地图着色
• 图 - 顶点覆盖
• 背包问题
• Job Scheduling Problem

下面给出的问题使用分而治之的算法方法找到他们的解决方案 -

• 合并排序
• 快速排序
• Binary Search
• Strassen的矩阵乘法
• 最近的一对（点）

下面给出的问题使用分而治之的算法方法找到他们的解决方案 -

• 斐波纳契数系列
• 背包问题
• Tower of Hanoi
• 由Floyd-Warshall完成的所有最短路径
• Shortest path by Dijkstra
• Project scheduling

链表是与链接连接的数据项列表，即指针或引用。 大多数现代高级编程语言不提供直接访问内存位置的功能，因此，链接列表不受支持或以内置函数的形式提供。

在数据结构中，堆栈是一种抽象数据类型（ADT），用于在Last In First Out方法中存储和检索值。

堆栈遵循LIFO方法，并且数据项的添加和检索仅花费Ο（n）时间。 堆栈用于需要以相反顺序或到达时访问数据的位置。 堆栈通常用于递归函数调用，表达式解析，图形的深度优先遍历等。

以下操作可以在堆栈上执行 -

• push() - 将一个项添加到堆栈中

• pop() - 删除顶部堆栈项

• peek() - 给出顶级项的值而不删除它

• isempty() - 检查堆栈是否为空

• isfull() - 检查堆栈是否已满

队列是一种抽象的数据结构，有点类似于堆栈。 与堆栈相反，队列在两端都打开。 一端始终用于插入数据（入队），另一端用于删除数据（出队）。 队列遵循先进先出方法，即首先访问先存储的数据项。

由于队列遵循FIFO方法，因此在我们需要按照到达的确切顺序处理数据项时使用它们。 每个操作系统都维护着各种进程的队列。 优先级队列和广度优先遍历的图是队列的一些示例。

以下操作可以在堆栈上执行 -

• enqueue() - 在队列后面添加一个项目

• dequeue() - 从队列前面删除项目

• peek() - 给出前项的值而不删除它

• isempty() - 检查堆栈是否为空

• isfull() - 检查堆栈是否已满

线性搜索尝试在顺序排列的数据类型中查找项目。 这些顺序排列的数据项称为数组或列表，可在递增内存位置时访问。 线性搜索将预期数据项与列表或数组中的每个数据项进行比较。 线性搜索的平均情况时间复杂度是Ο（n），最差情况复杂度是Ο（n ² ）。 目标数组/列表中的数据无需排序。

二进制搜索仅适用于已排序的列表或数组。 此搜索选择将整个列表分成两部分的中间部分。 首先比较中间。

此搜索首先将目标值与列表中间值进行比较。 如果没有找到，则需要决定是否。

冒泡排序是基于比较的算法，其中比较每对相邻元素并且如果它们不按顺序交换元素。 由于时间复杂度为Ο（n ² ），因此不适用于大量数据。

插入排序将列表分为两个子列表，已排序和未排序。 它一次需要一个元素，并在排序的子列表中找到合适的位置并插入其中。 插入后的输出是已排序的子列表。 它迭代地处理未排序的子列表的所有元素，并按顺序将它们插入到排序的子列表中。

选择排序是就地排序技术。 它将数据集分为两个子列表:sorted和unsorted。 然后，它从未排序的子列表中选择最小元素，并将其放入排序列表中。 除非将未排序的子列表中的所有元素都消耗到已排序的子列表中，否则这将进行迭代。

两种排序技术都维护两个子列表，排序和未排序，并且一次只取一个元素并将其放入已排序的子列表中。 插入排序适用于当前的当前元素，并将其放置在排序数组中的适当位置，从而保持插入排序的属性。 然而，选择排序从未排序的子列表中搜索最小值，并将其替换为手中的当前元素。

合并排序是基于分而治之的编程方法的排序算法。 它继续将列表划分为更小的子列表，直到所有子列表只有1个元素。 然后它以排序的方式合并它们，直到消耗掉所有子列表。 它的运行时复杂度为Ο（n log n），它需要Ο（n）辅助空间。

Shell排序可以说是插入排序的变种。 Shell排序根据某个gap变量将列表划分为较小的子列表，然后使用insert sort对每个子列表进行排序。 在最好的情况下，它可以执行高达Ο（n log n）。

快速排序使用分而治之的方法。 它使用“pivot”将列表划分为较小的“分区”。 小于枢轴的值排列在左侧分区中，更大的值排列在右侧分区中。 使用快速排序递归排序每个分区。

图形是一组对象的图形表示，其中一些对象通过链接连接。 互连对象由称为顶点的点表示，连接顶点的链接称为边。

深度优先搜索算法（DFS）以向深运动的方式遍历图形，并使用堆栈记住在任何迭代中发生死角时获取下一个顶点以开始搜索。

广度优先搜索算法（BFS）以横向运动遍历图形并使用队列记住在任何迭代中发生死角时获取下一个顶点以开始搜索。

树是没有环路和电路的最小连通图。

二叉树具有特殊条件，即每个节点最多可以有两个子节点。

二叉搜索树是具有特殊规定的二叉树，其中节点的左子节点的值必须小于其父节点的值，节点的右子节点的值必须大于其父值。

树遍历是访问树的所有节点的过程。 因为所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。 我们使用三种方式遍历树 -

• 有序遍历
• Pre-order Traversal
• Post-order Traversal

• 有序遍历 - 10 14 19 27 31 35 42
• 预订遍历 - 27 14 10 19 35 31 42
• 下订单遍历 - 10 19 14 31 42 35 27

AVL树是高度平衡二叉搜索树。 AVL树检查左右子树的高度，并确保差异不大于1.这种差异称为平衡因子。

BalanceFactor = height(left-sutree) − height(right-sutree)

生成树是图G的子集，其具有覆盖有最小可能边数的所有顶点。 生成树没有循环，也无法断开连接。

这取决于图表的连接方式。 完整的无向图可以具有最多n ^n-1个生成树，其中n是节点数。

此算法将图形视为林，将每个节点视为单个树。 只有在所有可用选项中成本最低且不违反MST属性的情况下，树才会连接到另一个树。

Prim算法将节点视为单个树，并继续从给定图形向生成树添加新节点。

在加权图中，最小生成树是生成树，其具有与同一图的所有其他生成树相比最小的权重。

堆是一种特殊的平衡二叉树数据结构，其中根节点密钥与其子节点进行比较并相应地进行排列。 最小堆，父节点的键值小于其子节点，并且最大堆父节点的值大于其子节点。

递归函数是直接调用自身或调用函数的函数，函数又调用它。 每个递归函数都遵循递归属性 - 函数停止调用自身的base criteria和函数在每次迭代中尝试满足基本条件的progressive approach 。

河内塔，是一个数学难题，由三个塔（钉）和一个以上的环组成。 所有环都具有不同的尺寸并且彼此堆叠在一起，其中大盘总是在小盘下面。 目的是将磁盘塔从一个挂钩移动到另一个挂钩，而不会破坏其特性。

Fibonacci系列通过添加两个先前的数字来生成后续数字。 例如 - 0 1 1 2 3 5 8 13。

散列是一种将一系列键值转换为数组索引范围的技术。 通过使用哈希表，我们可以创建一个关联数据存储，通过提供其键值可以找到数据索引。

插值搜索是二进制搜索的改进变体。 该搜索算法适用于所需值的探测位置。

前缀表示法 - * + ab + cd

后缀表示法 - ab + cd + *