在开始正文之前，先讨论一下数据结构是什么？数据结构就是程序运行时数据存放的结构，在万物皆对象的java里面，对象就是存放在堆内存里面。
而有一些对象很特别：
比如数组，是有一片连续的内存组成的，可以通过数组的下标来访问到数组里面的每一个对象。
再比如链表，在自己的内存空间中不仅存储值内容，还有一个指向下一个元素指针/引用，一般都叫个next或者pre之类的名字。
再比如二叉树，有两个引用，比如left和right。
照着这个逻辑一个对象可以有三个引用吗？当然可以比如二叉树再维护一下父元素的引用，left,right和parent。
那四个呢，也可以up down left right。
五个六个七八个呢，个人觉得也是可以的，大不了next1,next2,next3,next4,next5,next6但是代码如果写到这个程度，多少有点不优雅。
一个引用叫链表，两个可以维护一颗二叉树，多个拼起来也是一种数据结构叫做图。图里面的每一个元素叫做顶点。
个人理解觉得链表和二叉树都是图的范畴。都是用引用跟另外的元素连接起来。那么如果一个元素跟另外的100个元素都能连接我是不是要维护100个引用呢。
前辈告诉我们不需要。图有专门的记录方式，最经典的就是两种：
一种是矩阵，比如我有100个元素（顶点），那么维护一个长度是100的数组来记录顶点。然后在维护一个边长是100的矩阵（正方形），用一种标志标记两个顶点是否相连比如1，另外的标志标记连个顶点不相连，比如无穷大或者0。
一种是链表，比如还是100个顶点，还是长度100的数组记录顶点，然后维护一个长度100的链表桶，就跟java里面HashMap的存储结构一样，每个链表记录与该顶点相连的其他顶点。
好了终于进入今天的正文了，深度/广度优先搜索就是为遍历图数据结构的算法。
首先是深度优先，我不关心这个顶点有几个相连元素，我每次只取一个，并标记已访问的元素，直到没有下一个或者所有的都访问到。
然后是广度优先，我把一个定点所有的元素全部访问到(第一层)，然后再去访问第二层，第三层直到所有的元素访问完毕。
深度优先搜索不好理解的地方在于回溯。就是如果一条路走不通，需要重新回溯回来重新搜索。
而广度优先搜索需要借助一种数据结构队列，才能完成。大体的逻辑就是先把第一个顶点元素入队列，然后搜索这个顶点所有的节点入队之后第一个定点出队，在队列中再取出另外的元素继续这个过程直到队列元素为空，利用的队列先进先出的特性。
一个算法例子：
宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，
宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，
路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
表数如下：
// -3：妈妈
// -2：宝宝
// -1：障碍
// ≥0：糖果数（0表示没有糖果，但是可以走）
// 4
// 3 2 1 -3
// 1 -1 1 1
// 1 1 -1 2
// -2 1 2 3
这个题目要求最短时间到达，第一反应是使用广度优先搜索，一层一层的搜索，直到为妈妈找到一条最短的路径。
代码说明，首先看Pos对象注意其visit属性，这个是必须要维护的，网上你凡是能搜索到的免费答案，几乎都是错的，付费的咱不知道。
维护一个全局的是否访问属性，能叫广度搜索吗？稍微给一个复杂点的例子都跑不通。
以上欢迎大佬批评指正。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/kjbd-yiny/63889.html