- 浏览: 604334 次
- 来自: ...
文章分类
最新评论
-
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 632... -
求推箱子的最小步数(java)
2014-05-06 08:32 3776题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
回溯法入门学习之二(九宫格与数独)
2012-11-11 08:53 3337回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避 ... -
回溯法入门学习之一
2012-11-10 15:53 1850一: 回溯法 有时我们要得到问题的解,先从其中某一种情况 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1943很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5941Bellman-Ford算法: ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ... -
深度优先搜索学习五例之五(JAVA)
2012-10-22 15:48 1249一、深度优先搜索遍历磁盘文件目录 import java.io ... -
深度优先搜索学习五例之四(JAVA)
2012-10-21 17:25 2031先继续“深度优先搜索学习五例之三”http://128k ... -
深度优先搜索学习五例之三(JAVA)
2012-10-20 20:43 2317一、深度优先搜索框架一递归实现,流程如下: ... -
深度优先搜索学习五例之二(JAVA)
2012-10-20 12:24 2270继续“深度优先搜索学习五例之一 ”中的第一例子:http:// ... -
深度优先搜索学习五例之一(JAVA)
2012-10-19 14:54 4985深度优先搜索DFS(Depth First Search) ( ... -
广度优先搜索学习五例之五
2012-10-17 21:11 1446如果已经知道搜索的开始状态和结束状态,要找一个满足某种条 ... -
广度优先搜索学习五例之四
2012-10-16 15:26 1170例:输出由数字0,1,2..n ... -
广度优先搜索学习五例之三
2012-10-14 19:19 1505广度优先搜索是以某一节点为出发点,先拜访所有相邻的节点。 ... -
广度优先搜索学习五例之二(JAVA)
2012-10-12 14:32 2132再次强调: 图的广度优先搜索,要遵守以下规则: (0) 选取某 ... -
动态规划算法学习十例之十
2012-10-08 21:00 2280凸多边形最优三角剖分 一凸8边形P的顶点顺时针为{v1 ... -
动态规划算法学习十例之九
2012-10-07 15:50 1112最长单调递增子序列的长度问题 所谓子序列,就是在原序列里删 ... -
动态规划算法学习十例之八
2012-10-05 15:14 1285矩阵链乘法最优结合问题 一、《问题的引出》 看下面一个 ...
相关推荐
【标题】:“广度优先搜索学习五例之四” 在计算机科学中,广度优先搜索(Breadth-First Search,简称BFS)是一种用于遍历或搜索树或图的算法。它按照从根节点开始,逐层进行探索的方式进行。在本案例中,我们可能...
【标题】:“广度优先搜索学习五例之二(JAVA)” 在计算机科学中,图算法是解决问题的关键工具之一,而广度优先搜索(Breadth-First Search, BFS)是一种用于遍历或搜索树或图的算法。本篇文章将重点讲解如何在...
【标题】"广度优先搜索学习五例之三"涉及的是图论算法中的一个重要概念——广度优先搜索(Breadth-First Search, BFS)。在计算机科学中,BFS是一种用于遍历或搜索树或图的算法,尤其适用于查找最短路径问题。此标题...
在给定的"广度优先搜索学习五例之五"中,我们可能探讨的是一个具体的应用场景或者变体,但描述中并未提供详细信息。通常,BFS 的实现涉及以下几个关键元素: 1. **队列(Queue)**:BFS 使用队列作为主要的数据结构...
在这个主题"深度优先搜索学习五例之一(JAVA)"中,我们可以期待看到至少五个不同的应用实例,这些实例将用Java语言实现,可能包括但不限于以下场景: 1. **图的遍历**:DFS可以用于遍历无向图或有向图,通过访问每...
在这个“深度优先搜索学习五例之四”的主题中,我们将重点关注使用Java实现DFS解决具体问题的情况。这篇博客文章可能通过一个具体的实例,如迷宫求解,来演示如何利用DFS进行递归或栈操作。 首先,我们来看"MazeDsf...
盲目搜索如宽度优先搜索(BFS)和深度优先搜索(DFS),在未知环境中探索所有可能的解决方案路径,虽然简单但效率较低。启发式搜索则依据某种评估函数来指导搜索方向,如A*搜索,通过结合路径代价和预计到达目标的...
而图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS),则为处理复杂数据结构提供了有力的工具。更高级的算法,如动态规划,则能够指导学习者如何将复杂问题分解为更易于管理和求解的子问题。 第二部分的...
盲目搜索算法,如深度优先搜索(DFS)和宽度优先搜索(BFS),它们在搜索过程中不利用问题的任何特性,而是按照固定的顺序遍历状态空间,直至找到解答。深度优先搜索通过递归地探索可能的状态分支来找到解决方案,而...
- 广度优先搜索(BFS):一种用于遍历或搜索树或图的算法。它先访问起始点的邻接节点,然后是邻接节点的邻接节点,依此类推。 - 启发式搜索:利用特定问题领域的知识来引导搜索过程,如A*搜索算法。 - 双向搜索:...
搜索算法如二分查找、广度优先搜索(BFS)和深度优先搜索(DFS),在解决图论问题和树形结构问题时非常关键。动态规划是一种强大的问题解决方法,通过构建状态转移方程,可以解决很多复杂的问题,如斐波那契数列、...
图的遍历算法是图论中的基础概念之一,深度优先遍历和广度优先遍历各有优缺点,具体选择哪种遍历方法取决于实际应用场景的需求。例如,在搜索最短路径问题中,广度优先遍历更合适;而在搜索所有可能路径的问题中,...
在C语言中实现这样的算法,通常会用到深度优先搜索(DFS)或广度优先搜索(BFS)等图遍历策略,也可能涉及动态规划等复杂算法。 通过这个文件,学习者可以了解到如何在C语言中表示图,如何遍历图以及如何设计和实现...
广度优先搜索是另一种遍历策略,它先探索节点的所有相邻节点,然后再探索这些相邻节点的相邻节点。在8数码问题中,BFS会按照距离起点的步数来寻找解决方案,即先尝试找到最近的解。BFS通常使用队列数据结构来实现。 ...
例如,快速排序、归并排序、二分查找、哈希表、贪心算法、深度优先搜索和广度优先搜索等。这些都是ACM竞赛中常见的问题类型,学习这些算法不仅可以提升你的编程能力,也能训练你的逻辑思维和问题解决技巧。 C语言的...
最小生成树是图论中的一个重要概念,特别是在...通过深度优先搜索和广度优先搜索,我们可以找到图中的路径和最短路径,进而构造出最小生成树。这些算法在解决实际问题如网络设计、运输调度等场景中具有广泛的应用价值。
5. **算法实现**:C语言是实现算法的理想工具,实例可能涵盖了排序(如冒泡排序、快速排序)、查找(如线性查找、二分查找)、图算法(如深度优先搜索、广度优先搜索)等经典算法。 6. **游戏编程**:例如“俄罗斯...
宽度优先搜索逐层进行探索,直至找到目标,而深度优先搜索则尽可能深地搜索,直到不能再深入为止。尽管这些方法简单易实现,但在面对大规模问题时,搜索空间的庞大可能导致搜索效率低下。 相比之下,启发式搜索策略...
图形算法部分,读者将接触到深度优先搜索、广度优先搜索和拓扑排序等算法。这些算法在处理图结构数据时尤为关键,例如在社交网络分析、网页爬虫设计等领域有着广泛的应用。以拓扑排序为例,它能够将有向无环图中的...