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