图的搜索算法：广度优先与深度优先

“试描述算法及算法三要素。-算法设计课件” 算法是解决问题的明确规范，它是一系列详细的步骤，用于完成特定任务或解决特定问题。算法三要素包括输入（Input）、输出（Output）和控制流程（Control Flow）： 1. 输入：算法可能需要零个或多个输入，这些输入是算法处理的数据来源。 2. 输出：算法执行后必须产生一个或多个输出，这些输出是算法解决问题的结果。 3. 控制流程：算法中的控制流程决定了如何处理输入并产生输出，通常包括顺序执行、选择（条件分支）、循环（迭代）等基本结构。 算法分析的主要任务是对算法的效率进行评估，以便了解其在不同规模问题上的性能。算法复杂度主要分为时间复杂度和空间复杂度： 1. 时间复杂度：衡量算法执行所需的基本运算次数，反映了算法运行速度。用大O记法表示，如O(1)，O(n)，O(n²)等。 2. 空间复杂度：衡量算法执行过程中所需的内存空间，包括临时变量、数据结构等。同样用大O记法表示。 自顶向下（Top-Down）的设计方法是一种模块化设计策略，它首先从问题的整体出发，将其分解为更小的子问题，然后分别解决子问题，最终组合成整体解决方案。例如，设计一个排序算法，可以先定义一个主函数，然后将排序过程分解为交换元素和比较元素等子功能。 贪婪算法和动态规划都是解决优化问题的策略： 1. 贪婪算法：每次决策时都采取当前看起来最优的选择，不考虑长远影响。例如，找零钱问题中，每次都找最大面额的硬币。 2. 动态规划：通过解决子问题并存储结果，避免重复计算，最终构建全局最优解。例如，斐波那契数列或背包问题。 动态规划的基本思想是将问题分解为相互重叠的子问题，并利用子问题的最优解来构造原问题的最优解。最优子结构性质是指一个问题的最优解包含其子问题的最优解。 本课件还涉及图的搜索算法，如广度优先搜索（BFS）和深度优先搜索（DFS）： 1. 广度优先搜索：从起点开始，逐层遍历图的节点，先访问离起点近的节点，常用于找到两个节点间的最短路径。 2. 深度优先搜索：从起点开始，尽可能深地探索图的分支，直到达到叶子节点，然后回溯。适用于寻找是否存在路径的情况。 图的存储通常有两种方式：邻接矩阵和邻接表。邻接矩阵适合表示稠密图，邻接表则适合表示稀疏图，可以节省存储空间。穷举搜索和启发式搜索是两种不同的搜索策略，前者盲目搜索所有可能的解，后者则利用额外信息提高搜索效率。