type
status
date
slug
summary
tags
category
icon
password
图的数据结构包含一个有限的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边的集合。
通常采用一个矩阵即二维数组，每个坐标即为储存每两个节点的值，或是邻接表，每一个点后面带一个链表，存储他能到达的所有位置。
BFS DFS即为深度优先和广度优先搜索算法，如果是一个二维迷宫的话举例深度优先简单来说就是每一个点一直往下尝试各个方向走，指导走不通然后回头一点点继续尝试。BFS为下把每一个点往四个方向走，然后一直继续下去。
深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图的算法。在二维迷宫中，DFS可以看作是从起点开始，一直沿着一个方向走，直到遇到障碍或已经访问过的点，然后回溯并尝试其他路径。
具体步骤：
- 从起点开始，标记该点为已访问。
- 尝试向下一个未访问的相邻点移动（可以是上、下、左、右四个方向之一）。
- 如果当前点可以移动到下一个点（即下一个点是迷宫的一部分且未被访问过），则移动到该点，并重复步骤2。
- 如果当前点无法移动到下一个点（即所有相邻点都是障碍或已被访问过），则回溯到上一个点，并尝试其他未访问的相邻点。
- 重复步骤3和4，直到找到终点或遍历完所有可达的点。
广度优先搜索（BFS）
广度优先搜索也是一种用于遍历或搜索树或图的算法。与DFS不同的是，BFS会先访问所有与起点相邻的未访问点，然后再从这些点出发，访问它们的未访问相邻点，依此类推。
具体步骤：
- 从起点开始，标记该点为已访问，并将其加入到一个队列中。
- 从队列中取出一个点，并尝试向下一个未访问的相邻点移动（可以是上、下、左、右四个方向之一）。
- 如果当前点可以移动到下一个点（即下一个点是迷宫的一部分且未被访问过），则移动到该点，标记为已访问，并将其加入到队列中。
- 重复步骤2和3，直到队列为空或找到终点。
- 如果队列为空且未找到终点，则遍历完所有可达的点。
其实感觉大部分的需要搜索的问题都可以通过他俩来解决了就是可能时间复杂度有的时候会比较高hhh
再来俩例题吧。
输入是一个二进制矩阵，在每一个为1 的点进行搜索，将来连通的面积保存下来，获取他的最大值，这里用到的方法是DFS
这里是将一个矩阵中的每一个非零的数字更新为它离0的距离，在这里头将矩阵遍历，首先创建一个visit数组，将所有0放进去，防止被访问，从每一个零往他的四周扩散，如果不是0就加上1，然后赛道这个队列里，重复上述的过程，是一个基本的BFS
- Author:SAKURAAE
- URL:https://tangly1024.com/article/7152dc6c-a0d5-47f5-a3d2-7c5a6d78bc6b
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!