java基础的深度问题 - 编程好6文档

一、深度优先搜索

深度优先搜索（DFS）是一种用于图遍历或树遍历的算法。它的核心思想是尽可能地向深度方向遍历，直到到达最深处，然后返回上一个节点，继续向另一个方向遍历。

深度优先搜索的实现可以使用递归或栈（迭代版本）来实现。以下是递归实现的示例代码：

在这个示例中，函数递归地遍历邻接列表表示的图。如果当前节点没有被访问过，则输出该节点，将其添加到已访问集合中，并递归访问其邻居节点。

下面是使用栈实现深度优先搜索的示例代码：

在这个示例中，函数使用栈来实现深度优先搜索。它从起始节点开始，将其入栈。然后进入一个循环，弹出栈顶节点，如果该节点没有被访问过，则输出该节点，将其添加到已访问集合中，并将其邻居节点压入栈中。循环继续，直到栈为空。

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种java基础的深度问题从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

这是一个典型的搜索问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。由于题目中给定了障碍，所以在搜索过程中需要判断当前位置是否是障碍，如果是则不能继续搜索。

下面以DFS为例，给出一个可能的实现：

其中，函数表示从当前位置开始搜索，已经访问过的位置保存在中，终点坐标是，表示整个迷宫。函数是最终的接口函数，用于调用函数并返回结果。

需要注意的是，在搜索过程中，已经访问过的位置需要标记为已访问，避免重复搜索，但在返回时需要将其标记为未访问，以允许其他路径从该位置经过。另外，在搜索时需要判断当前位置是否越界或是障碍，避免出现数组下标越界或是走到障碍的情况。

广度优先搜索（Breadth-First Search，BFS）是一种基于图形数据结构的算法，用于解决从起点到目标节点的最短路径问题。BFS以图形结构为基础，逐层搜索与起点相邻的节点，并且保持搜索距离一层一层地增加，直到找到目标节点或者遍历完所有节点。

下面是广度优先搜索的实现步骤：

BFS算法可以使用迭代或者递归的方式进行实现。以下是Python中使用队列实现BFS算法的非递归实现：

其中，参数为图的邻接表表示，参数为起始节点。在该实现中，使用了Python标准库中的类来实现队列的功能，同时使用了Python的类来存储已访问的节点，以避免重复访问。函数中的while循环用于不断地取出队列中的节点进行访问，直到队列为空为止。

递归方式实现BFS也是可行的。递归方式的BFS可以看作是一个深度优先搜索（DFS）的变种，它通过使用队列来保存每一层的节点，从而实现了广度优先的搜索方式。BFS算法通常使用非递归实现，但是在某些情况下也可以使用递归实现，例如对于较小的图。

以下是BFS算法的Python递归实现：

在递归实现中，我们定义了一个名为的递归函数，它接受三个参数：表示图的字典，表示当前要访问的节点队列，表示已访问过的节点集合。

首先，我们从队列中取出队首节点，并打印该节点的值。然后，我们遍历该节点的邻居节点，并将邻居节点添加到队列中，并将其标记为已访问。最后，我们递归调用函数，以便继续遍历下一个节点。

在主程序中，我们首先创建空队列和集合，并将起始节点加入队列和集合。然后，我们调用函数，以开始遍历整个图。

需要注意的是，递归方式实现BFS的性能通常不如迭代方式实现BFS。因为递归会产生函数调用的开销，而队列的操作也会导致额外的内存开销。因此，在实际应用中，通常建议使用迭代方式实现BFS。

题目：

有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步

题解：

这是一个典型的图论问题，可以使用广度优先搜索（BFS）来解决。

具体步骤如下：

创建一个二维数组，用来记录每个点到马所在点的最短距离。初始化为全零。
将马所在点加入一个队列中，同时将其值设为0。
对队列进行广度优先搜索。从队列中取出一个点，将其周围可以到达的点加入队列，并更新这些点的值。注意，这里的“可以到达的点”是指棋盘上的合法位置，即横、纵坐标都在棋盘范围内，并且与当前点的横、纵坐标之差的绝对值之和为3。
重复步骤3，直到队列为空。

最后，数组中记录的就是每个点到马所在点的最短距离。

以下是Python代码实现：

上一篇： java基础类型初始值

下一篇： java基础框架搭建ssm

版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.bianchenghao6.com/h6javajc/18807.html