- 浏览: 584675 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈或递归来实现,而广度优先搜索通过队列来实现。
广度优先搜索:
它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点)入队列,标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
例二:迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
下载源码
广度优先搜索:
它首先访问起始顶点的所有邻接点,然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。
图的广度优先搜索,要遵守以下规则:
(0) 选取某一顶点作为开始搜索的起点(当前顶点)入队列,标记为已访问。
(1) 访问当前顶点的下一个未被访问的邻接点,这个点必须是当前顶点的邻接点,标记它,并把它插入到队列中。
(2) 如果因为已经没有未访问的邻接点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2,则搜索结束。
例一:文件目录的广度优先遍历 private static void BFS(File file) throws IOException{ System.out.println(file.getCanonicalPath());//先访问起点 Queue< File> queue = new LinkedList< File>(); queue.offer(file); //起点入队 File fileInQueue = null; while (queue.size() > 0) { fileInQueue = queue.poll(); //当前顶点出队列 File[] files =fileInQueue.listFiles(); //求出当前顶点的所有邻接点 for (File eachFile : files) {//依次访问当前顶点的所有邻接点 if (eachFile.isFile()) {//标记这个邻接点已访问,是文件没有必要入队列 System.out.println("file:" + eachFile.getCanonicalPath()); } else {//标记这个邻接点已访问,是目录则入队列 System.out.println("dir--:" + eachFile.getCanonicalPath()); queue.offer(eachFile); } }//当前顶点所有邻接点访问完毕 }//队列为空退出 }
例二:迷宫问题
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径,格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
import java.util.*; public class Main{ private Point cur,next;//当前顶点及它的邻接点 private Point record[][];//用来记录路径 private int dir[][]={{0,1},{1,0},{0,-1},{-1,0}};//沿四个方向,右,下,左,上 private int mark[][]; //迷宫数组 public Main(int mark[][]){//构造函数 this.mark=mark; record=new Point[5][5]; for(int i=0;i< 5;i++) for(int j=0;j< 5;j++) record[i][j]=new Point(); cur=new Point(); next=new Point(); } public void bfs(){ //广度优先搜索迷宫 int i; Queue<Point> qu=new LinkedList<Point>(); cur.x=0; cur.y=0; qu.offer(cur); //起点入队 mark[0][0]=1; //标记为已访问 while(!qu.isEmpty()) { //队列非空 cur=qu.poll(); //队列头节点出队,当前节点 //访问当前节点的所有邻接点,可能有四个,沿四个方向,右,下,左,上 for(i=0;i<4;i++){ next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(next.x==4&&next.y==4){//如果是出口 record[next.x][next.y].x=cur.x; //这个节点存上个节点的坐标 record[next.x][next.y].y=cur.y; return; } if(next.x>=0&&next.x<5&&next.y>=0&&next.y<5&&mark[next.x][next.y]==0){ //如果是邻接点 //这个节点存上个节点的坐标 record[next.x][next.y].x=cur.x; //这个节点存上个节点的坐标 record[next.x][next.y].y=cur.y; mark[next.x][next.y]=1; //标记此邻接点已访问 qu.offer(new Point(next.x,next.y)); //入队 } }//当前点的所有邻接点访问完毕 } //队列为空 } public void print(){ Point point[]=new Point[50]; int i=4;int j=4;int k=0; int m=0;int n=0; while(i!=0||j!=0)/////把得到的记录record[][]存起来 { m=i;n=j; point[k]=record[m][n]; i=record[m][n].x; j=record[m][n].y; k++; } for(i=k-1;i>=0;i--)/////////////逆序输出 System.out.printf("(%d, %d)\n",point[i].x,point[i].y); System.out.printf("(4, 4)\n");////最后要打印的,之前没记录它 } public static void main(String[] args) { Scanner in=new Scanner(System.in); int[][] mark=new int[5][5]; for(int i=0;i< 5;i++) for(int j=0;j< 5;j++) mark[i][j]=in.nextInt(); Main m=new Main(mark); m.bfs(); m.print(); } } class Point { int x = 0; int y = 0; public Point() { this(0, 0); } public Point(int x, int y) { this.x = x; this.y = y; } public boolean equals(Point p) { return (x == p.x) && (y == p.y); } @Override public String toString() { return "(" + x + ", " + y + ")"; } }
下载源码
发表评论
-
龙抬头
2014-11-10 15:06 551... -
求推箱子的最小步数(java)
2014-05-06 08:32 3664题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2983POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3119回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1776一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1870很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5822Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3989一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1211一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 1966先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2264一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2225继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4907深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1403如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1101例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1459广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2064再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2222凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1070最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1233矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1699349
NULL 博文链接:https://128kj.iteye.com/blog/1697125
NULL 博文链接:https://128kj.iteye.com/blog/1700567
NULL 博文链接:https://128kj.iteye.com/blog/1698144
广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略。本程序用Matlab语言实现广度优先算法
②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识, 连同如何使用这些知识的方法,均隐式的表达为 一个求解问题的过程,每个...
人工智能实验 宽度优先搜索 人工智能实验 宽度优先搜索
BFS DFS 深度优先搜索 广度优先搜索 图 输出所有路径 输出最短路径 随便输出一条可能的路径
采用宽度优先搜索算法,编程实现八数码问题的求解。初始状态和目标状态可自定;采用宽度优先搜索算法,编程实现八数码问题的求解。初始状态和目标状态可自定采用宽度优先搜索算法,编程实现八数码问题的求解。初始...
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
MATLAB源码集锦-基于BFS广度优先搜索算法代码
易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言...
邻接表表示的图的深度优先搜索和广度优先搜索程序
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
广度优先搜索例题及代码详解 通过广度优先搜索的题目练习初步掌握广度优先搜索的机理
广度优先搜索和宽度优先搜索的动画演示,均为gif图,大家可以自行看看,理解思路或者放Ppt里很好用,怎么分数是5分,编辑不了了? 请管理员修改为1分,谢谢
参考中国大学MOOC,计算机算法与程序设计,5.2节内容,实现Python广度优先求最短路径。课程该章节没有课件,我手敲的代码调试好了,供大家一起学习!!!
Problem A【一本通基础广度优先搜索】细胞 Problem B【一本通基础广度优先搜索】 最少步数 Problem C【一本通基础广度优先搜索】The Castle Problem D【一本通基础广度优先搜索】Dungeon Master Problem E【一本通...